{"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":1783784584264,"version":"3.55.0"},"reference-count":40,"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>Recent advancements in AI have enabled models to map real-world entities, such as product images, into high-dimensional vectors, making approximate nearest neighbor search (ANNS) crucial for various applications. Often, these vectors are associated with additional attributes like price, prompting the need for range-filtered ANNS where users seek similar items within specific attribute ranges. Naive solutions like pre-filtering and post-filtering are straightforward but inefficient. Specialized indexes, such as SeRF, SuperPostFiltering, and iRangeGraph, have been developed to address these queries effectively. However, these solutions do not support dynamic updates, limiting their practicality in real-world scenarios where datasets frequently change.<\/jats:p>\n                  <jats:p>\n                    To address these challenges, we propose\n                    <jats:italic toggle=\"yes\">DIGRA,<\/jats:italic>\n                    a novel dynamic graph index for range-filtered ANNS.\n                    <jats:italic toggle=\"yes\">DIGRA<\/jats:italic>\n                    supports efficient dynamic updates while maintaining a balance among query efficiency, update efficiency, indexing cost, and result quality. Our approach introduces a dynamic multi-way tree structure combined with carefully integrated ANNS indices to handle range filtered ANNS efficiently. We employ a lazy weight-based update mechanism to significantly reduce update costs and adopt optimized choice of ANNS index to lower construction and update overhead. Experimental results demonstrate that DIGRA achieves superior trade-offs, making it suitable for large-scale dynamic datasets in real-world applications.\n                  <\/jats:p>","DOI":"10.1145\/3725399","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":12,"title":["DIGRA: A Dynamic Graph Indexing for Approximate Nearest Neighbor Search with Range Filter"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-5525-682X","authenticated-orcid":false,"given":"Mengxu","family":"Jiang","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-5931-4412","authenticated-orcid":false,"given":"Zhi","family":"Yang","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology, Wuhan, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-3253-4661","authenticated-orcid":false,"given":"Fangyuan","family":"Zhang","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, 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, Hong Kong"}],"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 Group, Hangzhou, 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 Group, Hangzhou, 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","unstructured":"2025. Code and technical report. https:\/\/github.com\/CUHK-DBGroup\/DIGRA."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327494"},{"key":"e_1_2_1_3_1","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."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/2856318.2856324"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970240481X"},{"key":"e_1_2_1_6_1","volume-title":"Lempitsky","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."},{"key":"e_1_2_1_7_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_8_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_9_1","doi-asserted-by":"crossref","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.","DOI":"10.1145\/997817.997857"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Hiroyuki Deguchi Taro Watanabe Yusuke Matsui Masao Utiyama Hideki Tanaka and Eiichiro Sumita. 2023. Subset Retrieval Nearest Neighbor Machine Translation. In ACL. 174--189.","DOI":"10.18653\/v1\/2023.acl-long.10"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Wei Dong Moses Charikar and Kai Li. 2011. Efficient k-nearest neighbor graph construction for generic similarity measures. In WWW. 577--586.","DOI":"10.1145\/1963405.1963487"},{"key":"e_1_2_1_12_1","unstructured":"Joshua Engels Benjamin Landrum Shangdi Yu Laxman Dhulipala and Julian Shun. 2024. Approximate nearest neighbor search with window filters. In ICML. Article 497 22 pages."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/3303753.3303754"},{"key":"e_1_2_1_14_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 Amit Singh and Harsha Vardhan Simhadri. 2023. Filtered-DiskANN: Graph Algorithms for Approximate Nearest Neighbor Search with Filters. In WWW. 3406--3416.","DOI":"10.1145\/3543507.3583552"},{"key":"e_1_2_1_15_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_16_1","doi-asserted-by":"crossref","unstructured":"Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable Feature Learning for Networks. In SIGKDD. 855--864.","DOI":"10.1145\/2939672.2939754"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Piotr Indyk and Rajeev Motwani. 1998. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. In STOC. 604--613.","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.57"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TBDATA.2019.2921572"},{"key":"e_1_2_1_20_1","unstructured":"Quoc Le and Tomas Mikolov. 2014. Distributed representations of sentences and documents. In ICML. 1188--1196."},{"key":"e_1_2_1_21_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_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.1016\/j.is.2013.10.006"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2018.2889473"},{"key":"e_1_2_1_25_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_26_1","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/2022.findings-acl.47"},{"key":"e_1_2_1_27_1","volume-title":"Distributed representations of words and phrases and their compositionality. NeurIPS 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 26 (2013)."},{"key":"e_1_2_1_28_1","unstructured":"James Jie Pan Jianguo Wang and Guoliang Li. 2023. Survey of vector database management systems. (2023)."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654923"},{"key":"e_1_2_1_30_1","volume-title":"First InternationalWorkshop on Similarity Search and Applications (sisap","author":"Patella Marco","year":"2008","unstructured":"Marco Patella and Paolo Ciaccia. 2008. The many facets of approximate similarity search. In First InternationalWorkshop on Similarity Search and Applications (sisap 2008). 10--21."},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","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.","DOI":"10.1109\/ICCV.2015.19"},{"key":"e_1_2_1_32_1","volume-title":"Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019","author":"Subramanya Suhas Jayaram","year":"2019","unstructured":"Suhas Jayaram Subramanya, Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnaswamy, and Rohan Kadekodi. 2019. Rand-NSG: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8--14, 2019, Vancouver, BC, Canada, Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d'Alch\u00e9-Buc, Emily B. Fox, and Roman Garnett (Eds.). 13748--13758."},{"key":"e_1_2_1_33_1","volume-title":"Milvus: A Purpose-Built Vector Data Management System. In SIGMOD. 2614--2627.","author":"Yi Xiaomeng","year":"2021","unstructured":"JianguoWang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, XiangyuWang, 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. 2021. Milvus: A Purpose-Built Vector Data Management System. In SIGMOD. 2614--2627."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476255"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/3415478.3415541"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3665844.3665854"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Paul Wohlhart and Vincent Lepetit. 2015. Learning descriptors for object recognition and 3D pose estimation. In CVPR. 3109--3118.","DOI":"10.1109\/CVPR.2015.7298930"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3698814"},{"key":"e_1_2_1_39_1","volume-title":"VBASE: Unifying Online Vector Similarity Search and Relational Queries via Relaxed Monotonicity. In OSDI. 377--395.","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."},{"key":"e_1_2_1_40_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\/3725399","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:54:19Z","timestamp":1774983259000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725399"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,17]]},"references-count":40,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6,17]]}},"alternative-id":["10.1145\/3725399"],"URL":"https:\/\/doi.org\/10.1145\/3725399","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,17]]}}}