{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T13:09:24Z","timestamp":1775912964431,"version":"3.50.1"},"reference-count":89,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2024,12,18]],"date-time":"2024-12-18T00:00:00Z","timestamp":1734480000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001459","name":"Ministry of Education, Singapore","doi-asserted-by":"crossref","award":["Tier 2 Award MOE-T2EP20221-0013, Tier 2 Award MOE-T2EP20220-0011, and Tier 1 Award (RG77\/21)"],"award-info":[{"award-number":["Tier 2 Award MOE-T2EP20221-0013, Tier 2 Award MOE-T2EP20220-0011, and Tier 1 Award (RG77\/21)"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Innovation Fund Denmark centre, DIREC"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,12,18]]},"abstract":"<jats:p>\n                    Range-filtering approximate nearest neighbor (RFANN) search is attracting increasing attention in academia and industry. Given a set of data objects, each being a pair of a high-dimensional vector and a numeric value, an RFANN query with a vector and a numeric range as parameters returns the data object whose numeric value is in the query range and whose vector is nearest to the query vector. To process this query, a recent study proposes to build\n                    <jats:italic toggle=\"yes\">O(n<\/jats:italic>\n                    <jats:sup>2<\/jats:sup>\n                    ) dedicated graph-based indexes for all possible query ranges to enable efficient processing on a database of\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    objects. As storing all these indexes is prohibitively expensive, the study constructs compressed indexes instead, which reduces the memory consumption considerably. However, this incurs suboptimal performance because the compression is lossy. In this study, instead of materializing a compressed index for every possible query range in preparation for querying, we materialize graph-based indexes, called elemental graphs, for a moderate number of ranges. We then provide an effective and efficient algorithm that during querying can construct an index for any query range using the elemental graphs. We prove that the time needed to construct such an index is low. We also cover an experimental study on real-world datasets that provides evidence that the materialized elemental graphs only consume moderate space and that the proposed method is capable of superior and stable query performance across different query workloads.\n                  <\/jats:p>","DOI":"10.1145\/3698814","type":"journal-article","created":{"date-parts":[[2024,12,20]],"date-time":"2024-12-20T16:40:35Z","timestamp":1734712835000},"page":"1-26","source":"Crossref","is-referenced-by-count":12,"title":["iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-2354-9323","authenticated-orcid":false,"given":"Yuexuan","family":"Xu","sequence":"first","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-4684-3624","authenticated-orcid":false,"given":"Jianyang","family":"Gao","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-7005-6463","authenticated-orcid":false,"given":"Yutong","family":"Gou","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6806-8405","authenticated-orcid":false,"given":"Cheng","family":"Long","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9697-7670","authenticated-orcid":false,"given":"Christian S.","family":"Jensen","sequence":"additional","affiliation":[{"name":"Aalborg University, Aalborg, Denmark"}]}],"member":"320","published-online":{"date-parts":[[2024,12,20]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"42nd International Conference on Very Large Data Bases","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 42nd International Conference on Very Large Data Bases, Vol. 9. 12."},{"key":"e_1_2_2_2_1","volume-title":"SODA","volume":"93","author":"Arya Sunil","year":"1993","unstructured":"Sunil Arya and David M Mount. 1993. Approximate nearest neighbor queries in fixed dimensions.. In SODA, Vol. 93. Citeseer, 271--280."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2019.02.006"},{"key":"e_1_2_2_4_1","volume-title":"Recent Approaches and Trends in Approximate Nearest Neighbor Search, with Remarks on Benchmarking. Data Engineering","author":"Aum\u00fcller Martin","year":"2023","unstructured":"Martin Aum\u00fcller and Matteo Ceccarello. 2023. Recent Approaches and Trends in Approximate Nearest Neighbor Search, with Remarks on Benchmarking. Data Engineering (2023), 89."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2014.124"},{"key":"e_1_2_2_6_1","volume-title":"The inverted multi-index","author":"Babenko Artem","year":"2014","unstructured":"Artem Babenko and Victor Lempitsky. 2014. The inverted multi-index. IEEE transactions on pattern analysis and machine intelligence, Vol. 37, 6 (2014), 1247--1260."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-58094-8_18"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143857"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/362003.362025"},{"key":"e_1_2_2_10_1","volume-title":"Diego Reforgiato Recupero, and Dennis Shasha","author":"Cantone Domenico","year":"2005","unstructured":"Domenico Cantone, Alfredo Ferro, Alfredo Pulvirenti, Diego Reforgiato Recupero, and Dennis Shasha. 2005. Antipole tree indexing to support range search and k-nearest neighbor search in metric spaces. IEEE transactions on knowledge and data engineering, Vol. 17, 4 (2005), 535--550."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/11795490_19"},{"key":"e_1_2_2_12_1","volume-title":"Faster Proximity Searching with the Distal SAT. In Similarity Search and Applications: 7th International Conference, SISAP 2014, Los Cabos, Mexico, October 29--31, 2104, Proceedings","volume":"8821","author":"Ch\u00e1vez Edgar","year":"2014","unstructured":"Edgar Ch\u00e1vez, Ver\u00f3nica Luduena, Nora Reyes, and Patricia Roggero. 2014. Faster Proximity Searching with the Distal SAT. In Similarity Search and Applications: 7th International Conference, SISAP 2014, Los Cabos, Mexico, October 29--31, 2104, Proceedings, Vol. 8821. Springer, 58."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2015.10.014"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00344-7"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2506556"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3530812"},{"key":"e_1_2_2_17_1","volume-title":"SPTAG: A library for fast approximate nearest neighbor search. https:\/\/github.com\/Microsoft\/SPTAG","author":"Chen Qi","year":"2018","unstructured":"Qi Chen, Haidong Wang, Mingqin Li, Gang Ren, Scarlett Li, Jeffery Zhu, Jason Li, Chuanjie Liu, Lintao Zhang, and Jingdong Wang. 2018. SPTAG: A library for fast approximate nearest neighbor search. https:\/\/github.com\/Microsoft\/SPTAG"},{"key":"e_1_2_2_18_1","first-page":"5199","article-title":"Spann: Highly-efficient billion-scale approximate nearest neighborhood search","volume":"34","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. Advances in Neural Information Processing Systems, Vol. 34 (2021), 5199--5212.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_2_19_1","volume-title":"Proceedings of the 9th Australasian Database Conference (ADC'98)","author":"Ciaccia Paolo","year":"1998","unstructured":"Paolo Ciaccia and Marco Patella. 1998. Bulk loading the M-tree. In Proceedings of the 9th Australasian Database Conference (ADC'98). Citeseer, 15--26."},{"key":"e_1_2_2_20_1","volume-title":"Approximate similarity queries: A survey","author":"Ciaccia Paolo","year":"2001","unstructured":"Paolo Ciaccia and Marco Patella. 2001. Approximate similarity queries: A survey. University of Bolognia: Bologna, Italy (2001)."},{"key":"e_1_2_2_21_1","volume-title":"Proceedings of the 23rd International Conference on Very Large Data Bases (VLDB '97)","author":"Ciaccia Paolo","year":"1997","unstructured":"Paolo Ciaccia, Marco Patella, and Pavel Zezula. 1997. M-tree: An Efficient Access Method for Similarity Search in Metric Spaces. In Proceedings of the 23rd International Conference on Very Large Data Bases (VLDB '97). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 426--435."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258655"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997857"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04245-8"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0306-4379(87)90041-X"},{"key":"e_1_2_2_26_1","volume-title":"Harsha Vardhan Simhadri, and Yihan Sun","author":"Dobson Magdalen","year":"2023","unstructured":"Magdalen Dobson, Zheqi Shen, Guy E Blelloch, Laxman Dhulipala, Yan Gu, Harsha Vardhan Simhadri, and Yihan Sun. 2023. Scaling Graph-Based ANNS Algorithms to Billion-Size Datasets: A Comparative Analysis. arXiv preprint arXiv:2305.04359 (2023)."},{"key":"e_1_2_2_27_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_2_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476311.3476407"},{"key":"e_1_2_2_29_1","volume-title":"Approximate Nearest Neighbor Search with Window Filters. arXiv preprint arXiv:2402.00943","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. arXiv preprint arXiv:2402.00943 (2024)."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223812"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-47724-1_14"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85654-2_7"},{"key":"e_1_2_2_33_1","volume-title":"Generalized Relative Neighborhood Graph (GRNG) for Similarity Search. In International Conference on Similarity Search and Applications. Springer, 133--149","author":"Foster Cole","year":"2022","unstructured":"Cole Foster, Berk Sevilmis, and Benjamin Kimia. 2022. Generalized Relative Neighborhood Graph (GRNG) for Similarity Search. In International Conference on Similarity Search and Applications. Springer, 133--149."},{"key":"e_1_2_2_34_1","volume-title":"Efanna: An extremely fast approximate nearest neighbor search algorithm based on knn graph. arXiv preprint arXiv:1609.07228","author":"Fu Cong","year":"2016","unstructured":"Cong Fu and Deng Cai. 2016. Efanna: An extremely fast approximate nearest neighbor search algorithm based on knn graph. arXiv preprint arXiv:1609.07228 (2016)."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2021.3067706"},{"key":"e_1_2_2_36_1","volume-title":"Fast approximate nearest neighbor search with the navigating spreading-out graph. arXiv preprint arXiv:1707.00143","author":"Fu Cong","year":"2017","unstructured":"Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2017. Fast approximate nearest neighbor search with the navigating spreading-out graph. arXiv preprint arXiv:1707.00143 (2017)."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213898"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589282"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654970"},{"key":"e_1_2_2_40_1","volume-title":"Optimized product quantization","author":"Ge Tiezheng","year":"2013","unstructured":"Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. 2013. Optimized product quantization. IEEE transactions on pattern analysis and machine intelligence, Vol. 36, 4 (2013), 744--755."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3543507.3583552"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490148.3538581"},{"key":"e_1_2_2_43_1","volume-title":"International Conference on Machine Learning. PMLR, 3887--3896","author":"Guo Ruiqi","year":"2020","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 International Conference on Machine Learning. PMLR, 3887--3896."},{"key":"e_1_2_2_44_1","volume-title":"CAPS: A Practical Partition Index for Filtered Similarity Search. arXiv preprint arXiv:2308.15014","author":"Gupta Gaurav","year":"2023","unstructured":"Gaurav Gupta, Jonah Yi, Benjamin Coleman, Chen Luo, Vihan Lakshman, and Anshumali Shrivastava. 2023. CAPS: A Practical Partition Index for Filtered Similarity Search. arXiv preprint arXiv:2308.15014 (2023)."},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2016.616"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/958942.958948"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850469.2850470"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_2_49_1","doi-asserted-by":"crossref","unstructured":"Piotr Indyk and Haike Xu. 2023. Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations. In Thirty-seventh Conference on Neural Information Processing Systems. https:\/\/openreview.net\/forum?id=oKqaWlEfjY","DOI":"10.52202\/075280-2891"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-46759-7_2"},{"key":"e_1_2_2_51_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. Advances in Neural Information Processing Systems, Vol. 32 (2019)."},{"key":"e_1_2_2_52_1","volume-title":"Product quantization for nearest neighbor search","author":"Jegou Herve","year":"2010","unstructured":"Herve Jegou, Matthijs Douze, and Cordelia Schmid. 2010. Product quantization for nearest neighbor search. IEEE transactions on pattern analysis and machine intelligence, Vol. 33, 1 (2010), 117--128."},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1983.235263"},{"key":"e_1_2_2_54_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, Vol. 33 (2020), 9459--9474.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3284028.3284030"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2909204"},{"key":"e_1_2_2_57_1","volume-title":"A survey of content-based image retrieval with high-level semantics. Pattern recognition","author":"Liu Ying","year":"2007","unstructured":"Ying Liu, Dengsheng Zhang, Guojun Lu, and Wei-Ying Ma. 2007. A survey of content-based image retrieval with high-level semantics. Pattern recognition, Vol. 40, 1 (2007), 262--282."},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2013.10.006"},{"key":"e_1_2_2_59_1","volume-title":"Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs","author":"Malkov Yu A","year":"2018","unstructured":"Yu A Malkov and Dmitry A Yashunin. 2018. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence, Vol. 42, 4 (2018), 824--836."},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3240508.3240630"},{"key":"e_1_2_2_61_1","unstructured":"Microsoft. 2024. https:\/\/github.com\/microsoft\/DiskANN."},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589777"},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/1995412.1995418"},{"key":"e_1_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780200060"},{"key":"e_1_2_2_65_1","volume-title":"ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data. arXiv preprint arXiv:2403.04871","author":"Patel Liana","year":"2024","unstructured":"Liana Patel, Peter Kraft, Carlos Guestrin, and Matei Zaharia. 2024. ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data. arXiv preprint arXiv:2403.04871 (2024)."},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1109\/SISAP.2008.18"},{"key":"e_1_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2008.09.014"},{"key":"e_1_2_2_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3470811"},{"key":"e_1_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188916"},{"key":"e_1_2_2_70_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8655(86)90013-9"},{"key":"e_1_2_2_71_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735461.2735462"},{"key":"e_1_2_2_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806907.1806912"},{"key":"e_1_2_2_73_1","volume-title":"The relative neighbourhood graph of a finite planar set. Pattern recognition","author":"Toussaint Godfried T","year":"1980","unstructured":"Godfried T Toussaint. 1980. The relative neighbourhood graph of a finite planar set. Pattern recognition, Vol. 12, 4 (1980), 261--268."},{"key":"e_1_2_2_74_1","volume-title":"Satisfying general proximity\/similarity queries with metric trees. Information processing letters","author":"Uhlmann Jeffrey K","year":"1991","unstructured":"Jeffrey K Uhlmann. 1991. Satisfying general proximity\/similarity queries with metric trees. Information processing letters, Vol. 40, 4 (1991), 175--179."},{"key":"e_1_2_2_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457550"},{"key":"e_1_2_2_76_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSMCB.2005.848489"},{"key":"e_1_2_2_77_1","volume-title":"Advances in Neural Information Processing Systems","volume":"36","author":"Wang Mengzhao","year":"2024","unstructured":"Mengzhao Wang, Lingwei Lv, Xiaoliang Xu, Yuxiang Wang, Qiang Yue, and Jiongkang Ni. 2024. An efficient and robust framework for approximate nearest neighbor search with attribute constraint. Advances in Neural Information Processing Systems, Vol. 36 (2024)."},{"key":"e_1_2_2_78_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476255"},{"key":"e_1_2_2_79_1","volume-title":"A Survey on Efficient Processing of Similarity Queries over Neural Embeddings. arXiv preprint arXiv:2204.07922","author":"Wang Yifan","year":"2022","unstructured":"Yifan Wang. 2022. A Survey on Efficient Processing of Similarity Queries over Neural Embeddings. arXiv preprint arXiv:2204.07922 (2022)."},{"key":"e_1_2_2_80_1","volume-title":"Graph-and Tree-based Indexes for High-dimensional Vector Similarity Search: Analyses, Comparisons, and Future Directions. Data Engineering","author":"Wang Zeyu","year":"2023","unstructured":"Zeyu Wang, Peng Wang, Themis Palpanas, and Wei Wang. 2023. Graph-and Tree-based Indexes for High-dimensional Vector Similarity Search: Analyses, Comparisons, and Future Directions. Data Engineering (2023), 3--21."},{"key":"e_1_2_2_81_1","doi-asserted-by":"publisher","DOI":"10.14778\/3415478.3415541"},{"key":"e_1_2_2_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/3511808.3557610"},{"key":"e_1_2_2_83_1","doi-asserted-by":"crossref","unstructured":"Yuexuan Xu Jianyang Gao Yutong Gou Cheng Long and Christian S. Jensen. 2025. iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search (Technical Report). https:\/\/github.com\/YuexuanXu7\/iRangeGraph.","DOI":"10.1145\/3698814"},{"key":"e_1_2_2_84_1","first-page":"311","article-title":"Data structures and algorithms for nearest neighbor search in general metric spaces","volume":"93","author":"Yianilos Peter N","year":"1993","unstructured":"Peter N Yianilos. 1993. Data structures and algorithms for nearest neighbor search in general metric spaces. In Soda, Vol. 93. 311--21.","journal-title":"Soda"},{"key":"e_1_2_2_85_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780050069"},{"key":"e_1_2_2_86_1","volume-title":"17th USENIX Symposium on Operating Systems Design and Implementation (OSDI 23)","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 17th USENIX Symposium on Operating Systems Design and Implementation (OSDI 23). USENIX Association, Boston, MA, 377--395. https:\/\/www.usenix.org\/conference\/osdi23\/presentation\/zhang-qianxi"},{"key":"e_1_2_2_87_1","volume-title":"Constrained Approximate Similarity Search on Proximity Graph. arXiv preprint arXiv:2210.14958","author":"Zhao Weijie","year":"2022","unstructured":"Weijie Zhao, Shulong Tan, and Ping Li. 2022. Constrained Approximate Similarity Search on Proximity Graph. arXiv preprint arXiv:2210.14958 (2022)."},{"key":"e_1_2_2_88_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00691-4"},{"key":"e_1_2_2_89_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\/10.1145\/3698814","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3698814","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T17:45:55Z","timestamp":1774979155000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3698814"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,18]]},"references-count":89,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,12,18]]}},"alternative-id":["10.1145\/3698814"],"URL":"https:\/\/doi.org\/10.1145\/3698814","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,18]]}}}