{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,24]],"date-time":"2025-04-24T04:29:35Z","timestamp":1745468975584,"version":"3.40.4"},"publisher-location":"Cham","reference-count":39,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031758225"},{"type":"electronic","value":"9783031758232"}],"license":[{"start":{"date-parts":[[2024,10,25]],"date-time":"2024-10-25T00:00:00Z","timestamp":1729814400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,10,25]],"date-time":"2024-10-25T00:00:00Z","timestamp":1729814400000},"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":[[2025]]},"DOI":"10.1007\/978-3-031-75823-2_13","type":"book-chapter","created":{"date-parts":[[2024,10,24]],"date-time":"2024-10-24T20:33:24Z","timestamp":1729802004000},"page":"155-169","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An Empirical Evaluation of\u00a0Search Strategies for\u00a0Locality-Sensitive Hashing: Lookup, Voting, and\u00a0Natural Classifier Search"],"prefix":"10.1007","author":[{"given":"Malte Helin","family":"Johnsen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7212-6476","authenticated-orcid":false,"given":"Martin","family":"Aum\u00fcller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,10,25]]},"reference":[{"key":"13_CR1","doi-asserted-by":"crossref","unstructured":"Ahle, T.D., Aum\u00fcller, M., Pagh, R.: Parameter-free locality sensitive hashing for spherical range reporting. In: SODA (2017)","DOI":"10.1137\/1.9781611974782.16"},{"key":"13_CR2","doi-asserted-by":"crossref","unstructured":"Amsaleg, L., Chelly, O., Furon, T., Girard, S., Houle, M.E., Kawarabayashi, K., Nett, M.: Estimating local intrinsic dimensionality. In: KDD (2015)","DOI":"10.1145\/2783258.2783405"},{"key":"13_CR3","unstructured":"Andoni, A., Indyk, P., Laarhoven, T., Razenshteyn, I.P., Schmidt, L.: Practical and optimal LSH for angular distance. In: NIPS, pp. 1225\u20131233 (2015)"},{"key":"13_CR4","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 (2020)","DOI":"10.1016\/j.is.2019.02.006"},{"key":"13_CR5","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2021.101807","volume":"101","author":"M Aum\u00fcller","year":"2021","unstructured":"Aum\u00fcller, M., Ceccarello, M.: The role of local dimensionality measures in benchmarking nearest neighbor search. Inf. Syst. 101, 101807 (2021)","journal-title":"Inf. Syst."},{"issue":"3","key":"13_CR6","first-page":"89","volume":"46","author":"M Aum\u00fcller","year":"2023","unstructured":"Aum\u00fcller, M., Ceccarello, M.: Recent approaches and trends in approximate nearest neighbor search, with remarks on benchmarking. IEEE Data Eng. Bull. 46(3), 89\u2013105 (2023)","journal-title":"IEEE Data Eng. Bull."},{"key":"13_CR7","unstructured":"Aum\u00fcller, M., Christiani, T., Pagh, R., Vesterli, M.: PUFFINN: parameterless and universally fast finding of nearest neighbors. In: ESA (2019)"},{"key":"13_CR8","doi-asserted-by":"crossref","unstructured":"Bawa, M., Condie, T., Ganesan, P.: LSH forest: self-tuning indexes for similarity search. In: WWW. ACM, pp. 651\u2013660 (2005)","DOI":"10.1145\/1060745.1060840"},{"key":"13_CR9","doi-asserted-by":"crossref","unstructured":"Bentley, J.L.: Multidimensional binary search trees used for associative searching. Commun. ACM 18(9) (sep 1975)","DOI":"10.1145\/361002.361007"},{"key":"13_CR10","doi-asserted-by":"crossref","unstructured":"Beygelzimer, A., Kakade, S.M., Langford, J.: Cover trees for nearest neighbor. In: ICML 2006. ACM","DOI":"10.1145\/1143844.1143857"},{"key":"13_CR11","doi-asserted-by":"crossref","unstructured":"Charikar, M.S.: Similarity estimation techniques from rounding algorithms. In: STOC (2002)","DOI":"10.1145\/509907.509965"},{"key":"13_CR12","doi-asserted-by":"crossref","unstructured":"Christiani, T.: A framework for similarity search with space-time tradeoffs using locality-sensitive filtering. In: SODA. SIAM, pp. 31\u201346 (2017)","DOI":"10.1137\/1.9781611974782.3"},{"key":"13_CR13","doi-asserted-by":"crossref","unstructured":"Christiani, T.: Fast locality-sensitive hashing frameworks for approximate near neighbor search. In: SISAP (2019)","DOI":"10.1007\/978-3-030-32047-8_1"},{"key":"13_CR14","doi-asserted-by":"crossref","unstructured":"Christiani, T., Pagh, R., Thorup, M.: Confirmation sampling for exact nearest neighbor search. In: SISAP (2020)","DOI":"10.1007\/978-3-030-60936-8_8"},{"key":"13_CR15","doi-asserted-by":"crossref","unstructured":"Chum, O., Philbin, J., Sivic, J., Isard, M., Zisserman, A.: Total recall: automatic query expansion with a generative feature model for object retrieval. In: ICCV (2007)","DOI":"10.1109\/ICCV.2007.4408891"},{"key":"13_CR16","doi-asserted-by":"crossref","unstructured":"Dasgupta, S., Sinha, K.: Randomized partition trees for exact nearest neighbor search. In: COLT (2013)","DOI":"10.1007\/s00453-014-9885-5"},{"key":"13_CR17","doi-asserted-by":"crossref","unstructured":"Datar, M., Immorlica, N., Indyk, P., Mirrokni, V.S.: Locality-sensitive hashing scheme based on p-stable distributions. In: SCG. SCG \u201904 (2004)","DOI":"10.1145\/997817.997857"},{"key":"13_CR18","unstructured":"Dijkstra, E.W.: A Discipline of Programming. Prentice-Hall (1976)"},{"key":"13_CR19","doi-asserted-by":"crossref","unstructured":"Dong, W., Wang, Z., Josephson, W., Charikar, M., Li, K.: Modeling LSH for performance tuning. In: CIKM. ACM, pp. 669\u2013678 (2008)","DOI":"10.1145\/1458082.1458172"},{"key":"13_CR20","unstructured":"Douze, M., Guzhva, A., Deng, C., Johnson, J., Szilvasy, G., Mazar\u00e9, P., Lomeli, M., Hosseini, L., J\u00e9gou, H.: The faiss library. CoRR abs\/2401.08281 (2024)"},{"key":"13_CR21","unstructured":"Efremenko, K., Kontorovich, A., Noivirt, M.: Fast and bayes-consistent nearest neighbors. In: AISTATS. Proceedings of Machine Learning Research, vol.\u00a0108. PMLR, pp. 1276\u20131286 (2020)"},{"key":"13_CR22","doi-asserted-by":"crossref","unstructured":"Houle, M.E.: Dimensionality, discriminability, density and distance distributions. In: ICDM Workshops. IEEE Computer Society, pp. 468\u2013473 (2013)","DOI":"10.1109\/ICDMW.2013.139"},{"key":"13_CR23","doi-asserted-by":"crossref","unstructured":"Houle, M.E., Ma, X., Oria, V., Sun, J.: Query expansion for content-based similarity search using local and global features. ACM Trans. Multim. Comput. Commun. Appl. 13(3) (2017)","DOI":"10.1145\/3063595"},{"key":"13_CR24","doi-asserted-by":"crossref","unstructured":"Houle, M.E., Nett, M.: Rank cover trees for nearest neighbor search. In: SISAP (2013)","DOI":"10.1007\/978-3-642-41062-8_3"},{"issue":"46","key":"13_CR25","first-page":"1","volume":"25","author":"V Hyv\u00f6nen","year":"2024","unstructured":"Hyv\u00f6nen, V., J\u00e4\u00e4saari, E., Roos, T.: A multilabel classification framework for approximate nearest neighbor search. J. Mach. Learn. Res. 25(46), 1\u201351 (2024)","journal-title":"J. Mach. Learn. Res."},{"key":"13_CR26","unstructured":"Hyv\u00f6nen, V., J\u00e4\u00e4saari, E., Roos, T.: A multilabel classification framework for approximate nearest neighbor search. In: Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., Oh, A. (eds.) NeurIPS (2022)"},{"key":"13_CR27","doi-asserted-by":"crossref","unstructured":"Hyv\u00f6nen, V., Pitkanen, T., Tasoulis, S., J\u00e4\u00e4saari, E., Tuomainen, R., Wang, L., Corander, J., Roos, T.: Fast nearest neighbor search through sparse random projections and voting. In: Big Data 2016 (2016)","DOI":"10.1109\/BigData.2016.7840682"},{"key":"13_CR28","doi-asserted-by":"crossref","unstructured":"Indyk, P., Motwani, R.: Approximate nearest neighbors: towards removing the curse of dimensionality. In: STOC. ACM, pp. 604\u2013613 (1998)","DOI":"10.1145\/276698.276876"},{"key":"13_CR29","unstructured":"Iwasaki, M., Miyazaki, D.: Optimization of indexing based on k-nearest neigh-bor graph for proximity search in high-dimensional data. CoRR abs\/1810.07355 (2018)"},{"key":"13_CR30","unstructured":"Johnsen, M.H.: Helping out a neighbor: a study of partition-based algorithms for k-approximate nearest neighbor search. Master\u2019s thesis, ITU (2024)"},{"key":"13_CR31","doi-asserted-by":"crossref","unstructured":"Li, P., Hastie, T.J., Church, K.W.: Very sparse random projections. In: KDD (2006)","DOI":"10.1145\/1150402.1150436"},{"key":"13_CR32","unstructured":"Lv, Q., Josephson, W., Wang, Z., Charikar, M., Li, K.: Multi-probe LSH: efficient indexing for high-dimensional similarity search. In: VLDB. ACM (2007)"},{"issue":"4","key":"13_CR33","doi-asserted-by":"publisher","first-page":"824","DOI":"10.1109\/TPAMI.2018.2889473","volume":"42","author":"YA Malkov","year":"2020","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 (2020)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"13_CR34","doi-asserted-by":"crossref","unstructured":"Manohar, M.D., Shen, Z., Blelloch, G.E., Dhulipala, L., Gu, Y., Simhadri, H.V., Sun, Y.: Parlayann: Scalable and deterministic parallel graph-based approximate nearest neighbor search algorithms. In: PPoPP. ACM, pp. 270\u2013285 (2024)","DOI":"10.1145\/3627535.3638475"},{"key":"13_CR35","doi-asserted-by":"crossref","unstructured":"Paulev\u00e9, L., J\u00e9gou, H., Amsaleg, L.: Locality sensitive hashing: A comparison of hash function types and querying mechanisms. Pattern Recognit. Lett. 31(11) (2010)","DOI":"10.1016\/j.patrec.2010.04.004"},{"key":"13_CR36","unstructured":"Simhadri, H.V., Williams, G., Aum\u00fcller, M., Douze, M., Babenko, A., Baranchuk, D., Chen, Q., Hosseini, L., Krishnaswamy, R., Srinivasa, G., Subramanya, S.J., Wang, J.: Results of the NeurIPS\u201921 challenge on billion-scale approximate nearest neighbor search. In: NeurIPS (Competition and Demos) (2021)"},{"issue":"9","key":"13_CR37","doi-asserted-by":"publisher","first-page":"2604","DOI":"10.1109\/JPROC.2012.2193849","volume":"100","author":"M Slaney","year":"2012","unstructured":"Slaney, M., Lifshits, Y., He, J.: Optimal parameters for locality-sensitive hashing. Proc. IEEE 100(9), 2604\u20132623 (2012)","journal-title":"Proc. IEEE"},{"key":"13_CR38","unstructured":"Subramanya, S.J., Devvrit, Simhadri, H.V., Krishnaswamy, R., Kadekodi, R.: Rand-nsg: Fast accurate billion-point nearest neighbor search on a single node. In: NeurIPS (2019)"},{"key":"13_CR39","unstructured":"Sun, P., Simcha, D., Dopson, D., Guo, R., Kumar, S.: SOAR: improved indexing for approximate nearest neighbor search. In: NeurIPS (2023)"}],"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-031-75823-2_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,23]],"date-time":"2025-04-23T17:05:21Z","timestamp":1745427921000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-75823-2_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,25]]},"ISBN":["9783031758225","9783031758232"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-75823-2_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024,10,25]]},"assertion":[{"value":"25 October 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"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":"Providence, RI","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 November 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 November 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sisap2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.sisap.org\/2024\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}