{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T19:02:45Z","timestamp":1774983765600,"version":"3.50.1"},"reference-count":114,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2025,2,10]],"date-time":"2025-02-10T00:00:00Z","timestamp":1739145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-sa\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100006374","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62202450"],"award-info":[{"award-number":["62202450"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Guangdong Provincial Key Laboratory of Mathematical Foundations for Artificial Intelligence","award":["2023B1212010001"],"award-info":[{"award-number":["2023B1212010001"]}]},{"name":"EU Horizon projects AI4Europe","award":["101070000"],"award-info":[{"award-number":["101070000"]}]},{"name":"TwinODIS","award":["101160009"],"award-info":[{"award-number":["101160009"]}]},{"name":"ARMADA","award":["101168951"],"award-info":[{"award-number":["101168951"]}]},{"name":"DataGEMS","award":["101188416"],"award-info":[{"award-number":["101188416"]}]},{"name":"RECITALS","award":["101168490"],"award-info":[{"award-number":["101168490"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,2,10]]},"abstract":"<jats:p>Approximate Nearest Neighbor (ANN) search in high-dimensional Euclidean spaces is a fundamental problem with a wide range of applications. However, there is currently no ANN method that performs well in both indexing and query answering performance, while providing rigorous theoretical guarantees for the quality of the answers. In this paper, we first design SC-score, a metric that we show follows the Pareto principle and can act as a proxy for the Euclidean distance between data points. Inspired by this, we propose a novel ANN search framework called Subspace Collision (SC), which can provide theoretical guarantees on the quality of its results. We further propose SuCo, which achieves efficient and accurate ANN search by designing a clustering-based lightweight index and query strategies for our proposed subspace collision framework. Extensive experiments on real-world datasets demonstrate that both the indexing and query answering performance of SuCo outperform state-of-the-art ANN methods that can provide theoretical guarantees, performing 1-2 orders of magnitude faster query answering with only up to one-tenth of the index memory footprint. Moreover, SuCo achieves top performance (best for hard datasets) even when compared to methods that do not provide theoretical guarantees.<\/jats:p>","DOI":"10.1145\/3709729","type":"journal-article","created":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T15:45:06Z","timestamp":1739288706000},"page":"1-29","source":"Crossref","is-referenced-by-count":6,"title":["Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7300-4246","authenticated-orcid":false,"given":"Jiuqi","family":"Wei","sequence":"first","affiliation":[{"name":"Institute of Computing Technology Chinese Academy of Sciences, Beijing, China, &amp; University of Chinese Academy of Sciences, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1757-8365","authenticated-orcid":false,"given":"Xiaodong","family":"Lee","sequence":"additional","affiliation":[{"name":"Institute of Computing Technology Chinese Academy of Sciences, Beijing, China, &amp; Fuxi Institution, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1915-8559","authenticated-orcid":false,"given":"Zhenyu","family":"Liao","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology, Wuhan, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8031-0265","authenticated-orcid":false,"given":"Themis","family":"Palpanas","sequence":"additional","affiliation":[{"name":"LIPADE, Universit\u00e9 Paris Cit\u00e9, Paris, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2873-2452","authenticated-orcid":false,"given":"Botao","family":"Peng","sequence":"additional","affiliation":[{"name":"Institute of Computing Technology Chinese Academy of Sciences, Beijing, China"}]}],"member":"320","published-online":{"date-parts":[[2025,2,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1002\/0471722162.ch4"},{"key":"e_1_2_1_2_1","first-page":"33","article-title":"Expected Values and Moments. In Order Statistics. John Wiley & Sons, Ltd","volume":"3","year":"2003","unstructured":"2003. Expected Values and Moments. In Order Statistics. John Wiley & Sons, Ltd, Chapter 3, 33--58. doi:10.1002\/ 0471722162.ch3","journal-title":"Chapter"},{"key":"e_1_2_1_3_1","unstructured":"Alexandr Andoni. 2005. LSH Algorithm and Implementation (E2LSH). https:\/\/web.mit.edu\/andoni\/www\/LSH\/index. html."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746553"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2019.02.006"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/3583140.3583166"},{"key":"e_1_2_1_7_1","volume-title":"Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art. PACMMOD","author":"Azizi Ilias","year":"2025","unstructured":"Ilias Azizi, Karima Echihabi, and Themis Palpanas. 2025. Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art. PACMMOD (2025)."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2014.124"},{"key":"e_1_2_1_9_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 37, 6 (2014), 1247--1260."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2015.7299052"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2055--2063","author":"Babenko Artem","year":"2016","unstructured":"Artem Babenko and Victor Lempitsky. 2016. Efficient indexing of billion-scale datasets of deep descriptors. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2055--2063."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.3390\/e23101368"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718416"},{"key":"e_1_2_1_14_1","unstructured":"Erik Bernhardsson. 2015. Approximate Nearest Neighbors in C\/Python optimized for memory usage and loading\/saving to disk. https:\/\/github.com\/spotify\/annoy"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143857"},{"key":"e_1_2_1_16_1","volume-title":"Statistical Estimates and Transformed Beta-variables","author":"Blom Gunnar","unstructured":"Gunnar Blom. 1958. Statistical Estimates and Transformed Beta-variables. Wiley."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/357775.357776"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301330"},{"key":"e_1_2_1_19_1","volume-title":"Learning to prune in metric and non-metric spaces. Advances in Neural Information Processing Systems 26","author":"Boytsov Leonid","year":"2013","unstructured":"Leonid Boytsov and Bilegsaikhan Naidan. 2013. Learning to prune in metric and non-metric spaces. Advances in Neural Information Processing Systems 26 (2013)."},{"key":"e_1_2_1_20_1","volume-title":"Beyond one billion time series: indexing and mining very large time series collections with iSAX2. Knowledge and information systems 39, 1","author":"Camerra Alessandro","year":"2014","unstructured":"Alessandro Camerra, Jin Shieh, Themis Palpanas, Thanawin Rakthanmanon, and Eamonn Keogh. 2014. Beyond one billion time series: indexing and mining very large time series collections with iSAX2. Knowledge and information systems 39, 1 (2014), 123--151."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390156.1390171"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3579075.3579087"},{"key":"e_1_2_1_23_1","volume-title":"SPTAG: A library for fast approximate nearest neighbor search.","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."},{"key":"e_1_2_1_24_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 34 (2021), 5199--5212.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781009128490"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374452"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997857"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963487"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3547305.3547308"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3405962.3405989"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368303"},{"key":"e_1_2_1_32_1","volume-title":"FreSh: A Lock-Free Data Series Index. In 42nd International Symposium on Reliable Distributed Systems, SRDS. IEEE, 209--220","author":"Fatourou Panagiota","year":"2023","unstructured":"Panagiota Fatourou, Eleftherios Kosmas, Themis Palpanas, and George Paterakis. 2023. FreSh: A Lock-Free Data Series Index. In 42nd International Symposium on Reliable Distributed Systems, SRDS. IEEE, 209--220. doi:10.1109\/ SRDS60354.2023.00029"},{"key":"e_1_2_1_33_1","first-page":"4139","article-title":"High dimensional similarity search with satellite system graph: Efficiency, scalability, and unindexed query compatibility","volume":"44","author":"Fu Cong","year":"2021","unstructured":"Cong Fu, Changxu Wang, and Deng Cai. 2021. High dimensional similarity search with satellite system graph: Efficiency, scalability, and unindexed query compatibility. IEEE Transactions on Pattern Analysis and Machine Intelligence 44, 8 (2021), 4139--4150.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/3303753.3303754"},{"key":"e_1_2_1_35_1","volume-title":"Narendra","author":"Fukunaga Keinosuke","year":"1975","unstructured":"Keinosuke Fukunaga and Patrenahalli M. Narendra. 1975. A branch and bound algorithm for computing k-nearest neighbors. IEEE transactions on computers 100, 7 (1975), 750--753."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213898"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589282"},{"key":"e_1_2_1_38_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 36, 4 (2013), 744--755."},{"key":"e_1_2_1_39_1","first-page":"518","article-title":"Similarity search in high dimensions via hashing","volume":"99","author":"Gionis Aristides","year":"1999","unstructured":"Aristides Gionis, Piotr Indyk, Rajeev Motwani, et al. 1999. Similarity search in high dimensions via hashing. In Vldb, Vol. 99. 518--529.","journal-title":"Vldb"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/MASSP.1984.1162229"},{"key":"e_1_2_1_41_1","volume-title":"Neuhoff","author":"Gray Robert M.","year":"1998","unstructured":"Robert M. Gray and David L. Neuhoff. 1998. Quantization. IEEE transactions on information theory 44, 6 (1998), 2325--2383."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/645926.671675"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850469.2850470"},{"key":"e_1_2_1_44_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 32 (2019)."},{"key":"e_1_2_1_45_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 33, 1 (2010), 117--128."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.2011.5946540"},{"key":"e_1_2_1_47_1","volume-title":"Low bias local intrinsic dimension estimation from expected simplex skewness","author":"Johnsson Kerstin","year":"2014","unstructured":"Kerstin Johnsson, Charlotte Soneson, and Magnus Fontes. 2014. Low bias local intrinsic dimension estimation from expected simplex skewness. IEEE transactions on pattern analysis and machine intelligence 37, 1 (2014), 196--202."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2014.298"},{"key":"e_1_2_1_49_1","volume-title":"Dense passage retrieval for open-domain question answering. arXiv preprint arXiv:2004.04906","author":"Karpukhin Vladimir","year":"2020","unstructured":"Vladimir Karpukhin, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. 2020. Dense passage retrieval for open-domain question answering. arXiv preprint arXiv:2004.04906 (2020)."},{"key":"e_1_2_1_50_1","volume-title":"Proceedings of the VLDB Endowment 11","author":"Kondylakis Haridimos","year":"2018","unstructured":"Haridimos Kondylakis, Niv Dayan, Kostas Zoumpatianos, and Themis Palpanas. 2018. Coconut: A Scalable Bottom-Up Approach for Building Data Series Indexes. Proceedings of the VLDB Endowment 11, 6 (2018)."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00573-w"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389778"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00032"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2909204"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2024.110774"},{"key":"e_1_2_1_56_1","volume-title":"Mahoney","author":"Liao Zhenyu","year":"2020","unstructured":"Zhenyu Liao, Romain Couillet, and Michael W. Mahoney. 2020. A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian Kernel, a Precise Phase Transition, and the Corresponding Double Descent. In Advances in Neural Information Processing Systems, Vol. 33. Curran Associates, Inc., 13939-13950."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.14778\/3275366.3284968"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00619-4"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00635-4"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3132901"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732939.2732947"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1214\/17-aap1328"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00095"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.14778\/3489496.3489506"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397240"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2013.10.006"},{"key":"e_1_2_1_67_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 42, 4 (2018), 824--836."},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.3169\/mta.6.2"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2015.225"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2014.2321376"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2019.106970"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2302.11474"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780200060"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2013.388"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/2814710.2814719"},{"key":"e_1_2_1_76_1","volume-title":"Report on the First and Second Interdisciplinary Time Series Analysis Workshop (ITISA). SIGREC (48(3)","author":"Palpanas Themis","year":"2019","unstructured":"Themis Palpanas and Volker Beckmann. 48(3), 2019. Report on the First and Second Interdisciplinary Time Series Analysis Workshop (ITISA). SIGREC (48(3), 2019)."},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1109\/SISAP.2008.18"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2008.09.014"},{"key":"e_1_2_1_79_1","volume-title":"ParIS: The Next Destination for Fast Data Series Indexing and Query Answering","author":"Peng Botao","year":"2018","unstructured":"Botao Peng, Panagiota Fatourou, and Themis Palpanas. 2018. ParIS: The Next Destination for Fast Data Series Indexing and Query Answering. IEEE BigData (2018)."},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00036"},{"key":"e_1_2_1_81_1","first-page":"2151","article-title":"Paris: Data series indexing on multi-core architectures","volume":"33","author":"Peng Botao","year":"2020","unstructured":"Botao Peng, Panagiota Fatourou, and Themis Palpanas. 2020. Paris: Data series indexing on multi-core architectures. IEEE Transactions on Knowledge and Data Engineering 33, 5 (2020), 2151--2164.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00677-2"},{"key":"e_1_2_1_83_1","volume-title":"SING: Sequence Indexing Using GPUs. In 2021 IEEE 37th International Conference on Data Engineering (ICDE). IEEE","author":"Peng Botao","year":"2021","unstructured":"Botao Peng, Panagiota Fatourou, and Themis Palpanas. 2021. SING: Sequence Indexing Using GPUs. In 2021 IEEE 37th International Conference on Data Engineering (ICDE). IEEE, 1883--1888."},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588908"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72079-9_9"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2008.4587638"},{"key":"e_1_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735461.2735462"},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3097987"},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559905"},{"key":"e_1_2_1_90_1","volume-title":"Approximate Nearest Neighbor Search in High Dimensional Vector Databases: Current Research and Future Directions","author":"Tian Yao","year":"2023","unstructured":"Yao Tian, Ziyang Yue, Ruiyuan Zhang, Xi Zhao, Bolong Zheng, and Xiaofang Zhou. 2023. Approximate Nearest Neighbor Search in High Dimensional Vector Databases: Current Research and Future Directions. IEEE Data Engineering Bulletin 47, 3 (2023)."},{"key":"e_1_2_1_91_1","volume-title":"Locality-Sensitive Hashing With Query-Based Dynamic Bucketing","author":"Tian Yao","year":"2023","unstructured":"Yao Tian, Xi Zhao, and Xiaofang Zhou. 2023. DB-LSH 2.0: Locality-Sensitive Hashing With Query-Based Dynamic Bucketing. IEEE Transactions on Knowledge and Data Engineering (2023)."},{"key":"e_1_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476255"},{"key":"e_1_2_1_93_1","doi-asserted-by":"publisher","DOI":"10.1145\/3709701"},{"key":"e_1_2_1_94_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467317"},{"key":"e_1_2_1_95_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3270264"},{"key":"e_1_2_1_96_1","volume-title":"A data-adaptive and dynamic segmentation index for whole matching on time series. VLDB","author":"Wang Yang","year":"2013","unstructured":"Yang Wang, Peng Wang, Jian Pei, Wei Wang, and Sheng Huang. 2013. A data-adaptive and dynamic segmentation index for whole matching on time series. VLDB (2013)."},{"key":"e_1_2_1_97_1","first-page":"3","article-title":"Graph- and Tree-based Indexes for High-dimensional Vector Similarity Search: Analyses, Comparisons, and Future Directions","volume":"47","author":"Palpanas Themis","year":"2023","unstructured":"ZeyuWang, PengWang, Themis Palpanas, andWeiWang. 2023. Graph- and Tree-based Indexes for High-dimensional Vector Similarity Search: Analyses, Comparisons, and Future Directions. IEEE Data Eng. Bull. 47, 3 (2023), 3--21.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_98_1","volume-title":"-Hardness: A Query Hardness Measure for Graph-Based ANN Indexes. PVLDB","author":"Wang Zeyu","year":"2024","unstructured":"Zeyu Wang, Qitong Wang, Xiaoxing Cheng, Peng Wang, Themis Palpanas, and Wei Wang. 2024. -Hardness: A Query Hardness Measure for Graph-Based ANN Indexes. PVLDB (2024)."},{"key":"e_1_2_1_99_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588965"},{"key":"e_1_2_1_100_1","volume-title":"DumpyOS: A data-adaptive multi-ary index for scalable data series similarity search. The VLDB Journal","author":"Wang Zeyu","year":"2024","unstructured":"Zeyu Wang, Qitong Wang, Peng Wang, Themis Palpanas, and Wei Wang. 2024. DumpyOS: A data-adaptive multi-ary index for scalable data series similarity search. The VLDB Journal (2024), 1--25."},{"key":"e_1_2_1_101_1","first-page":"194","article-title":"A quantitative analysis and performance study for similaritysearch methods in high-dimensional spaces","volume":"98","author":"Schek Hans-J\u00f6rg","year":"1998","unstructured":"RogerWeber, Hans-J\u00f6rg Schek, and Stephen Blott. 1998. A quantitative analysis and performance study for similaritysearch methods in high-dimensional spaces. In VLDB, Vol. 98. 194--205.","journal-title":"VLDB"},{"key":"e_1_2_1_102_1","volume-title":"Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search. https:\/\/github.com\/WeiJiuQi\/SuCo.","year":"2024","unstructured":"JiuqiWei. 2024. Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search. https:\/\/github.com\/WeiJiuQi\/SuCo."},{"key":"e_1_2_1_103_1","volume-title":"Data Interoperating Architecture (DIA): Decoupling Data and Applications to Give Back Your Data Ownership. In 2023 IEEE 47th Annual Computers, Software, and Applications Conference (COMPSAC)","author":"Li Ying","unstructured":"JiuqiWei, Ying Li, Yufan Fu, Youyi Zhang, and Xiaodong Li. 2023. Data Interoperating Architecture (DIA): Decoupling Data and Applications to Give Back Your Data Ownership. In 2023 IEEE 47th Annual Computers, Software, and Applications Conference (COMPSAC). IEEE, 438--447."},{"key":"e_1_2_1_104_1","doi-asserted-by":"publisher","DOI":"10.14778\/3665844.3665854"},{"key":"e_1_2_1_105_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2013.424"},{"key":"e_1_2_1_106_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2017.151"},{"key":"e_1_2_1_107_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2880215"},{"key":"e_1_2_1_108_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_1_109_1","volume-title":"International Conference on Machine Learning. PMLR, 838--846","author":"Zhang Ting","year":"2014","unstructured":"Ting Zhang, Chao Du, and Jingdong Wang. 2014. Composite quantization for approximate nearest neighbor search. In International Conference on Machine Learning. PMLR, 838--846."},{"key":"e_1_2_1_110_1","doi-asserted-by":"publisher","DOI":"10.14778\/3594512.3594527"},{"key":"e_1_2_1_111_1","doi-asserted-by":"publisher","DOI":"10.14778\/3377369.3377374"},{"key":"e_1_2_1_112_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882930"},{"key":"e_1_2_1_113_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610498"},{"key":"e_1_2_1_114_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0442-5"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3709729","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3709729","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:23:27Z","timestamp":1774981407000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3709729"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,10]]},"references-count":114,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,2,10]]}},"alternative-id":["10.1145\/3709729"],"URL":"https:\/\/doi.org\/10.1145\/3709729","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,10]]}}}