iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search
Open Access
- 18 December 2024
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 2 (6) , 1-26
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, for a moderate number of ranges. We then provide an effective and efficient algorithm that during querying can construct an index for any query range using the elemental graphs. We prove that the time needed to construct such an index is low. We also cover an experimental study on real-world datasets that provides evidence that the materialized elemental graphs only consume moderate space and that the proposed method is capable of superior and stable query performance across different query workloads.Keywords
All Related Versions
Funding Information
- Ministry of Education - Singapore (Tier 2 Award MOE-T2EP20221-0013, Tier 2 Award MOE-T2EP20220-0011, and Tier 1 Award (RG77/21))
- Innovation Fund Denmark Centre, DIREC
This publication has 65 references indexed in Scilit:
- Pivot selection algorithms in metric spaces: a survey and experimental studyThe VLDB Journal, 2021
- Pruned Bi-directed K-nearest Neighbor Graph for Proximity Search2016
- HRG: A Graph Structure for Fast Similarity Search in Metric Spaces2008
- Half-Space Proximal: A New Local Test for Extracting a Bounded Dilation Spanner of a Unit Disk Graph2006
- Searching in metric spaces by spatial approximationThe VLDB Journal, 2002
- Constrained Nearest Neighbor Queries2001
- Computational Geometry2000
- Approximate similarity retrieval with M-treesThe VLDB Journal, 1998
- Proximity matching using fixed-queries trees1994
- An algorithm for finding nearest neighbours in (approximately) constant average timePattern Recognition Letters, 1986