{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,8]],"date-time":"2025-10-08T00:26:26Z","timestamp":1759883186070,"version":"build-2065373602"},"publisher-location":"Cham","reference-count":24,"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_19","type":"book-chapter","created":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T15:52:51Z","timestamp":1759852371000},"page":"233-247","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Approximate Single-Linkage Clustering Using Graph-Based Indexes: MST-Based Approaches and\u00a0Incremental Searchers"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-1904-4024","authenticated-orcid":false,"given":"Camilla Birch","family":"Okkels","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1639-3534","authenticated-orcid":false,"given":"Erik","family":"Thordsen","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7212-6476","authenticated-orcid":false,"given":"Martin","family":"Aum\u00fcller","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7713-4208","authenticated-orcid":false,"given":"Arthur","family":"Zimek","sequence":"additional","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":"19_CR1","unstructured":"Abboud, A., Cohen-Addad, V., Houdrouge, H.: Subquadratic high-dimensional hierarchical clustering. In: NeurIPS, pp. 11576\u201311586 (2019)"},{"key":"19_CR2","doi-asserted-by":"crossref","unstructured":"Alman, J., Williams, R.: Probabilistic polynomials and hamming nearest neighbors. In: FOCS, pp. 136\u2013150. IEEE Computer Society (2015)","DOI":"10.1109\/FOCS.2015.18"},{"key":"19_CR3","doi-asserted-by":"crossref","unstructured":"Azizi, I., Echihabi, K., Palpanas, T.: Graph-based vector search: an experimental evaluation of the state-of-the-art. Proc. ACM Manag. Data 3(1), 43:1\u201343:31 (2025)","DOI":"10.1145\/3709693"},{"key":"19_CR4","unstructured":"Ester, M., Kriegel, H., Sander, J., Xu, X.: A density-based algorithm for discovering clusters in large spatial databases with noise. In: KDD, pp. 226\u2013231 (1996)"},{"key":"19_CR5","doi-asserted-by":"crossref","unstructured":"Gan, J., Tao, Y.: On the hardness and approximation of Euclidean DBSCAN. ACM Trans. Database Syst. 42(3), 14:1\u201314:45 (2017)","DOI":"10.1145\/3083897"},{"key":"19_CR6","doi-asserted-by":"crossref","unstructured":"Huang, Y., Yu, S., Shun, J.: Faster parallel exact density peaks clustering. In: ACDA, pp. 49\u201362. SIAM (2023)","DOI":"10.1137\/1.9781611977714.5"},{"issue":"1","key":"19_CR7","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/s10115-006-0027-5","volume":"12","author":"H Koga","year":"2007","unstructured":"Koga, H., Ishibashi, T., Watanabe, T.: Fast agglomerative hierarchical clustering algorithm using locality-sensitive hashing. Knowl. Inf. Syst. 12(1), 25\u201353 (2007)","journal-title":"Knowl. Inf. Syst."},{"issue":"2","key":"19_CR8","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/s10115-016-1004-2","volume":"52","author":"H Kriegel","year":"2017","unstructured":"Kriegel, H., Schubert, E., Zimek, A.: The (black) art of runtime evaluation: are we comparing algorithms or implementations? Knowl. Inf. Syst. 52(2), 341\u2013378 (2017)","journal-title":"Knowl. Inf. Syst."},{"issue":"1","key":"19_CR9","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","volume":"7","author":"JB Kruskal","year":"1956","unstructured":"Kruskal, J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Am. Math. Soc. 7(1), 48\u201350 (1956)","journal-title":"Proc. Am. Math. Soc."},{"key":"19_CR10","doi-asserted-by":"crossref","unstructured":"Malkov, Y.A., Yashunin, D.A.: Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE TPAMI 42(4) (2020)","DOI":"10.1109\/TPAMI.2018.2889473"},{"key":"19_CR11","unstructured":"Okkels, C.B., Aum\u00fcller, M., Thomsen, V.B., Zimek, A.: High-dimensional density-based clustering using locality-sensitive hashing. In: EDBT, pp. 694\u2013706 (2025)"},{"key":"19_CR12","doi-asserted-by":"crossref","unstructured":"Okkels, C.B., Aum\u00fcller, M., Zimek, A.: On the design of scalable outlier detection methods using approximate nearest neighbor graphs. In: SISAP, pp. 170\u2013184 (2024)","DOI":"10.1007\/978-3-031-75823-2_14"},{"key":"19_CR13","doi-asserted-by":"crossref","unstructured":"Santos, J.A., Iqbal, S.T., Naldi, M.C., Campello, R.J.G.B., Sander, J.: Hierarchical density-based clustering using MapReduce. IEEE Trans. Big Data 7(1), 102\u2013114 (2021)","DOI":"10.1109\/TBDATA.2019.2907624"},{"issue":"4","key":"19_CR14","doi-asserted-by":"publisher","first-page":"972","DOI":"10.1007\/s10618-017-0498-x","volume":"31","author":"J Schneider","year":"2017","unstructured":"Schneider, J., Vlachos, M.: Scalable density-based clustering with quality guarantees using random projections. Data Min. Knowl. Disc. 31(4), 972\u20131005 (2017). https:\/\/doi.org\/10.1007\/s10618-017-0498-x","journal-title":"Data Min. Knowl. Disc."},{"key":"19_CR15","doi-asserted-by":"crossref","unstructured":"Schubert, E.: Hierarchical clustering without pairwise distances by incremental similarity search. In: Proceedings of the SISAP, pp. 238\u2013252 (2024)","DOI":"10.1007\/978-3-031-75823-2_20"},{"key":"19_CR16","doi-asserted-by":"crossref","unstructured":"Schubert, E., Sander, J., Ester, M., Kriegel, H., Xu, X.: DBSCAN revisited, revisited: Why and how you should (still) use DBSCAN. ACM Trans. Database Syst. 42(3), 19:1\u201319:21 (2017)","DOI":"10.1145\/3068335"},{"key":"19_CR17","doi-asserted-by":"crossref","unstructured":"Sibson, R.: SLINK: an optimally efficient algorithm for the single-link cluster method. Comput. J. 16(1), 30\u201334 (1973)","DOI":"10.1093\/comjnl\/16.1.30"},{"key":"19_CR18","unstructured":"Sokal, R.R., Michener, C.D., et\u00a0al.: A statistical method for evaluating systematic relationships (1958)"},{"issue":"2","key":"19_CR19","doi-asserted-by":"publisher","first-page":"33","DOI":"10.2307\/1217208","volume":"11","author":"RR Sokal","year":"1962","unstructured":"Sokal, R.R., Rohlf, F.J.: The comparison of dendrograms by objective methods. Taxon 11(2), 33\u201340 (1962)","journal-title":"Taxon"},{"key":"19_CR20","unstructured":"Thordsen, E., Schubert, E.: Theoretical and practical insights into graph-based indexing. In: Proceedigs of the International Conference on Similarity Search and Applications, SISAP (2025)"},{"key":"19_CR21","unstructured":"Virtanen, P., et al.: SciPy 1.0\u2013fundamental algorithms for scientific computing in Python. CoRR 1907.10121 (2019)"},{"key":"19_CR22","doi-asserted-by":"crossref","unstructured":"Wang, Y., Yu, S., Gu, Y., Shun, J.: Fast parallel algorithms for Euclidean minimum spanning tree and hierarchical spatial clustering. In: SIGMOD Conference, pp. 1982\u20131995. ACM (2021)","DOI":"10.1145\/3448016.3457296"},{"key":"19_CR23","unstructured":"Weber, R., Schek, H., Blott, S.: A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. In: VLDB, pp. 194\u2013205 (1998)"},{"key":"19_CR24","unstructured":"Xu, H., Pham, N.: Scalable DBSCAN with random projections. In: NeurIPS (2024)"}],"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_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T15:52:55Z","timestamp":1759852375000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-06069-3_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,8]]},"ISBN":["9783032060686","9783032060693"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-06069-3_19","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"}}]}}