Efficient Approximate Nearest Neighbor Search under Multi-Attribute Range Filter
Yuanhang Yu, Dawei Cheng, Ying Zhang, Lu Qin, Wenjie Zhang, Xuemin Lin · 2026
Read Efficient Approximate Nearest Neighbor Search under Multi-Attribute Range Filter by Yuanhang Yu, Dawei Cheng, Ying Zhang, Lu Qin, Wenjie Zhang, Xuemin Lin (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-15488.txt.
Description
Yu and colleagues tackle a search task common in modern AI and data systems. The task is to find near neighbours for a high-dimensional vector among items passing limits on several numeric traits. Older indexes handle one trait at a time, and stretching them tends to work poorly. The team answers with KHI, an index pairing a tree over attribute space with fast graph search at each node.
A skew-aware split rule keeps the tree shallow. A query walks the tree, then a greedy search runs on the graphs it meets. Tests on four real data sets show high throughput and high recall. KHI beats the best prior method by about two and a half times on average in queries per second, and far more on the hardest set. Gains grow when few items pass the filter, when more neighbours are sought, and when more traits are used.
Catalog record
| CREATOR | Yuanhang Yu, Dawei Cheng, Ying Zhang, Lu Qin, Wenjie Zhang, Xuemin Lin |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 70 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-15488