摘要
Range-filtered approximate nearest neighbor (RFANN) search is a fundamental operation in modern data systems. Given a set of objects, each with a vector and a numerical attribute, an RFANN query retrieves the nearest neighbors to a query vector among those objects whose numerical attributes fall within the range specified by the query. Existing state-of-the-art methods for RFANN search often require constructing multiple range-specific graph indexes to achieve high query performance, which incurs significant indexing overhead. To address this, we first establish a novel graph indexing theory, the range-aware relative neighborhood graph (RRNG), which jointly considers spatial and attribute proximity. We prove that the RRNG satisfies two crucial properties: (1) monotonic search-ability, which ensures correct nearest neighbor retrieval via beam search; and (2) structural heredity, which guarantees that any range-induced sub-graph remains a valid RRNG, thus enabling efficient search with a single graph index. Based on this theoretical foundation, we propose a new graph index, called RNSG, as a practical solution that approximates RRNG efficiently. We develop fast algorithms for both constructing the RNSG index and processing RFANN queries with it. Extensive experiments on five real-world datasets show that RNSG achieves significantly higher query performance with a more compact index and lower construction cost than existing state-of-the-art methods.
| 源语言 | 英语 |
|---|---|
| 页(从-至) | 2839-2852 |
| 页数 | 14 |
| 期刊 | Proceedings of the VLDB Endowment |
| 卷 | 19 |
| 期 | 10 |
| DOI | |
| 出版状态 | 已出版 - 2026 |
| 活动 | 52nd International Conference on Very Large Data Bases, VLDB 2026 - Boston, 美国 期限: 31 8月 2026 → 4 9月 2026 |
学术指纹
探究 'RNSG: A Range-Aware Graph Index for Efficient Range-Filtered Approximate Nearest Neighbor Search' 的科研主题。它们共同构成独一无二的学术指纹。引用此
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver