Irangegraph: Improvising Range-dedicated Graphs For Range-filtering Nearest Neighbor Search
2024 · Yuexuan Xu, Jianyang Gao, Yutong Gou, et al.
Abstract
Range-filtering approximate nearest neighbor (RFANN) search is attracting increasing attention in academia and industry. Given a set of data objects, each being a pair of a high-dimensional vector and a numeric value, an RFANN query with a vector and a numeric range as parameters returns the data object whose numeric value is in the query range and whose vector is nearest to the query vector. To process this query, a recent study proposes to build \(O(n^2)\) dedicated graph-based indexes for all possible query ranges to enable efficient processing on a database of \(n\) objects. As storing all these indexes is prohibitively expensive, the study constructs compressed indexes instead, which reduces the memory consumption considerably. However, this incurs suboptimal performance because the compression is lossy. In this study, instead of materializing a compressed index for every possible query range in preparation for querying, we materialize graph-based indexes, called elemental graphs,
Authors
(none)
Tags
Stats
Related papers
- UNIFY: Unified Index For Range Filtered Approximate Nearest Neighbors Search (2024)3.58
- ESG: Elastic Graphs For Range-filtering Approximate K-nearest Neighbor Search (2025)0.00
- Frequency-aware Graph Construction And Search For Dynamic Vector Databases (2025)0.00
- A Scalable Solution To The Nearest Neighbor Search Problem Through Local-search Methods On Neighbor Graphs (2017)3.58
- A Comprehensive Survey And Experimental Comparison Of Graph-based Approximate Nearest Neighbor Search (2021)17.35
- Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph (2017)18.20
- Symphonyqg: Towards Symphonious Integration Of Quantization And Graph For Approximate Nearest Neighbor Search (2024)7.50
- EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based On Knn Graph (2016)0.00