{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T03:49:05Z","timestamp":1772164145699,"version":"3.50.1"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,6]]},"abstract":"<jats:p>\n            Range-filtering approximate nearest neighbor search (RFANNS) has gained significant attention recently. Consider a set\n            <jats:italic toggle=\"yes\">D<\/jats:italic>\n            of high-dimensional vectors, each associated with a numeric attribute value, e.g., price or timestamp. An RFANNS query consists of a query vector\n            <jats:italic toggle=\"yes\">q<\/jats:italic>\n            and a query range, reporting the approximate nearest neighbors of\n            <jats:italic toggle=\"yes\">q<\/jats:italic>\n            among data vectors whose attributes fall in the query range. Existing work on RFANNS only considers a static set\n            <jats:italic toggle=\"yes\">D<\/jats:italic>\n            of data vectors while in many real-world scenarios, vectors arrive in the system in an arbitrary order. This paper studies dynamic RFANNS where both data vectors and queries arrive in a mixed stream: a query is posed on all the data vectors that have already arrived in the system. Existing work on RFANNS is difficult to be extended to the streaming setting as they construct the index in the order of the attribute values while the vectors arrive in the system in an arbitrary order. The main challenge to the dynamic RFANNS lies in the difference between the two orders. A naive approach to RFANNS maintains multiple hierarchical navigable small-world (HNSW) graphs, one for each of the\n            <jats:italic toggle=\"yes\">O<\/jats:italic>\n            (|\n            <jats:italic toggle=\"yes\">D<\/jats:italic>\n            |\n            <jats:sup>2<\/jats:sup>\n            ) possible query ranges - too expensive to construct and maintain. To design an index structure that can integrate new data vectors with a low index size increment for efficient and effective query processing, we propose a structure called\n            <jats:italic toggle=\"yes\">dynamic segment graph.<\/jats:italic>\n            It compresses the set of HNSW graphs of the naive approach, proven to be lossless under certain conditions, with only a linear to log |\n            <jats:italic toggle=\"yes\">D<\/jats:italic>\n            | new edges in expectation when inserting a new vector. This dramatically reduces the index size while largely preserving the search performance. We further propose heuristics to significantly reduce the index cost of our dynamic segment graph in practice. Extensive experimental results show that our approach outperforms existing methods for static RFANNS and is scalable in handling dynamic RFANNS.\n          <\/jats:p>","DOI":"10.14778\/3748191.3748193","type":"journal-article","created":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T13:50:16Z","timestamp":1756993816000},"page":"3256-3268","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Dynamic Range-Filtering Approximate Nearest Neighbor Search"],"prefix":"10.14778","volume":"18","author":[{"given":"Zhencan","family":"Peng","sequence":"first","affiliation":[{"name":"Rutgers University"}]},{"given":"Miao","family":"Qiao","sequence":"additional","affiliation":[{"name":"The University of Auckland"}]},{"given":"Wenchao","family":"Zhou","sequence":"additional","affiliation":[{"name":"Alibaba Group"}]},{"given":"Feifei","family":"Li","sequence":"additional","affiliation":[{"name":"Alibaba Group"}]},{"given":"Dong","family":"Deng","sequence":"additional","affiliation":[{"name":"Rutgers University"}]}],"member":"320","published-online":{"date-parts":[[2025,9,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Alexandr Andoni and Piotr Indyk. 2006. Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions. In FOCS. 459\u2013468.","DOI":"10.1109\/FOCS.2006.49"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/2856318.2856324"},{"key":"e_1_2_1_3_1","volume-title":"Mount","author":"Arya Sunil","year":"1993","unstructured":"Sunil Arya and David M. Mount. 1993. Approximate Nearest Neighbor Queries in Fixed Dimensions. In ACM\/SIGACT-SIAM. 271\u2013280."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2016.226"},{"key":"e_1_2_1_5_1","volume-title":"Approximate Nearest Neighbor Search with Window Filters. In Forty-first International Conference on Machine Learning, ICML 2024","author":"Engels Joshua","year":"2024","unstructured":"Joshua Engels, Benjamin Landrum, Shangdi Yu, Laxman Dhulipala, and Julian Shun. 2024. Approximate Nearest Neighbor Search with Window Filters. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21\u201327, 2024. OpenReview.net. https:\/\/openreview.net\/forum?id=8t8zBaGFar"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/3303753.3303754"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Junhao Gan Jianlin Feng Qiong Fang and Wilfred Ng. 2012. Locality-sensitive hashing scheme based on dynamic collision counting. In SIGMOD. 541\u2013552.","DOI":"10.1145\/2213836.2213898"},{"key":"e_1_2_1_8_1","unstructured":"Tiezheng Ge Kaiming He Qifa Ke and Jian Sun. 2013. Optimized Product Quantization for Approximate Nearest Neighbor Search. In CVPR. 2946\u20132953."},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Siddharth Gollapudi Neel Karia Varun Sivashankar Ravishankar Krishnaswamy Nikit Begwani Swapnil Raz Yiyong Lin Yin Zhang Neelam Mahapatro Premkumar Srinivasan et al. 2023. Filtered-DiskANN: Graph Algorithms for Approximate Nearest Neighbor Search with Filters. In WWW. 3406\u20133416.","DOI":"10.1145\/3543507.3583552"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Antonin Guttman. 1984. R-Trees: A Dynamic Index Structure for Spatial Searching. In SIGMOD. 47\u201357.","DOI":"10.1145\/971697.602266"},{"key":"e_1_2_1_11_1","volume-title":"FANNG: Fast Approximate Nearest Neighbour Graphs. In CVPR. 5713\u20135722.","author":"Harwood Ben","year":"2016","unstructured":"Ben Harwood and Tom Drummond. 2016. FANNG: Fast Approximate Nearest Neighbour Graphs. In CVPR. 5713\u20135722."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850469.2850470"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Piotr Indyk and Rajeev Motwani. 1998. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. In STOC. 604\u2013613.","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.163414"},{"key":"e_1_2_1_15_1","volume-title":"Ravishankar Krishnawamy, and Rohan Kadekodi.","author":"Subramanya Suhas Jayaram","year":"2019","unstructured":"Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. 2019. DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. In NeurIPS, Vol. 32."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.57"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Yannis Kalantidis and Yannis Avrithis. 2014. Locally Optimized Product Quantization for Approximate Nearest Neighbor Search. In CVPR. 2329\u20132336.","DOI":"10.1109\/CVPR.2014.298"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2015.7298865"},{"key":"e_1_2_1_19_1","first-page":"9459","article-title":"Retrieval-augmented generation for knowledge-intensive nlp tasks","volume":"33","author":"Lewis Patrick","year":"2020","unstructured":"Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich K\u00fcttler, Mike Lewis, Wen-tau Yih, Tim Rockt\u00e4schel, et al. 2020. Retrieval-augmented generation for knowledge-intensive nlp tasks. Advances in Neural Information Processing Systems 33 (2020), 9459\u20139474.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_20_1","unstructured":"Jimmy Lin. 2024. Operational Advice for Dense and Sparse Retrievers: HNSW Flat or Inverted Indexes? arXiv:2409.06464 [cs.IR] https:\/\/arxiv.org\/abs\/2409.06464"},{"key":"e_1_2_1_21_1","volume-title":"Zhe Wang, Moses Charikar, and Kai Li.","author":"Lv Qin","year":"2007","unstructured":"Qin Lv, William Josephson, Zhe Wang, Moses Charikar, and Kai Li. 2007. Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search. In PVLDB. 950\u2013961."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2013.10.006"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2018.2889473"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","unstructured":"Yusuke Matsui Ryota Hinami and Shin'ichi Satoh. 2018. Reconfigurable Inverted Index. In MM. 1715\u20131723. 10.1145\/3240508.3240630","DOI":"10.1145\/3240508.3240630"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Yusuke Matsui Toshihiko Yamasaki and Kiyoharu Aizawa. 2015. PQTable: Fast Exact Asymmetric Distance Neighbor Search for Product Quantization Using Hash Tables. In ICCV. 1940\u20131948.","DOI":"10.1109\/ICCV.2015.225"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654923"},{"key":"e_1_2_1_27_1","unstructured":"Anshumali Shrivastava and Ping Li. 2014. Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS). In NeurIPS. 2321\u20132329."},{"key":"e_1_2_1_28_1","volume-title":"Ravishankar Krishnaswamy, and Harsha Vardhan Simhadri.","author":"Singh Aditi","year":"2021","unstructured":"Aditi Singh, Suhas Jayaram Subramanya, Ravishankar Krishnaswamy, and Harsha Vardhan Simhadri. 2021. FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search. arXiv:2105.09613 [cs.IR] https:\/\/arxiv.org\/abs\/2105.09613"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-024-00894-5"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457550"},{"key":"e_1_2_1_31_1","unstructured":"Mengzhao Wang Lingwei Lv Xiaoliang Xu Yuxiang Wang Qiang Yue and Jiongkang Ni. 2022. Navigable Proximity Graph-Driven Native Hybrid Queries with Structured and Unstructured Constraints. arXiv:2203.13601 [cs.DB]"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/3424573.3424580"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3415478.3415541"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3511808.3557610"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2817526"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2409.02571"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2210.14958"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2015.133"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/3603581.3603601"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639324"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3748191.3748193","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T13:53:26Z","timestamp":1756994006000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3748191.3748193"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6]]},"references-count":40,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["10.14778\/3748191.3748193"],"URL":"https:\/\/doi.org\/10.14778\/3748191.3748193","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2025,6]]},"assertion":[{"value":"2025-09-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}