{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:13:37Z","timestamp":1779174817131,"version":"3.51.4"},"reference-count":124,"publisher":"Association for Computing Machinery (ACM)","issue":"13","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,9]]},"abstract":"<jats:p>\n            Graph-based indexes have been widely employed to accelerate approximate similarity search of high-dimensional vectors. However, the performance of graph indexes to answer different queries varies vastly, leading to an unstable quality of service for downstream applications. This necessitates an effective measure to test query hardness on graph indexes. Nonetheless, popular distance-based hardness measures like LID lose their effects due to the ignorance of the graph structure. In this paper, we propose\n            <jats:italic>Steiner<\/jats:italic>\n            -hardness, a novel connection-based graph-native query hardness measure. Specifically, we first propose a theoretical framework to analyze the minimum query effort on graph indexes and then define\n            <jats:italic>Steiner<\/jats:italic>\n            -hardness as the minimum effort on a representative graph. Moreover, we prove that our\n            <jats:italic>Steiner<\/jats:italic>\n            -hardness is highly relevant to the classical Directed\n            <jats:italic>Steiner<\/jats:italic>\n            Tree (DST) problems. In this case, we design a novel algorithm to reduce our problem to DST problems and then leverage their solvers to help calculate\n            <jats:italic>Steiner<\/jats:italic>\n            -hardness efficiently. Compared with LID and other similar measures,\n            <jats:italic>Steiner<\/jats:italic>\n            -hardness shows a significantly better correlation with the actual query effort on various datasets. Additionally, an unbiased evaluation designed based on\n            <jats:italic>Steiner<\/jats:italic>\n            -hardness reveals new ranking results, indicating a meaningful direction for enhancing the robustness of graph indexes.\n          <\/jats:p>","DOI":"10.14778\/3704965.3704974","type":"journal-article","created":{"date-parts":[[2025,2,18]],"date-time":"2025-02-18T17:22:57Z","timestamp":1739899377000},"page":"4668-4682","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["<i>Steiner<\/i>\n            -Hardness: A Query Hardness Measure for Graph-Based ANN Indexes"],"prefix":"10.14778","volume":"17","author":[{"given":"Zeyu","family":"Wang","sequence":"first","affiliation":[{"name":"Fudan University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qitong","family":"Wang","sequence":"additional","affiliation":[{"name":"LIPADE, Universit\u00e9 Paris Cit\u00e9"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaoxing","family":"Cheng","sequence":"additional","affiliation":[{"name":"Tongji University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peng","family":"Wang","sequence":"additional","affiliation":[{"name":"Fudan University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Themis","family":"Palpanas","sequence":"additional","affiliation":[{"name":"LIPADE, Universit\u00e9 Paris Cit\u00e9"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wei","family":"Wang","sequence":"additional","affiliation":[{"name":"Fudan University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,2,18]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2018. PACE (Parameterized Algorithms and Computational Experiments) 2018-Steiner Tree. https:\/\/pacechallenge.org\/2018\/steiner-tree\/. Accessed on January 30 2024."},{"key":"e_1_2_1_2_1","volume-title":"Dijkstra's algorithm. https:\/\/en.wikipedia.org\/w\/index.php?title=Dijkstra%27s_algorithm&oldid=1189493285 [Online","year":"2024","unstructured":"2023. Dijkstra's algorithm. https:\/\/en.wikipedia.org\/w\/index.php?title=Dijkstra%27s_algorithm&oldid=1189493285 [Online; accessed 11-January-2024]."},{"key":"e_1_2_1_3_1","volume-title":"Mixture model. https:\/\/en.wikipedia.org\/w\/index.php?title=Mixture_model&oldid=1166525726. [Online","year":"2024","unstructured":"2023. Mixture model. https:\/\/en.wikipedia.org\/w\/index.php?title=Mixture_model&oldid=1166525726. [Online; accessed 7-January-2024]."},{"key":"e_1_2_1_4_1","volume-title":"The Free Encyclopedia. https:\/\/en.wikipedia.org\/w\/index.php?title=Box_plot&oldid=1225026016. [Online","year":"2024","unstructured":"2024. Box plot --- Wikipedia, The Free Encyclopedia. https:\/\/en.wikipedia.org\/w\/index.php?title=Box_plot&oldid=1225026016. [Online; accessed 1-June-2024]."},{"key":"e_1_2_1_5_1","volume-title":"Mahalanobis distance. https:\/\/en.wikipedia.org\/w\/index.php?title=Mahalanobis_distance&oldid=1193836393 [Online","year":"2024","unstructured":"2024. Mahalanobis distance. https:\/\/en.wikipedia.org\/w\/index.php?title=Mahalanobis_distance&oldid=1193836393 [Online; accessed 12-January-2024]."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","unstructured":"Thomas D. Ahle Martin Aum\u00fcller and Rasmus Pagh. [n.d.]. Parameter-free Locality Sensitive Hashing for Spherical Range Reporting. 239--256. 10.1137\/1.9781611974782.16","DOI":"10.1137\/1.9781611974782.16"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783405"},{"key":"e_1_2_1_8_1","unstructured":"Laurent Amsaleg and J\u00e9gou Herv\u00e9. [n.d.]. Evaluation of Approximate nearest neighbors: large datasets. http:\/\/corpus-texmex.irisa.fr\/ [Online; accessed 15-May-2024]."},{"key":"e_1_2_1_9_1","volume-title":"HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces. PVLDB 11, 8","author":"Arora Akhil","year":"2018","unstructured":"Akhil Arora, Sakshi Sinha, Piyush Kumar, and Arnab Bhattacharya. 2018. HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces. PVLDB 11, 8 (2018)."},{"key":"e_1_2_1_10_1","first-page":"89","article-title":"Recent Approaches and Trends in Approximate Nearest Neighbor Search, with Remarks on Benchmarking","volume":"46","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. IEEE Data Eng. Bull. 46, 3 (2023), 89--105.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2019.02.006"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2021.101807"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/3583140.3583166"},{"key":"e_1_2_1_14_1","volume-title":"Benchmarks for Billion-Scale Similarity Search. https:\/\/research.yandex.com\/blog\/benchmarks-for-billion-scale-similarity-search [Online","author":"Baranchuk Dmitry","year":"2024","unstructured":"Dmitry Baranchuk and Artem Babenko. [n.d.]. Benchmarks for Billion-Scale Similarity Search. https:\/\/research.yandex.com\/blog\/benchmarks-for-billion-scale-similarity-search [Online; accessed 15-May-2024]."},{"key":"e_1_2_1_15_1","volume-title":"https:\/\/github.com\/spotify\/. [Online","author":"Bernhardsson Eric","year":"2024","unstructured":"Eric Bernhardsson. [n.d.]. Annoy. https:\/\/github.com\/spotify\/. [Online; accessed 7-January-2024]."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1042"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3579075.3579087"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Lu Chen Yunjun Gao Xinhan Li Christian S Jensen and Gang Chen. 2015. Efficient metric indexing for similarity search. In ICDE. 591--602.","DOI":"10.1109\/ICDE.2015.7113317"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3115404.3115411"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3543507.3583318"},{"key":"e_1_2_1_21_1","volume-title":"Advances in Neural Information Processing Systems","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. In Advances in Neural Information Processing Systems, Vol. 34. Curran Associates, Inc., 5199--5212."},{"key":"e_1_2_1_22_1","volume-title":"GQR: A General and Efficient Querying Method for Learning to Hash. https:\/\/www.cse.cuhk.edu.hk\/systems\/hash\/gqr\/datasets.html [Online","author":"Cheng James","year":"2024","unstructured":"James Cheng, Xinyan Dai, Bao Ergute, Ti-chung Cheng, Haopeng Sun, Bin Hu, Xiao Yan, Jinfei Li, and Jie Liu. [n.d.]. GQR: A General and Efficient Querying Method for Learning to Hash. https:\/\/www.cse.cuhk.edu.hk\/systems\/hash\/gqr\/datasets.html [Online; accessed 15-May-2024]."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3381451"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3381451"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374452"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACSSC.1988.754602"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACSSC.1988.754602"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3077581"},{"key":"e_1_2_1_29_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:2305.04359 [cs.IR]"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963487"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/3503585.3503594"},{"key":"e_1_2_1_32_1","volume-title":"Hercules Against Data Series Similarity Search. PVLDB 15, 10","author":"Echihabi Karima","year":"2022","unstructured":"Karima Echihabi, Panagiota Fatourou, Kostas Zoumpatianos, Themis Palpanas, and Houda Benbrahim. 2022. Hercules Against Data Series Similarity Search. PVLDB 15, 10 (2022)."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3282495.3282498"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368303"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704441241"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.05.009"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2021.3067706"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/3303753.3303754"},{"key":"e_1_2_1_39_1","unstructured":"Junhao Gan Jianlin Feng Qiong Fang and Wilfred Ng. 2012. Locality-sensitive hashing scheme based on dynamic collision counting. In SIGMOD. 541--552."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589282"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654970"},{"key":"e_1_2_1_42_1","unstructured":"Aristides Gionis Piotr Indyk and Rajeev Motwani. 1999. Similarity Search in High Dimensions via Hashing. In PVLDB. 518--529."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3604915.3608773"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316349"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/3554821.3554843"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2016.616"},{"key":"e_1_2_1_47_1","unstructured":"M Hauptmann and M Karpinski. 2013. A Compendium on Steiner Tree Problems. (2013)."},{"key":"e_1_2_1_48_1","volume-title":"Konstantin Schall, and Klaus Jung.","author":"Hezel Nico","year":"2023","unstructured":"Nico Hezel, Kai Uwe Barthel, Konstantin Schall, and Klaus Jung. 2023. Fast Approximate Nearest Neighbor Search with a Dynamic Exploration Graph using Continuous Refinement. arXiv:2307.10479 [cs.IR]"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3523227.3546779"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDMW.2013.139"},{"key":"e_1_2_1_51_1","volume-title":"Similarity Search and Applications","author":"Houle Michael E.","unstructured":"Michael E. Houle. 2017. Local Intrinsic Dimensionality I: An Extreme-Value-Theoretic Foundation for Similarity Applications. In Similarity Search and Applications. Springer International Publishing, Cham, 64--79."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDMW.2012.94"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850469.2850470"},{"key":"e_1_2_1_54_1","volume-title":"Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations. In Thirty-seventh Conference on Neural Information Processing Systems.","author":"Indyk Piotr","year":"2023","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."},{"key":"e_1_2_1_55_1","unstructured":"Ishindanil. [n.d.]. directed-steiner-tree. https:\/\/github.com\/ishindanil\/directed-steiner-tree. Accessed: 2024-01-30."},{"key":"e_1_2_1_56_1","unstructured":"Masajiro Iwasaki and Daisuke Miyazaki. 2018. Optimization of Indexing Based on k-Nearest Neighbor Graph for Proximity Search in High-dimensional Data. arXiv:1810.07355 [cs.DB]"},{"key":"e_1_2_1_57_1","volume-title":"Harsha Vardhan Simhadri, and Sheshansh Agrawal","author":"Jaiswal Shikhar","year":"2022","unstructured":"Shikhar Jaiswal, Ravishankar Krishnaswamy, Ankit Garg, Harsha Vardhan Simhadri, and Sheshansh Agrawal. 2022. OOD-DiskANN: Efficient and Scalable Graph ANNS for Out-of-Distribution Queries. arXiv:2211.12850 [cs.LG]"},{"key":"e_1_2_1_58_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 Advances in Neural Information Processing Systems, Vol. 32. Curran Associates, Inc."},{"key":"e_1_2_1_59_1","volume-title":"Product quantization for nearest neighbor search. TPAMI 33, 1","author":"Jegou Herve","year":"2010","unstructured":"Herve Jegou, Matthijs Douze, and Cordelia Schmid. 2010. Product quantization for nearest neighbor search. TPAMI 33, 1 (2010)."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/TBDATA.2019.2921572"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510013"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335325"},{"key":"e_1_2_1_63_1","volume-title":"Graph-based time-space trade-offs for approximate near neighbors. CoRR abs\/1712.03158","author":"Laarhoven Thijs","year":"2017","unstructured":"Thijs Laarhoven. 2017. Graph-based time-space trade-offs for approximate near neighbors. CoRR abs\/1712.03158 (2017)."},{"key":"e_1_2_1_64_1","volume-title":"Advances in Neural Information Processing Systems","author":"Levina Elizaveta","unstructured":"Elizaveta Levina and Peter Bickel. 2004. Maximum Likelihood Estimation of Intrinsic Dimension. In Advances in Neural Information Processing Systems, Vol. 17. MIT Press."},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380600"},{"key":"e_1_2_1_66_1","volume-title":"Proceedings of the 34th International Conference on Machine Learning (Proceedings of Machine Learning Research)","volume":"70","author":"Li Ke","year":"2017","unstructured":"Ke Li and Jitendra Malik. 2017. Fast k-Nearest Neighbour Search via Prioritized DCI. In Proceedings of the 34th International Conference on Machine Learning (Proceedings of Machine Learning Research), Vol. 70. PMLR, 2081--2090."},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2909204"},{"key":"e_1_2_1_68_1","unstructured":"Peng-Cheng Lin and Wan-Lei Zhao. 2019. Graph based Nearest Neighbor Search: Promises and Failures. arXiv:1904.02077 [cs.IR]"},{"key":"e_1_2_1_69_1","doi-asserted-by":"crossref","first-page":"2236","DOI":"10.14778\/3275366.3284968","article-title":"Scalable, Variable-Length Similarity Search in Data Series: The ULISSE Approach","volume":"11","author":"Linardi Michele","year":"2018","unstructured":"Michele Linardi and Themis Palpanas. 2018. Scalable, Variable-Length Similarity Search in Data Series: The ULISSE Approach. Proc. VLDB Endow. 11, 13 (2018), 2236--2248.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00619-4"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM55031.2022.00045"},{"key":"e_1_2_1_72_1","doi-asserted-by":"crossref","unstructured":"Kejing Lu and Mineichi Kudo. 2020. R2LSH: A Nearest Neighbor Search Scheme Based on Two-dimensional Projected Spaces. In ICDE. 1045--1056.","DOI":"10.1109\/ICDE48307.2020.00095"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.14778\/3489496.3489506"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/3267471.3267474"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2013.10.006"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2018.2889473"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2014.2321376"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00778-021-00677-2"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00171"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588908"},{"key":"e_1_2_1_81_1","volume-title":"Manning","author":"Pennington Jeffrey","year":"2014","unstructured":"Jeffrey Pennington, Richard Socher, and Christopher D. Manning. 2014. GloVe: Global Vectors for Word Representation. In Empirical Methods in Natural Language Processing (EMNLP). 1532--1543. http:\/\/www.aclweb.org\/anthology\/D14-1162"},{"key":"e_1_2_1_82_1","volume-title":"Proceedings of the 37th International Conference on Machine Learning (Proceedings of Machine Learning Research)","volume":"119","author":"Prokhorenkova Liudmila","year":"2020","unstructured":"Liudmila Prokhorenkova and Aleksandr Shekhovtsov. 2020. Graph-based Nearest Neighbor Search: From Practice to Theory. In Proceedings of the 37th International Conference on Machine Learning (Proceedings of Machine Learning Research), Vol. 119. 7803--7813."},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/1553374.1553485"},{"key":"e_1_2_1_84_1","volume-title":"Hubs in Space: Popular Nearest Neighbors in High-Dimensional Data. J. Mach. Learn. Res. 11 (dec","author":"Radovanovi\u0107 Milo\u0161","year":"2010","unstructured":"Milo\u0161 Radovanovi\u0107, Alexandros Nanopoulos, and Mirjana Ivanovi\u0107. 2010. Hubs in Space: Popular Nearest Neighbors in High-Dimensional Data. J. Mach. Learn. Res. 11 (dec 2010), 2487--2531."},{"key":"e_1_2_1_85_1","unstructured":"Thomas Rothvo\u00df. 2012. Directed Steiner Tree and the Lasserre Hierarchy. arXiv:1111.5473 [cs.DS]"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-012-5294-7"},{"key":"e_1_2_1_87_1","unstructured":"Jin Shieh and Eamonn Keogh. 2008. iSAX: indexing and mining terabyte sized time series. In SIGKDD. 623--631."},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2015.115"},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2022.3206441"},{"key":"e_1_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(80)90066-7"},{"key":"e_1_2_1_91_1","unstructured":"Saskia van der Hoeven. 2023. Efficient solution methods for the directed Steiner tree problem."},{"key":"e_1_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2019.106970"},{"key":"e_1_2_1_93_1","doi-asserted-by":"publisher","DOI":"10.1145\/3437120.3437343"},{"key":"e_1_2_1_94_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.iot.2021.100428"},{"key":"e_1_2_1_95_1","unstructured":"Skoltech Computer Vision. [n.d.]. Deep billion-scale indexing. http:\/\/sites.skoltech.ru\/compvision\/noimi Accessed March 14 2022."},{"key":"e_1_2_1_96_1","unstructured":"Hui Wang Yong Wang and Wan-Lei Zhao. 2022. Graph-based Approximate NN Search: A Revisit. arXiv:2204.00824 [cs.IR]"},{"key":"e_1_2_1_97_1","unstructured":"Hongya Wang Zhizheng Wang Wei Wang Yingyuan Xiao Zeng Zhao and Kaixiang Yang. 2020. A Note on Graph-Based Nearest Neighbor Search. arXiv:2012.11083 [cs.LG]"},{"key":"e_1_2_1_98_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457550"},{"key":"e_1_2_1_99_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476255"},{"key":"e_1_2_1_100_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467317"},{"key":"e_1_2_1_101_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3270264"},{"key":"e_1_2_1_102_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536206.2536208"},{"key":"e_1_2_1_103_1","first-page":"3","article-title":"Graph-and Tree-based Indexes for High-dimensional Vector Similarity Search: Analyses, Comparisons, and Future Directions","volume":"46","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. IEEE Data Eng. Bull. 46, 3 (2023), 3--21.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_104_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588965"},{"key":"e_1_2_1_105_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_106_1","unstructured":"Zeyu Wang Haoran Xiong Zhenying He Peng Wang and Wei wang. 2024. Distance Comparison Operators for Approximate Nearest Neighbor Search: Exploration and Benchmark. arXiv:2403.13491 [cs.DB] https:\/\/arxiv.org\/abs\/2403.13491"},{"key":"e_1_2_1_107_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-016-0074-0"},{"key":"e_1_2_1_108_1","doi-asserted-by":"publisher","DOI":"10.14778\/3415478.3415541"},{"key":"e_1_2_1_109_1","doi-asserted-by":"publisher","DOI":"10.14778\/3665844.3665854"},{"key":"e_1_2_1_110_1","first-page":"9","article-title":"CIVET: Exploring Compact Index for Variable-Length Subsequence Matching on Time Series","volume":"17","author":"Xiong Haoran","year":"2024","unstructured":"Haoran Xiong, Hang Zhang, Zeyu Wang, Zhenying He, Peng Wang, and X. Sean Wang. 2024. CIVET: Exploring Compact Index for Variable-Length Subsequence Matching on Time Series. Proc. VLDB Endow. 17, 9 (aug 2024), 2123--2135.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_1_111_1","doi-asserted-by":"publisher","DOI":"10.1145\/3600006.3613166"},{"key":"e_1_2_1_112_1","doi-asserted-by":"crossref","unstructured":"Djamel Edine Yagoubi Reza Akbarinia Florent Masseglia and Themis Palpanas. 2017. DPiSAX: Massively Distributed Partitioned iSAX. In ICDM.","DOI":"10.1109\/ICDM.2017.151"},{"key":"e_1_2_1_113_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2880215"},{"key":"e_1_2_1_114_1","doi-asserted-by":"publisher","DOI":"10.1145\/3488560.3498425"},{"key":"e_1_2_1_115_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-022-00762-0"},{"key":"e_1_2_1_116_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."},{"key":"e_1_2_1_117_1","doi-asserted-by":"publisher","DOI":"10.14778\/3594512.3594527"},{"key":"e_1_2_1_118_1","doi-asserted-by":"publisher","DOI":"10.14778\/3377369.3377374"},{"key":"e_1_2_1_119_1","volume-title":"The Eleventh International Conference on Learning Representations.","author":"Zhou Shuyan","year":"2023","unstructured":"Shuyan Zhou, Uri Alon, Frank F. Xu, Zhengbao Jiang, and Graham Neubig. 2023. DocPrompting: Generating Code by Retrieving the Docs. In The Eleventh International Conference on Learning Representations."},{"key":"e_1_2_1_120_1","unstructured":"Dantong Zhu and Minjia Zhang. 2021. Understanding and Generalizing Monotonic Proximity Graphs for Approximate Nearest Neighbor Search. arXiv:2107.13052 [cs.IR]"},{"key":"e_1_2_1_121_1","volume-title":"Pivot selection algorithms in metric spaces: a survey and experimental study. The VLDB Journal","author":"Zhu Yifan","year":"2022","unstructured":"Yifan Zhu, Lu Chen, Yunjun Gao, and Christian S Jensen. 2022. Pivot selection algorithms in metric spaces: a survey and experimental study. The VLDB Journal (2022), 1--25."},{"key":"e_1_2_1_122_1","doi-asserted-by":"publisher","DOI":"10.5555\/545381.545388"},{"key":"e_1_2_1_123_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-018-0513-x"},{"key":"e_1_2_1_124_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783382"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3704965.3704974","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,18]],"date-time":"2025-02-18T17:34:24Z","timestamp":1739900064000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3704965.3704974"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9]]},"references-count":124,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["10.14778\/3704965.3704974"],"URL":"https:\/\/doi.org\/10.14778\/3704965.3704974","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,9]]},"assertion":[{"value":"2025-02-18","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}