ESG: Elastic Graphs For Range-filtering Approximate K-nearest Neighbor Search
2025 · Mingyu Yang, Wentao Li, Zhitao Shen, et al.
Abstract
Range-filtering approximate \(k\)-nearest neighbor (RFAKNN) search takes as input a vector and a numeric value, returning \(k\) points from a database of \(N\) high-dimensional points. The returned points must satisfy two criteria: their numeric values must lie within the specified query range, and they must be approximately the \(k\) nearest points to the query vector. To strike a better balance between query accuracy and efficiency, we propose novel methods that relax the strict requirement for subranges to \textit\{exactly\} match the query range. This elastic relaxation is based on a theoretical insight: allowing the controlled inclusion of out-of-range points during the search does not compromise the bounded complexity of the search process. Building on this insight, we prove that our methods reduce the number of required subranges to at most \textit\{two\}, eliminating the \(O(log N)\) query overhead inherent in existing methods. Extensive experiments on real-world datasets demon
Authors
(none)
Tags
Stats
Related papers
- Irangegraph: Improvising Range-dedicated Graphs For Range-filtering Nearest Neighbor Search (2024)8.35
- UNIFY: Unified Index For Range Filtered Approximate Nearest Neighbors Search (2024)3.58
- EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based On Knn Graph (2016)0.00
- Let Them Have CAKES: A Cutting-edge Algorithm For Scalable, Efficient, And Exact Search On Big Data (2023)2.68
- FINGER: Fast Inference For Graph-based Approximate Nearest Neighbor Search (2022)10.74
- High-dimensional Approximate Nearest Neighbor Search: With Reliable And Efficient Distance Comparison Operations (2023)13.44
- Effective And General Distance Computation For Approximate Nearest Neighbor Search (2024)5.84
- Hd-index: Pushing The Scalability-accuracy Boundary For Approximate Knn Search In High-dimensional Spaces (2018)14.02