iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914936072962048 |
|---|---|
| author | Xu, Yuexuan Gao, Jianyang Gou, Yutong Long, Cheng Jensen, Christian S. |
| author_facet | Xu, Yuexuan Gao, Jianyang Gou, Yutong Long, Cheng Jensen, Christian S. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_02571 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search Xu, Yuexuan Gao, Jianyang Gou, Yutong Long, Cheng Jensen, Christian S. Databases Data Structures and Algorithms Information Retrieval 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. |
| title | iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search |
| topic | Databases Data Structures and Algorithms Information Retrieval |
| url | https://arxiv.org/abs/2409.02571 |