{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,8]],"date-time":"2025-10-08T00:26:47Z","timestamp":1759883207108,"version":"build-2065373602"},"publisher-location":"Cham","reference-count":14,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032060686","type":"print"},{"value":"9783032060693","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,10,8]],"date-time":"2025-10-08T00:00:00Z","timestamp":1759881600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,10,8]],"date-time":"2025-10-08T00:00:00Z","timestamp":1759881600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-06069-3_22","type":"book-chapter","created":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T15:53:41Z","timestamp":1759852421000},"page":"273-287","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Theoretical and\u00a0Practical Insights Into Graph-Based Indexing"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1639-3534","authenticated-orcid":false,"given":"Erik","family":"Thordsen","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9143-4880","authenticated-orcid":false,"given":"Erich","family":"Schubert","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,10,8]]},"reference":[{"key":"22_CR1","unstructured":"Balister, P., Bollob\u00e1s, B.: Percolation in the K-nearest neighbor graph. recent results in designs and graphs: a tribute to Lucia Gionfriddo. Quaderni di Matematica 28, 83\u2013100 (2013)"},{"key":"22_CR2","doi-asserted-by":"publisher","unstructured":"Billiot, J.M., Corset, F., Fontenas, \u00c9.: Continuum percolation in the relative neighborhood graph. arXiv: Mathematical Physics (2010). https:\/\/doi.org\/10.48550\/arXiv.1004.5292","DOI":"10.48550\/arXiv.1004.5292"},{"key":"22_CR3","doi-asserted-by":"publisher","unstructured":"B\u00f6r\u00f6czky, K., Wintsche, G.: Covering the sphere by equal spherical balls, pp. 235\u2013251 (2003). https:\/\/doi.org\/10.1007\/978-3-642-55566-4_10","DOI":"10.1007\/978-3-642-55566-4_10"},{"key":"22_CR4","doi-asserted-by":"publisher","unstructured":"Dearholt, D.W., Gonzales, N., Kurup, G., 3CRL, F., Cruces, N.L.: Monotonic search networks for computer vision databases. In: Asilomar Conference on Signals, Systems and Computers, vol. 2, pp. 548\u2013553 (1988). https:\/\/doi.org\/10.1109\/ACSSC.1988.754602","DOI":"10.1109\/ACSSC.1988.754602"},{"key":"22_CR5","doi-asserted-by":"publisher","unstructured":"Dong, W., Charikar, M., Li, K.: Efficient K-nearest neighbor graph construction for generic similarity measures. In: Proc. World Wide Web, WWW, pp. 577\u2013586 (2011). https:\/\/doi.org\/10.1145\/1963405.1963487","DOI":"10.1145\/1963405.1963487"},{"issue":"8","key":"22_CR6","doi-asserted-by":"publisher","first-page":"4139","DOI":"10.1109\/TPAMI.2021.3067706","volume":"44","author":"C Fu","year":"2022","unstructured":"Fu, C., Wang, C., Cai, D.: High dimensional similarity search with satellite system graph: efficiency, scalability, and unindexed query compatibility. IEEE Trans. Pattern Anal. Mach. Intell. 44(8), 4139\u20134150 (2022). https:\/\/doi.org\/10.1109\/TPAMI.2021.3067706","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"22_CR7","doi-asserted-by":"publisher","unstructured":"Fu, C., Xiang, C., Wang, C., Cai, D.: Fast approximate nearest neighbor search with the navigating spreading-out graph. Proc. VLDB Endow. 12(5), 461\u2013474 (2019). https:\/\/doi.org\/10.14778\/3303753.3303754","DOI":"10.14778\/3303753.3303754"},{"key":"22_CR8","doi-asserted-by":"publisher","first-page":"259","DOI":"10.2307\/2412323","volume":"18","author":"KR Gabriel","year":"1969","unstructured":"Gabriel, K.R., Sokal, R.R.: A new statistical approach to geographic variation analysis. Syst. Biol. 18, 259\u2013278 (1969). https:\/\/doi.org\/10.2307\/2412323","journal-title":"Syst. Biol."},{"key":"22_CR9","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1002\/(SICI)1098-2418(199610)9:3<295::AID-RSA3>3.0.CO;2-S","volume":"9","author":"O H\u00e4ggstr\u00f6m","year":"1996","unstructured":"H\u00e4ggstr\u00f6m, O., Meester, R.W.J.: Nearest neighbor and hard sphere models in continuum percolation. Random Struct. Algorithms 9, 295\u2013315 (1996)","journal-title":"Random Struct. Algorithms"},{"issue":"9","key":"22_CR10","doi-asserted-by":"publisher","first-page":"1502","DOI":"10.1109\/5.163414","volume":"80","author":"JW Jaromczyk","year":"1992","unstructured":"Jaromczyk, J.W., Toussaint, G.T.: Relative neighborhood graphs and their relatives. Proc. IEEE 80(9), 1502\u20131517 (1992). https:\/\/doi.org\/10.1109\/5.163414","journal-title":"Proc. IEEE"},{"key":"22_CR11","doi-asserted-by":"publisher","first-page":"66","DOI":"10.3923\/AJMS.2011.66.70","volume":"4","author":"S Li","year":"2011","unstructured":"Li, S.: Concise formulas for the area and volume of a hyperspherical cap. Asian J. Math. Stat. 4, 66\u201370 (2011). https:\/\/doi.org\/10.3923\/AJMS.2011.66.70","journal-title":"Asian J. Math. Stat."},{"issue":"4","key":"22_CR12","doi-asserted-by":"publisher","first-page":"824","DOI":"10.1109\/TPAMI.2018.2889473","volume":"42","author":"YA Malkov","year":"2018","unstructured":"Malkov, Y.A., Yashunin, D.A.: Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Trans. Pattern Anal. Mach. Intell. 42(4), 824\u2013836 (2018). https:\/\/doi.org\/10.1109\/TPAMI.2018.2889473","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"22_CR13","doi-asserted-by":"publisher","unstructured":"Okkels, C.B., Thordsen, E., Aum\u00fcller, M., Zimek, A., Schubert, E.: Approximate single-linkage clustering using graph-based indexes: MST-based approaches and incremental searchers. In: Proceedings of the Similarity Search and Applications, SISAP (2025). https:\/\/doi.org\/10.1007\/978-3-032-06069-3_19","DOI":"10.1007\/978-3-032-06069-3_19"},{"key":"22_CR14","doi-asserted-by":"publisher","unstructured":"Teofili, T., Lin, J.: Patience in proximity: a simple early termination strategy for HNSW graph traversal in approximate K-nearest neighbor search. In: European Conference on Information Retrieval (2025). https:\/\/doi.org\/10.1007\/978-3-031-88714-7_39","DOI":"10.1007\/978-3-031-88714-7_39"}],"container-title":["Lecture Notes in Computer Science","Similarity Search and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-06069-3_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T16:08:11Z","timestamp":1759853291000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-06069-3_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,8]]},"ISBN":["9783032060686","9783032060693"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-06069-3_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,8]]},"assertion":[{"value":"8 October 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"SISAP","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Similarity Search and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Reykjavik","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Iceland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 October 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 October 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sisap2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.sisap.org\/2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}