Generalized Range Filtering Approximate Nearest Neighbor Search: Containment and Overlap [Technical Report] Conference: Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2; August 09–13, 2026; Jeju Island, Republic of Korea Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2 (KDD ’26), August 09–13, 2026, Jeju Island, Republic of Korea CCS: Information systems Information retrieval
Yingfan Liu, Tong Wu, Jiadong Xie, Yang Zhao, Jeffrey Xu Yu, Jiangtao Cui · 2026
Read Generalized Range Filtering Approximate Nearest Neighbor Search: Containment and Overlap [Technical Report] Conference: Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2; August 09–13, 2026; Jeju Island, Republic of Korea Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2 (KDD ’26), August 09–13, 2026, Jeju Island, Republic of Korea CCS: Information systems Information retrieval by Yingfan Liu, Tong Wu, Jiadong Xie, Yang Zhao, Jeffrey Xu Yu, Jiangtao Cui (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-26474.txt.
Introduction
Yingfan Liu and five colleagues widen nearest-neighbor search to ranges. Each vector carries a numeric range, like price bands or time spans. A query seeks the k closest vectors under any user range-range rule: containment both ways, overlap both ways, or a mix. Old methods fail arbitrary rules, so the team offers a multi-segment tree graph that skips nodes failing the rule. Index size and build time match the best filtered search. Real tests reach 12.5-fold speedups at same accuracy, with stronger interval and time search.
Catalog record
| CREATOR | Yingfan Liu, Tong Wu, Jiadong Xie, Yang Zhao, Jeffrey Xu Yu, Jiangtao Cui |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 78126 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.26474
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Generalized Range Filtering Approximate Nearest Neighbor Search: Containment and Overlap [Technical Report] Conference: Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2; August 09–13, 2026; Jeju Island, Republic of Korea Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2 (KDD ’26), August 09–13, 2026, Jeju Island, Republic of Korea CCS: Information systems Information retrieval Yingfan Liu, Tong Wu, Jiadong Xie, Yang Zhao, Jeffrey Xu Yu, Jiangtao Cui Abstract . 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 n n vectors in ℝ d \mathbb{R}^{d} , each vector v i v_{i} is associated with a numeric range [ l i , r i ] [l_{i},r_{i}] , symbolizing aspects like a price range or time interval. An RRANN query ( v q , l q , r q ) (v_{q},l_{q},r_{q}) aims at finding k k vectors closest to v q v_{q} within the vectors satisfying an arbitrary RR predicate defined between the query range [ l q , r q ] [l_{q},r_{q}] and the object range [ l i , r i ] [l_{i},r_{i}] . The RR predicate remains unspecified, enabling user-defined conditions. It may encompass containment ( [ l i , r i ] ⊆ [ l q , r q ] [l_{i},r_{i}]\subseteq[l_{q},r_{q}] or [ l q , r q ] ⊆ [ l i , r i ] [l_{q},r_{q}]\subseteq[l_{i},r_{i}] ), overlap ( l i ≤ l q ≤ r i ≤ r q l_{i}\leq l_{q}\leq r_{i}\leq r_{q} or l q ≤ l i ≤ r q ≤ r i l_{q}\leq l_{i}\leq r_{q}\leq r_{i} ), or a disjunction of them. RRANN has broad applications in queries related to price ranges or time intervals, and it generalizes existing variants 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 arbitrary RR predicates by avoiding traversal through non-predicate-satisfied nodes, and keeps equivalent index size and construction time 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 . † † cc-license: by 1. Introduction With the recent advancements in embedding models leveraging machine learning techniques, diverse objects, such as images ( Nasrabadi and King 1988 ) and texts ( Mikolov et al. 2013 ) , are embedded into high-dimensional vectors to capture their semantic information. This has led to the rise in popularity of vector databases in both research communities and the industry ( Liu et al. 2025 ; Pan et al. 2024 ; Azizi et al. 2023 ; Deng et al. 2025 ; Zhu et al. 2024 ) . In vector databases, the fundamental operation is the approximate k -nearest neighbor search ( k -ANNS), which retrieves k vectors sufficiently close to a given query vector. Vector databases like Milvus ( Wang et al. 2021b ) and AnalyticDB ( Wei et al. 2020 ) enhance search precision by integrating k -ANN search with attribute-based filters. In this paper, we study the k -ANNS with range filters. In numerous applications, each object in the dataset O is represented as o_{i}=(v_{i},l_{i},r_{i}) , where v_{i}\in\mathbb{R}^{d} is a d -dimensional vector and [l_{i},r_{i}]\subset\mathbb{R} is a numeric range. Similarly, each query q consists of a vector v_{q} and a range [l_{q},r_{q}] . Here, the range-range (RR) predicates between the query range and the object range are not specified, allowing user-defined conditions. As illustrated in Fig. 1 , there are four atomic conditions, including two types of containment and two types of overlap: ① query left-overlap: l_{i}\leq l_{q}\leq r_{i}\leq r_{q} ; ② query-contained: l_{i}\leq l_{q}\leq r_{q}\leq r_{i} ; ③ query right-overlap: l_{q}\leq l_{i}\leq r_{q}\leq r_{i} ; and ④ query-containing: l_{q}\leq l_{i}\leq r_{i}\leq r_{q} . The RR predicates can be one of them, or a disjunction of them. This problem, k -ANNS with arbitrary RR predicates, referred to as range-range filtering k -ANN (RRANN), has broad applications. Price Range Querying: The price of an object in real-world scenarios can be a continuous interval, such as a stock price range or prices of products on comparison shopping websites that aggregate product data across multiple online retailers. By using RRANN queries, users can search for objects that meet specific price predicates. For example, a user might seek a shoe resembling a provided image on comparison shopping websites, priced between $50 and $100. RRANN can be utilized to retrieve products (v_{i},l_{i},r_{i}) whose image vectors have the smallest distances to the query image vector, and simultaneously satisfy [l_{i},r_{i}]\cap[50,100]\neq\emptyset . Time-Relevant Querying: Consider multiple traffic cameras monitoring cars passing on a state highway. Each camera detects and extracts a feature vector representing every car in the video stream. These feature vectors, along with their time ranges on the highway, are stored in a database. Upon receiving a query containing a particular car image and a given time interval, RRANN can locate similar cars that traversed the highway within the query time range. Figure 1. The atomic conditions of the RR predicates Table 1. Comparisons between RRANN with other range-filtering k -ANN problems Problems Object Attribute Query Attribute RR Predicate QPS at Recall@10=0.95 on Gist dataset when selectivity is 10\% iRangeGraph ( Xu et al. 2025 ) Hi-PNG ( Yang et al. 2025a ) TS-Graph ( Wang et al. 2025 ) MSTG (ours) RFANN ( Xu et al. 2025 ) point-valued ( l_{i}=r_{i} ) range-valued [l_{i},r_{i}]\subseteq[l_{q},r_{q}] (④) 752.997 127.238 - 753.215 IFANN ( Yang et al. 2025a ) range-valued range-valued [l_{i},r_{i}]\subseteq[l_{q},r_{q}] (④) - 156.790 - 873.672 TSANN ( Wang et al. 2025 ) range-valued point-valued ( l_{q}=r_{q} ) [l_{q},r_{q}]\subseteq[l_{i},r_{i}] (②) - - 238.851 925.845 RRANN (ours) range-valued range-valued arbitrary - - - 604.572 General Form of other k -ANNS with Range Filters: There are three variations of k -ANNS with range filters: (1) range-filtering k -ANN (RFANN) ( Xu et al. 2025 ; Zuo et al. 2024 ; Zhang et al. 2023 ; Wei et al. 2020 ; Patel et al. 2024 ; Liang et al. 2025 ; Engels et al. 2024 ; Jiang et al. 2025 ; Xie et al. 2025c ) with point-valued object attribute and range-valued query attribute, (2) interval-filtering k -ANN (IFANN) ( Yang et al. 2025a ) with range-valued object attribute and range-valued query attribute but limited RR predicates, and (3) timestamp k -ANN (TSANN) ( Wang et al. 2025 ) with range-valued object attribute and point-valued query attribute. These variations, as outlined in Table 1 , are all special cases of our RRANN problem. Specifically, the RR predicate of RFANN is [l_{i},r_{i}]\subseteq[l_{q},r_{q}] (i.e., case ④) with l_{i}=r_{i} ; the RR predicate of IFANN is [l_{i},r_{i}]\subseteq[l_{q},r_{q}] (i.e., case ④); the RR predicate of TSANN is [l_{q},r_{q}]\subseteq[l_{i},r_{i}] (i.e., case ②) with l_{q}=r_{q}