Generalized Range Filtering Approximate Nearest Neighbor Search: Containment and Overlap

Approximate nearest neighbor (ANN) search with range filters has recently garnered significant attention. This paper delves into a generalized form of this problem, i.e., ANN search with exact range-range (RR) predicates on a range-valued attribute, named RR filtering ANN (RRANN). Specifically, given a set of objects consisting of n vectors in ℝd, where each vector vi is associated with a numeric range [li, ri], symbolizing aspects like a price range or time interval. An RRANN query (vq, lq, rq) aims at finding k vectors closest to vq within the vectors satisfying an arbitrary RR predicate defined between the query range [lq, rq] and the object range [li, ri]. The RR predicate remains unspecified, enabling user-defined conditions. It may encompass containment ([li, ri] ⊆ [lq, rq] or [lq, rq] ⊆ [li, ri]), overlap (li ≤ lq ≤ ri ≤ rq or lq ≤ li ≤ rq ≤ ri), or a disjunction of them. RRANN has broad applications in queries related to price ranges or time intervals, and serves as the general form for all existing variations of ANN search with range filters. However, existing dedicated approaches for these problems lack the capacity to support queries with arbitrary RR predicates. Hence, we introduce a new approach, labeled multi-segment tree graph. It efficiently handles queries with arbitrary RR predicates by avoiding traversal through non-predicate-satisfied nodes, and maintains index size and construction time equivalent to state-of-the-art methods for RFANN. Extensive experiments on real-world data demonstrate the efficacy of our approach in RRANN queries, achieving up to 12.5x speedups with the same accuracy as the baselines. Moreover, our approach attains comparable RFANN search performance and notably superior IFANN and TSANN search performance compared to the respective state-of-the-art approaches. Our code is available at https://github.com/FanEDG/MSTG.