{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T00:10:17Z","timestamp":1774311017589,"version":"3.50.1"},"publisher-location":"Cham","reference-count":40,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032213235","type":"print"},{"value":"9783032213242","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"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-21324-2_3","type":"book-chapter","created":{"date-parts":[[2026,3,23]],"date-time":"2026-03-23T08:39:23Z","timestamp":1774255163000},"page":"33-48","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Down with\u00a0the\u00a0Hierarchy: The \u2018H\u2019 in\u00a0HNSW Stands for\u00a0\u201cHubs\u201d"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-7269-4710","authenticated-orcid":false,"given":"Blaise","family":"Munyampirwa","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-9836-7714","authenticated-orcid":false,"given":"Vihan","family":"Lakshman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-8045-3717","authenticated-orcid":false,"given":"Benjamin","family":"Coleman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,3,24]]},"reference":[{"key":"3_CR1","doi-asserted-by":"publisher","unstructured":"Aguerrebere, C., Bhati, I., Hildebrand, M., Tepper, M., Willke, T.: Similarity search in the blink of an eye with compressed indices. Proc. VLDB Endowment 16, 3433\u20133446 (2023). https:\/\/doi.org\/10.14778\/3611479.3611537","DOI":"10.14778\/3611479.3611537"},{"key":"3_CR2","doi-asserted-by":"crossref","unstructured":"Aum\u00fcller, M., Bernhardsson, E., Faithfull, A.J.: Ann-benchmarks: a benchmarking tool for approximate nearest neighbor algorithms. Inf. Syst. 87 (2018). https:\/\/api.semanticscholar.org\/CorpusID:36089988","DOI":"10.1016\/j.is.2019.02.006"},{"issue":"9","key":"3_CR3","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1145\/361002.361007","volume":"18","author":"JL Bentley","year":"1975","unstructured":"Bentley, J.L.: Multidimensional binary search trees used for associative searching. Commun. ACM 18(9), 509\u2013517 (1975)","journal-title":"Commun. ACM"},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"Beygelzimer, A., Kakade, S., Langford, J.: Cover trees for nearest neighbor. In: Proceedings of the 23rd International Conference on Machine Learning, pp. 97\u2013104 (2006)","DOI":"10.1145\/1143844.1143857"},{"key":"3_CR5","doi-asserted-by":"publisher","unstructured":"Boytsov, L., Naidan, B.: Engineering efficient and effective non-metric space library. In: Brisaboa, N., Pedreira, O., Zezula, P. (eds.) Similarity Search and Applications: 6th International Conference, SISAP 2013, A Coru\u00f1a, Spain, October 2\u20134, 2013, Proceedings 6, pp. 280\u2013293. Springer, Cham (2013). https:\/\/doi.org\/10.1007\/978-3-642-41062-8_28","DOI":"10.1007\/978-3-642-41062-8_28"},{"key":"3_CR6","doi-asserted-by":"publisher","first-page":"38488","DOI":"10.52202\/068431-2789","volume":"35","author":"B Coleman","year":"2022","unstructured":"Coleman, B., Segarra, S., Smola, A.J., Shrivastava, A.: Graph reordering for cache-efficient near neighbor search. Adv. Neural. Inf. Process. Syst. 35, 38488\u201338500 (2022)","journal-title":"Adv. Neural. Inf. Process. Syst."},{"key":"3_CR7","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to algorithms. MIT press (2022)"},{"key":"3_CR8","doi-asserted-by":"crossref","unstructured":"Dasgupta, S., Freund, Y.: Random projection trees and low dimensional manifolds. In: Proceedings of the fortieth annual ACM symposium on Theory of computing, pp. 537\u2013546 (2008)","DOI":"10.1145\/1374376.1374452"},{"key":"3_CR9","unstructured":"Dolatshah, M., Hadian, A., Minaei-Bidgoli, B.: Ball*-tree: Efficient spatial indexing for constrained nearest-neighbor search in metric spaces. arXiv preprint arXiv:1511.00628 (2015)"},{"key":"3_CR10","unstructured":"Dong, Y., Indyk, P., Razenshteyn, I., Wagner, T.: Learning space partitions for nearest neighbor search. arXiv preprint arXiv:1901.08544 (2019)"},{"key":"3_CR11","first-page":"38912","volume":"35","author":"C Feng","year":"2022","unstructured":"Feng, C., Li, W., Lian, D., Liu, Z., Chen, E.: Recommender forest for efficient retrieval. Adv. Neural. Inf. Process. Syst. 35, 38912\u201338924 (2022)","journal-title":"Adv. Neural. Inf. Process. Syst."},{"key":"3_CR12","doi-asserted-by":"crossref","unstructured":"Fran\u00e7ois, D., Wertz, V., Verleysen, M.: The concentration of fractional distances. IEEE Trans. Knowl. Data Eng. 19, 873\u2013886 (2007). https:\/\/api.semanticscholar.org\/CorpusID:13220558","DOI":"10.1109\/TKDE.2007.1037"},{"key":"3_CR13","unstructured":"Fu, C., Xiang, C., Wang, C., Cai, D.: Fast approximate nearest neighbor search with the navigating spreading-out graph. arXiv preprint arXiv:1707.00143 (2017)"},{"key":"3_CR14","unstructured":"Gionis, A., Indyk, P., Motwani, R., et\u00a0al.: Similarity search in high dimensions via hashing. In: Vldb. vol.\u00a099, pp. 518\u2013529 (1999)"},{"key":"3_CR15","doi-asserted-by":"crossref","unstructured":"Guibas, L.J., Sedgewick, R.: A dichromatic framework for balanced trees. In: 19th Annual Symposium on Foundations of Computer Science (sfcs 1978), pp. 8\u201321. IEEE (1978)","DOI":"10.1109\/SFCS.1978.3"},{"key":"3_CR16","unstructured":"Guo, R., Sun, P., Lindgren, E., Geng, Q., Simcha, D., Chern, F., Kumar, S.: Accelerating large-scale inference with anisotropic vector quantization. In: International Conference on Machine Learning, pp. 3887\u20133896. PMLR (2020)"},{"key":"3_CR17","unstructured":"Guo, R., et al.: Accelerating large-scale inference with anisotropic vector quantization. In: International Conference on Machine Learning (2019). https:\/\/api.semanticscholar.org\/CorpusID:218614141"},{"key":"3_CR18","doi-asserted-by":"crossref","unstructured":"Indyk, P., Motwani, R.: Approximate nearest neighbors: towards removing the curse of dimensionality. In: Proceedings of the thirtieth annual ACM symposium on Theory of computing, pp. 604\u2013613 (1998)","DOI":"10.1145\/276698.276876"},{"key":"3_CR19","doi-asserted-by":"crossref","unstructured":"Iwasaki, M.: Pruned bi-directed k-nearest neighbor graph for proximity search. In: International Conference on Similarity Search and Applications, pp. 20\u201333. Springer, Cham (2016)","DOI":"10.1007\/978-3-319-46759-7_2"},{"key":"3_CR20","unstructured":"Iwasaki, M., Miyazaki, D.: Optimization of indexing based on k-nearest neighbor graph for proximity search in high-dimensional data. arXiv preprint arXiv:1810.07355 (2018)"},{"key":"3_CR21","unstructured":"Jayaram\u00a0Subramanya, S., Devvrit, F., Simhadri, H.V., Krishnawamy, R., Kadekodi, R.: Diskann: Fast accurate billion-point nearest neighbor search on a single node. Adv. Neural Inf. Process. Syst. 32 (2019)"},{"issue":"1","key":"3_CR22","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1109\/TPAMI.2010.57","volume":"33","author":"H Jegou","year":"2010","unstructured":"Jegou, H., Douze, M., Schmid, C.: Product quantization for nearest neighbor search. IEEE Trans. Pattern Anal. Mach. Intell. 33(1), 117\u2013128 (2010)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"3_CR23","doi-asserted-by":"crossref","unstructured":"Johnson, J., Douze, M., J\u00e9gou, H.: Billion-scale similarity search with gpus. IEEE Trans. Big Data 7, 535\u2013547 (2017). https:\/\/api.semanticscholar.org\/CorpusID:926364","DOI":"10.1109\/TBDATA.2019.2921572"},{"key":"3_CR24","unstructured":"Lewis, P., et al.: Retrieval-augmented generation for knowledge-intensive nlp tasks. ArXiv abs\/2005.11401 (2020). https:\/\/api.semanticscholar.org\/CorpusID:218869575"},{"key":"3_CR25","unstructured":"Lin, P.C., Zhao, W.L.: Graph based nearest neighbor search: Promises and failures. arXiv preprint arXiv:1904.02077 (2019)"},{"key":"3_CR26","doi-asserted-by":"crossref","unstructured":"Low, T., Borgelt, C., Stober, S., N\u00fcrnberger, A.: The hubness phenomenon: fact or artifact? Towards Advanced Data Analysis by Combining Soft Computing and Statistics, pp. 267\u2013278 (2013)","DOI":"10.1007\/978-3-642-30278-7_21"},{"key":"3_CR27","doi-asserted-by":"crossref","unstructured":"Malkov, Y., Yashunin, D.A.: Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Trans. Patt. Anal. Mach. Intell. 42, 824\u2013836 (2016). https:\/\/api.semanticscholar.org\/CorpusID:8915893","DOI":"10.1109\/TPAMI.2018.2889473"},{"key":"3_CR28","doi-asserted-by":"crossref","unstructured":"Mann, H.B., Whitney, D.R.: On a test of whether one of two random variables is stochastically larger than the other. In: The annals of mathematical statistics, pp. 50\u201360 (1947)","DOI":"10.1214\/aoms\/1177730491"},{"key":"3_CR29","unstructured":"Mikolov, T., Sutskever, I., Chen, K., Corrado, G.S., Dean, J.: Distributed representations of words and phrases and their compositionality. Adv. Neural Inf. Process. Syst. 26 (2013)"},{"key":"3_CR30","doi-asserted-by":"crossref","unstructured":"Munoz, J.V., Gon\u00e7alves, M.A., Dias, Z., Torres, R.d.S.: Hierarchical clustering-based graphs for large scale approximate nearest neighbor search. Pattern Recognit. 96, 106970 (2019)","DOI":"10.1016\/j.patcog.2019.106970"},{"key":"3_CR31","unstructured":"Panigrahy, R.: Entropy based nearest neighbor search in high dimensions. arXiv preprint cs\/0510019 (2005)"},{"key":"3_CR32","unstructured":"Pinterest: Manas hnsw realtime: Powering realtime embedding-based retrieval (2021). https:\/\/medium.com\/pinterest-engineering\/manas-hnsw-realtime-powering-realtime-embedding-based-retrieval-dc71dfd6afdd"},{"issue":"6","key":"3_CR33","doi-asserted-by":"publisher","first-page":"668","DOI":"10.1145\/78973.78977","volume":"33","author":"W Pugh","year":"1990","unstructured":"Pugh, W.: Skip lists: a probabilistic alternative to balanced trees. Commun. ACM 33(6), 668\u2013676 (1990)","journal-title":"Commun. ACM"},{"key":"3_CR34","unstructured":"Radovanovic, M., Nanopoulos, A., Ivanovic, M.: Hubs in space: popular nearest neighbors in high-dimensional data. J. Mach. Learn. Res. 11(sept), 2487\u20132531 (2010)"},{"key":"3_CR35","doi-asserted-by":"crossref","unstructured":"Ram, P., Sinha, K.: Revisiting kd-tree for nearest neighbor search. In: Proceedings of the 25th acm sigkdd international conference on knowledge discovery & data mining, pp. 1378\u20131388 (2019)","DOI":"10.1145\/3292500.3330875"},{"issue":"2","key":"3_CR36","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1145\/356924.356930","volume":"16","author":"H Samet","year":"1984","unstructured":"Samet, H.: The quadtree and related hierarchical data structures. ACM Comput. Surv. (CSUR) 16(2), 187\u2013260 (1984)","journal-title":"ACM Comput. Surv. (CSUR)"},{"key":"3_CR37","unstructured":"Simhadri, H.V., et al.: Results of the neurips\u201921 challenge on billion-scale approximate nearest neighbor search. In: Neural Information Processing Systems (2022). https:\/\/api.semanticscholar.org\/CorpusID:248572299"},{"key":"3_CR38","doi-asserted-by":"crossref","unstructured":"Talagrand, M.: Concentration of measure and isoperimetric inequalities in product spaces. Publications Math\u00e9matiques de l\u2019Institut des Hautes \u00c9tudes Scientifiques 81, 73\u2013205 (1994). https:\/\/api.semanticscholar.org\/CorpusID:119668709","DOI":"10.1007\/BF02699376"},{"key":"3_CR39","doi-asserted-by":"crossref","unstructured":"Xian, J., Teofili, T., Pradeep, R., Lin, J.: Vector search with openai embeddings: Lucene is all you need. In: Proceedings of the 17th ACM International Conference on Web Search and Data Mining, pp. 1090\u20131093 (2024)","DOI":"10.1145\/3616855.3635691"},{"issue":"16","key":"3_CR40","doi-asserted-by":"publisher","first-page":"e74","DOI":"10.1093\/nar\/gkae609","volume":"52","author":"J Zhao","year":"2024","unstructured":"Zhao, J., Both, J.P., Rodriguez-R, L.M., Konstantinidis, K.T.: Gsearch: ultra-fast and scalable genome search by combining k-mer hashing with hierarchical navigable small world graphs. Nucleic Acids Res. 52(16), e74\u2013e74 (2024)","journal-title":"Nucleic Acids Res."}],"container-title":["Lecture Notes in Computer Science","Advances in Information Retrieval"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-21324-2_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,23]],"date-time":"2026-03-23T23:15:54Z","timestamp":1774307754000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-21324-2_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032213235","9783032213242"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-21324-2_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"24 March 2026","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":"ECIR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"European Conference on Information Retrieval","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Delft","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"The Netherlands","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 March 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 April 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"48","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ecir2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ecir2026.eu\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}