{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T15:43:04Z","timestamp":1783784584117,"version":"3.55.0"},"reference-count":60,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"name":"Hong Kong RGC GRF grant","award":["No. 14217322"],"award-info":[{"award-number":["No. 14217322"]}]},{"name":"Research Grants Council of Hong Kong Special Administrative Region, China","award":["No. PolyU 25201221, PolyU 15205224"],"award-info":[{"award-number":["No. PolyU 25201221, PolyU 15205224"]}]},{"name":"Hong Kong ITC ITF grant","award":["No. MRP\/071\/20X"],"award-info":[{"award-number":["No. MRP\/071\/20X"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,17]]},"abstract":"<jats:p>\n                    Given a set O of objects consisting of\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    high-dimensional vectors, the problem of\n                    <jats:italic toggle=\"yes\">approximate nearest neighbor (ANN)<\/jats:italic>\n                    search for a query vector\n                    <jats:bold>q<\/jats:bold>\n                    is crucial in many applications where objects are represented as feature vectors in high-dimensional spaces. Each object in O often has attributes like popularity or price, which influence the search. Practically, searching for the nearest neighbor to\n                    <jats:bold>q<\/jats:bold>\n                    might include a range filter specifying the desired attribute values, e.g., within a specific price range. Existing solutions for range filtered ANN search often face trade-offs among excessive storage, poor query performance, and limited support for updates. To address this challenge, we propose RangePQ, a novel indexing scheme that supports efficient range filtered ANN searches and updates, requiring only linear space. Our scheme integrates seamlessly with existing PQ-based index---a widely recognized, scalable index type for ANN searches---to enhance range-filtered ANN queries and update capabilities. Our indexing method, supporting arbitrary range filters, has a space complexity of (O(n log K)), where K is a parameter of the PQ-based index and log K scales with O(log n). To reduce the space cost, we further present a hybrid two-layer structure to reduce space usage to O(n), preserving query efficiency without additional update costs. Experimental results demonstrate that our indexing scheme significantly improves query performance while maintaining competitive update performance and space efficiency.\n                  <\/jats:p>","DOI":"10.1145\/3725401","type":"journal-article","created":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:23:29Z","timestamp":1750281809000},"page":"1-26","source":"Crossref","is-referenced-by-count":9,"title":["Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-3253-4661","authenticated-orcid":false,"given":"Fangyuan","family":"Zhang","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong SAR, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-5525-682X","authenticated-orcid":false,"given":"Mengxu","family":"Jiang","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-7932-6138","authenticated-orcid":false,"given":"Guanhao","family":"Hou","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong SAR, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-4236-1660","authenticated-orcid":false,"given":"Jieming","family":"Shi","sequence":"additional","affiliation":[{"name":"The Hong Kong Polytechnic University, Hong Kong SAR, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6230-0445","authenticated-orcid":false,"given":"Hua","family":"Fan","sequence":"additional","affiliation":[{"name":"Alibaba Cloud Computing, Hang Zhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-2689-6020","authenticated-orcid":false,"given":"Wenchao","family":"Zhou","sequence":"additional","affiliation":[{"name":"Alibaba Cloud Computing, Hang Zhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-0770-5775","authenticated-orcid":false,"given":"Feifei","family":"Li","sequence":"additional","affiliation":[{"name":"Alibaba Cloud Computing, Hang Zhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1892-6971","authenticated-orcid":false,"given":"Sibo","family":"Wang","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/3611479.3611537"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327494"},{"key":"e_1_2_1_3_1","first-page":"1225","article-title":"Practical and Optimal LSH for Angular Distance","author":"Andoni Alexandr","year":"2015","unstructured":"Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya P. Razenshteyn, and Ludwig Schmidt. 2015. Practical and Optimal LSH for Angular Distance. In NeurIPS. 1225-1233.","journal-title":"NeurIPS."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/2856318.2856324"},{"key":"e_1_2_1_5_1","first-page":"12","article-title":"Cache locality is not enough: High-performance nearest neighbor search with product quantization fast scan","volume":"9","author":"Andr\u00e9 Fabien","year":"2016","unstructured":"Fabien Andr\u00e9, Anne-Marie Kermarrec, and Nicolas Le Scouarnec. 2016. Cache locality is not enough: High-performance nearest neighbor search with product quantization fast scan. In VLDB, Vol. 9. 12.","journal-title":"VLDB"},{"key":"e_1_2_1_6_1","first-page":"271","article-title":"Approximate Nearest Neighbor Queries in Fixed Dimensions","author":"Arya Sunil","year":"1993","unstructured":"Sunil Arya and David M. Mount. 1993. Approximate Nearest Neighbor Queries in Fixed Dimensions. In SODA. 271-280.","journal-title":"SODA."},{"key":"e_1_2_1_7_1","first-page":"3069","article-title":"The inverted multi-index","author":"Babenko Artem","year":"2012","unstructured":"Artem Babenko and Victor S. Lempitsky. 2012. The inverted multi-index. In CVPR. 3069-3076.","journal-title":"CVPR."},{"key":"e_1_2_1_8_1","first-page":"4240","article-title":"Tree quantization for large-scale similarity search and classification","author":"Babenko Artem","year":"2015","unstructured":"Artem Babenko and Victor S. Lempitsky. 2015. Tree quantization for large-scale similarity search and classification. In CVPR. 4240-4248.","journal-title":"CVPR."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-01258-8_13"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_2_1_11_1","volume-title":"Annoy: Approximate Nearest Neighbors in C\/Python. https:\/\/pypi.org\/project\/annoy\/ Python package version 1.13.0.","author":"Bernhardsson Erik","year":"2018","unstructured":"Erik Bernhardsson. 2018. Annoy: Approximate Nearest Neighbors in C\/Python. https:\/\/pypi.org\/project\/annoy\/ Python package version 1.13.0."},{"key":"e_1_2_1_12_1","volume-title":"SIGIR 2012 workshop on open source information retrieval. 17","author":"Bia\u0142ecki Andrzej","year":"2012","unstructured":"Andrzej Bia\u0142ecki, Robert Muir, Grant Ingersoll, and Lucid Imagination. 2012. Apache lucene 4. In SIGIR 2012 workshop on open source information retrieval. 17."},{"key":"e_1_2_1_13_1","volume-title":"Guttag","author":"Blalock Davis W.","year":"2017","unstructured":"Davis W. Blalock and John V. Guttag. 2017. Bolt: Accelerated Data Mining with Fast Vector Compression. In SIGKDD. 727-735."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90018-3"},{"key":"e_1_2_1_15_1","volume-title":"SPANN: Highly-efficient Billion-scale Approximate Nearest Neighborhood Search. In NeurIPS, .","author":"Chen Qi","year":"2021","unstructured":"Qi Chen, Bing Zhao, Haidong Wang, Mingqin Li, Chuanjie Liu, Zengzhong Li, Mao Yang, and Jingdong Wang. 2021. SPANN: Highly-efficient Billion-scale Approximate Nearest Neighborhood Search. In NeurIPS, ."},{"key":"e_1_2_1_16_1","first-page":"537","article-title":"Random projection trees and low dimensional manifolds","author":"Dasgupta Sanjoy","year":"2008","unstructured":"Sanjoy Dasgupta and Yoav Freund. 2008. Random projection trees and low dimensional manifolds. In STOC. 537-546.","journal-title":"STOC."},{"key":"e_1_2_1_17_1","first-page":"253","article-title":"Locality-sensitive hashing scheme based on p-stable distributions","author":"Datar Mayur","year":"2004","unstructured":"Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S Mirrokni. 2004. Locality-sensitive hashing scheme based on p-stable distributions. In PoCG. 253-262.","journal-title":"PoCG."},{"key":"e_1_2_1_18_1","first-page":"577","article-title":"Efficient k-nearest neighbor graph construction for generic similarity measures","author":"Dong Wei","year":"2011","unstructured":"Wei Dong, Moses Charikar, and Kai Li. 2011. Efficient k-nearest neighbor graph construction for generic similarity measures. In WWW. 577-586.","journal-title":"WWW."},{"key":"e_1_2_1_19_1","unstructured":"Matthijs Douze Alexandr Guzhva Chengqi Deng Jeff Johnson Gergely Szilvasy Pierre-Emmanuel Mazar\u00e9 Maria Lomeli Lucas Hosseini and Herv\u00e9 J\u00e9gou. 2024. The Faiss library. (2024). arxiv:2401.08281 [cs.LG]"},{"key":"e_1_2_1_20_1","unstructured":"Joshua Engels Benjamin Landrum Shangdi Yu Laxman Dhulipala and Julian Shun. 2024. Approximate Nearest Neighbor Search with Window Filters. In ICML ."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/3303753.3303754"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654970"},{"key":"e_1_2_1_23_1","first-page":"2946","article-title":"Optimized Product Quantization for Approximate Nearest Neighbor Search","author":"Ge Tiezheng","year":"2013","unstructured":"Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. 2013. Optimized Product Quantization for Approximate Nearest Neighbor Search. In CVPR. 2946-2953.","journal-title":"CVPR."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.273032"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Martin Grohe. 2020. word2vec node2vec graph2vec X2vec: Towards a Theory of Vector Embeddings of Structured Data. In PODS .","DOI":"10.1145\/3375395.3387641"},{"key":"e_1_2_1_26_1","first-page":"855","article-title":"node2vec","author":"Grover Aditya","year":"2016","unstructured":"Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable Feature Learning for Networks. In SIGKDD. 855-864.","journal-title":"Scalable Feature Learning for Networks. In SIGKDD."},{"key":"e_1_2_1_27_1","unstructured":"Ruiqi Guo Philip Sun Erik Lindgren Quan Geng David Simcha Felix Chern and Sanjiv Kumar. 2020. Accelerating Large-Scale Inference with Anisotropic Vector Quantization. In ICML."},{"key":"e_1_2_1_28_1","first-page":"604","article-title":"Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality","author":"Indyk Piotr","year":"1998","unstructured":"Piotr Indyk and Rajeev Motwani. 1998. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. In STOC. 604-613.","journal-title":"STOC."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.57"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TBDATA.2019.2921572"},{"key":"e_1_2_1_31_1","first-page":"2329","article-title":"Locally Optimized Product Quantization for Approximate Nearest Neighbor Search","author":"Kalantidis Yannis","year":"2014","unstructured":"Yannis Kalantidis and Yannis Avrithis. 2014. Locally Optimized Product Quantization for Approximate Nearest Neighbor Search. In CVPR. 2329-2336.","journal-title":"CVPR."},{"key":"e_1_2_1_32_1","unstructured":"Donald Ervin Knuth et al. 1973. The art of computer programming. Vol. 3."},{"key":"e_1_2_1_33_1","first-page":"1188","article-title":"Distributed representations of sentences and documents","author":"Le Quoc","year":"2014","unstructured":"Quoc Le and Tomas Mikolov. 2014. Distributed representations of sentences and documents. In ICML. 1188-1196.","journal-title":"ICML."},{"key":"e_1_2_1_34_1","volume-title":"Deep learning. nature","author":"LeCun Yann","year":"2015","unstructured":"Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. 2015. Deep learning. nature, Vol. 521, 7553 (2015), 436-444."},{"key":"e_1_2_1_35_1","volume-title":"Man Lung Yiu, and Nikos Mamoulis.","author":"Li Hui","year":"2017","unstructured":"Hui Li, Tsz Nam Chan, Man Lung Yiu, and Nikos Mamoulis. 2017. FEXIPRO: Fast and Exact Inner Product Retrieval in Recommender Systems. In SIGMOD. 835-850."},{"key":"e_1_2_1_36_1","first-page":"695","article-title":"LightRec","author":"Lian Defu","year":"2020","unstructured":"Defu Lian, Haoyu Wang, Zheng Liu, Jianxun Lian, Enhong Chen, and Xing Xie. 2020. LightRec: A Memory and Search-Efficient Recommender System. In WWW. 695-705.","journal-title":"A Memory and Search-Efficient Recommender System. In WWW."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2013.10.006"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2018.2889473"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1093\/imamat\/24.1.59"},{"key":"e_1_2_1_40_1","volume-title":"Reconfigurable Inverted Index. In ACM Multimedia Conference on Multimedia Conference, MM,. ACM, 1715-1723","author":"Matsui Yusuke","year":"2018","unstructured":"Yusuke Matsui, Ryota Hinami, and Shin'ichi Satoh. 2018. Reconfigurable Inverted Index. In ACM Multimedia Conference on Multimedia Conference, MM,. ACM, 1715-1723."},{"key":"e_1_2_1_41_1","first-page":"2630","article-title":"HowTo100M: Learning a Text-Video Embedding by Watching Hundred Million Narrated Video Clips","author":"Miech Antoine","year":"2019","unstructured":"Antoine Miech, Dimitri Zhukov, Jean-Baptiste Alayrac, Makarand Tapaswi, Ivan Laptev, and Josef Sivic. 2019. HowTo100M: Learning a Text-Video Embedding by Watching Hundred Million Narrated Video Clips. In ICCV. 2630-2640.","journal-title":"ICCV."},{"key":"e_1_2_1_42_1","volume-title":"NeurIPS","volume":"26","author":"Mikolov Tomas","year":"2013","unstructured":"Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. 2013. Distributed representations of words and phrases and their compositionality. NeurIPS, Vol. 26 (2013)."},{"key":"e_1_2_1_43_1","unstructured":"Marius Muja and David Lowe. 2009. Flann-fast library for approximate nearest neighbors user manual. (2009)."},{"key":"e_1_2_1_44_1","unstructured":"James Jie Pan Jianguo Wang and Guoliang Li. 2023. Survey of vector database management systems. (2023)."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654923"},{"key":"e_1_2_1_46_1","first-page":"91","article-title":"Local Convolutional Features with Unsupervised Training for Image Retrieval","author":"Paulin Mattis","year":"2015","unstructured":"Mattis Paulin, Matthijs Douze, Za\u00efd Harchaoui, Julien Mairal, Florent Perronnin, and Cordelia Schmid. 2015. Local Convolutional Features with Unsupervised Training for Image Retrieval. In ICCV. 91-99.","journal-title":"ICCV."},{"key":"e_1_2_1_47_1","first-page":"412","article-title":"Learning a Nonlinear Embedding by Preserving Class Neighbourhood Structure","volume":"2","author":"Salakhutdinov Ruslan","year":"2007","unstructured":"Ruslan Salakhutdinov and Geoffrey E. Hinton. 2007. Learning a Nonlinear Embedding by Preserving Class Neighbourhood Structure. In AISTATS, Vol. 2. 412-419.","journal-title":"AISTATS"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3624724"},{"key":"e_1_2_1_49_1","volume-title":"Hartley","author":"Silpa-Anan Chanop","year":"2008","unstructured":"Chanop Silpa-Anan and Richard I. Hartley. 2008. Optimised KD-trees for fast image descriptor matching. In CVPR, ."},{"key":"e_1_2_1_50_1","volume-title":"Blelloch","author":"Sun Yihan","year":"2018","unstructured":"Yihan Sun, Daniel Ferizovic, and Guy E. Blelloch. 2018. PAM: parallel augmented maps. In PPoPP, Andreas Krall and Thomas R. Gross, (Eds.). 290-304."},{"key":"e_1_2_1_51_1","first-page":"129","article-title":"Algorithmic Techniques for Independent Query Sampling","author":"Tao Yufei","year":"2022","unstructured":"Yufei Tao. 2022. Algorithmic Techniques for Independent Query Sampling. In PODS. 129-138.","journal-title":"PODS."},{"key":"e_1_2_1_52_1","first-page":"2614","article-title":"Milvus","author":"Wang Jianguo","year":"2021","unstructured":"Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xiangyu Wang, Xiangzhou Guo, Chengming Li, Xiaohai Xu, Kun Yu, Yuxing Yuan, Yinghao Zou, Jiquan Long, Yudong Cai, Zhenxiang Li, Zhifeng Zhang, Yihua Mo, Jun Gu, Ruiyi Jiang, Yi Wei, and Charles Xie. 2021b. Milvus: A Purpose-Built Vector Data Management System. In SIGMOD. 2614-2627.","journal-title":"A Purpose-Built Vector Data Management System. In SIGMOD."},{"key":"e_1_2_1_53_1","first-page":"769","volume-title":"TPAMI","volume":"40","author":"Wang Jingdong","year":"2017","unstructured":"Jingdong Wang, Ting Zhang, Nicu Sebe, Heng Tao Shen, et al., 2017. A survey on learning to hash. TPAMI, Vol. 40, 4 (2017), 769-790."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476255"},{"key":"e_1_2_1_55_1","first-page":"194","article-title":"A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces","author":"Weber Roger","year":"1998","unstructured":"Roger Weber, Hans-J\u00f6rg Schek, and Stephen Blott. 1998. A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces. In VLDB. 194-205.","journal-title":"VLDB."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.14778\/3415478.3415541"},{"key":"e_1_2_1_57_1","first-page":"286","article-title":"Progressively Optimized Bi-Granular Document Representation for Scalable Embedding Based Retrieval","author":"Xiao Shitao","year":"2022","unstructured":"Shitao Xiao, Zheng Liu, Weihao Han, Jianjin Zhang, Yingxia Shao, Defu Lian, Chaozhuo Li, Hao Sun, Denvy Deng, Liangjie Zhang, Qi Zhang, and Xing Xie. 2022. Progressively Optimized Bi-Granular Document Representation for Scalable Embedding Based Retrieval. In WWW. 286-296.","journal-title":"WWW."},{"key":"e_1_2_1_58_1","first-page":"2241","article-title":"PASE","author":"Yang Wen","year":"2020","unstructured":"Wen Yang, Tao Li, Gai Fang, and Hong Wei. 2020. PASE: PostgreSQL Ultra-High-Dimensional Approximate Nearest Neighbor Search Extension. In SIGMOD. 2241-2253.","journal-title":"PostgreSQL Ultra-High-Dimensional Approximate Nearest Neighbor Search Extension. In SIGMOD."},{"key":"e_1_2_1_59_1","first-page":"377","article-title":"VBASE: Unifying Online Vector Similarity Search and Relational Queries via Relaxed Monotonicity","author":"Zhang Qianxi","year":"2023","unstructured":"Qianxi Zhang, Shuotao Xu, Qi Chen, Guoxin Sui, Jiadong Xie, Zhizhen Cai, Yaoqi Chen, Yinxuan He, Yuqing Yang, Fan Yang, Mao Yang, and Lidong Zhou. 2023. VBASE: Unifying Online Vector Similarity Search and Relational Queries via Relaxed Monotonicity. In OSDI. 377-395.","journal-title":"OSDI."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639324"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725401","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:58:59Z","timestamp":1774983539000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725401"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,17]]},"references-count":60,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6,17]]}},"alternative-id":["10.1145\/3725401"],"URL":"https:\/\/doi.org\/10.1145\/3725401","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,17]]}}}