iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search

• DOI: 10.1145/3698814
• Publication Date: 2024-12-20T21:40:35Z
• Authors: Yuexuan Xu; Jianyang Gao; Yutong Gou; Cheng Long; Christian S. Jensen
• Keywords: Range query (database); Online aggregation

Range-filtering approximate nearest neighbor (RFANN) search is attracting increasing attention in academia and industry. Given a set of data objects, each being pair high-dimensional vector numeric value, an RFANN query with range as parameters returns the object whose value to vector. To process this query, recent study proposes build O(n 2 ) dedicated graph-based indexes for all possible ranges enable efficient processing on database n objects. As storing these prohibitively expensive, constructs compressed instead, which reduces memory consumption considerably. However, incurs suboptimal performance because compression lossy. In study, instead materializing index every preparation querying, we materialize indexes, called elemental graphs, moderate number ranges. We then provide effective algorithm that during querying can construct any using graphs. prove time needed such low. also cover experimental real-world datasets provides evidence materialized graphs only consume space proposed method capable superior stable across different workloads.