跳到主要导航 跳到搜索 跳到主要内容

RNSG: A Range-Aware Graph Index for Efficient Range-Filtered Approximate Nearest Neighbor Search

  • Beijing Institute of Technology
  • Nanyang Technological University

科研成果: 期刊稿件 › 会议文章 › 同行评审

摘要

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' 的科研主题。它们共同构成独一无二的学术指纹。

引用此