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

CREATORYuanhang Yu, Dawei Cheng, Ying Zhang, Lu Qin, Wenjie Zhang, Xuemin Lin
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE70 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-15488

Browse the full library · About the Tower of Babel