{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:09Z","timestamp":1740109329221,"version":"3.37.3"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2022,8,24]],"date-time":"2022-08-24T00:00:00Z","timestamp":1661299200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,8,24]],"date-time":"2022-08-24T00:00:00Z","timestamp":1661299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Knowl Inf Syst"],"published-print":{"date-parts":[[2022,12]]},"DOI":"10.1007\/s10115-022-01742-0","type":"journal-article","created":{"date-parts":[[2022,8,24]],"date-time":"2022-08-24T19:36:36Z","timestamp":1661369796000},"page":"3325-3342","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A learned index for approximate kNN queries in high-dimensional spaces"],"prefix":"10.1007","volume":"64","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8898-5817","authenticated-orcid":false,"given":"Lingli","family":"Li","sequence":"first","affiliation":[]},{"given":"Jingwen","family":"Cai","sequence":"additional","affiliation":[]},{"given":"Jie","family":"Xu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,8,24]]},"reference":[{"issue":"8","key":"1742_CR1","first-page":"906","volume":"11","author":"A Arora","year":"2018","unstructured":"Arora A, Sinha S, Kumar P, Bhattacharya A (2018) Hd-index: pushing the scalability-accuracy boundary for approximate knn search in high-dimensional spaces. PVLDB 11(8):906\u2013919","journal-title":"PVLDB"},{"key":"1742_CR2","doi-asserted-by":"crossref","unstructured":"Beis JS, Lowe DG (1997) Shape indexing using approximate nearest-neighbour search in high-dimensional spaces. In: 1997 conference on computer vision and pattern recognition (CVPR \u201997), June 17\u201319, 1997, San Juan, Puerto Rico, pp 1000\u20131006. IEEE Computer Society","DOI":"10.1109\/CVPR.1997.609451"},{"issue":"9","key":"1742_CR3","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1145\/361002.361007","volume":"18","author":"Jon Louis Bentley","year":"1975","unstructured":"Jon Louis Bentley (1975) Multidimensional binary search trees used for associative searching. Commun ACM 18(9):509\u2013517","journal-title":"Commun ACM"},{"key":"1742_CR4","unstructured":"Ciaccia P, Patella M, and Pavel Zezula. (1997) M-tree An efficient access method for similarity search in metric spaces. In: VLDB\u201997, Proceedings of 23rd international conference on very large data bases, August 25\u201329, 1997, Athens, Greece, pp 426\u2013435. Morgan Kaufmann,"},{"key":"1742_CR5","doi-asserted-by":"crossref","unstructured":"Ding J, Minhas UF, Yu J, Wang C. ALEX: an updatable adaptive learned index. In: Proceedings of the 2020 international conference on management of data, SIGMOD Conference 2020, online conference [Portland, OR, USA], June 14\u201319, 2020, pp 969\u2013984. ACM, 2020","DOI":"10.1145\/3318464.3389711"},{"issue":"8","key":"1742_CR6","doi-asserted-by":"publisher","first-page":"1162","DOI":"10.14778\/3389133.3389135","volume":"13","author":"P Ferragina","year":"2020","unstructured":"Ferragina P, Vinciguerra G (2020) The pgm-index: a fully-dynamic compressed learned index with provable worst-case bounds. Proc VLDB Endow 13(8):1162\u20131175","journal-title":"Proc VLDB Endow"},{"key":"1742_CR7","unstructured":"Galakatos A, Markovitch M, Binnig C, Fonseca R, Kraska T. (2018) A-tree: a bounded approximate index structure. CoRR, abs\/1801.10207"},{"key":"1742_CR8","doi-asserted-by":"crossref","unstructured":"Galakatos A, Markovitch M, Binnig C, Fonseca R, Kraska T. (2019) Fiting-tree: a data-aware index structure. In: Proceedings of the 2019 international conference on management of data, SIGMOD Conference 2019, Amsterdam, The Netherlands, June 30\u2013July 5, 2019, pp 1189\u20131206. ACM,","DOI":"10.1145\/3299869.3319860"},{"issue":"12","key":"1742_CR9","doi-asserted-by":"publisher","first-page":"2916","DOI":"10.1109\/TPAMI.2012.193","volume":"35","author":"Y Gong","year":"2013","unstructured":"Gong Y, Lazebnik S, Gordo A, Perronnin F (2013) Iterative quantization: a procrustean approach to learning binary codes for large-scale image retrieval. IEEE Trans Pattern Anal Mach Intell 35(12):2916\u20132929","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"key":"1742_CR10","unstructured":"Hadian A, Kumar A, Heinis T (2020) Hands-off model integration in spatial index structures. In: AIDB@VLDB, (2020) 2nd International workshop on applied ai for database systems and applications, Held with VLDB 2020, Online Event \/ Tokyo, Japan, p 2020"},{"key":"1742_CR11","doi-asserted-by":"crossref","unstructured":"Hadjieleftheriou M, Manolopoulos Y, Theodoridis Y, Tsotras VJ (2017) R-trees: a dynamic index structure for spatial searching. In: Encyclopedia of GIS, pp 1805\u20131817. Springer","DOI":"10.1007\/978-3-319-17885-1_1151"},{"key":"1742_CR12","doi-asserted-by":"crossref","unstructured":"Indyk P and Motwani R (1998) Approximate nearest neighbors: towards removing the curse of dimensionality. In: Proceedings of the thirtieth annual ACM symposium on the theory of computing, Dallas, Texas, USA, May 23\u201326, 1998, pp 604\u2013613. ACM","DOI":"10.1145\/276698.276876"},{"key":"1742_CR13","doi-asserted-by":"crossref","unstructured":"Kipf A, Marcus R, van Renen A (2020) Radixspline: a single-pass learned index. In: Proceedings of the third international workshop on exploiting artificial intelligence techniques for data management, aiDM@SIGMOD 2020, Portland, Oregon, USA, June 19, 2020, pp 5:1\u20135:5. ACM","DOI":"10.1145\/3401071.3401659"},{"key":"1742_CR14","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.asoc.2019.03.031","volume":"79","author":"M Komorowski","year":"2019","unstructured":"Komorowski M, Trzcinski T (2019) Random binary search trees for approximate nearest neighbour search in binary spaces. Appl Soft Comput 79:87\u201393","journal-title":"Appl Soft Comput"},{"key":"1742_CR15","doi-asserted-by":"crossref","unstructured":"Kraska T, Beutel A, Chi EH, Dean J, Polyzotis N (2018) The case for learned index structures. In: Proceedings of the 2018 ACM SIGMOD international conference on management of data (SIGMOD), Houston, TX, USA, June 10-15, 2018, pp 489\u2013504","DOI":"10.1145\/3183713.3196909"},{"key":"1742_CR16","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1002\/nav.3800020109","volume":"2","author":"HW Kuhn","year":"1955","unstructured":"Kuhn HW (1955) The Hungarian method for the assignment problem. Naval Res Logist Q 2:83\u201397","journal-title":"Naval Res Logist Q"},{"key":"1742_CR17","doi-asserted-by":"crossref","unstructured":"Leibe B, Mikolajczyk K, Schiele B (2006) Efficient clustering and matching for object class recognition. In: Proceedings of the 2006 British Machine Vision Conference (BMVC), Edinburgh, UK, September 4\u20137, 2006, pp 789\u2013798","DOI":"10.5244\/C.20.81"},{"key":"1742_CR18","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/s10115-020-01518-4","volume":"63","author":"O Levchenko","year":"2021","unstructured":"Levchenko O, Kolev B, Yagoubi DE, Akbarinia R, Masseglia F, Palpanas T, Shasha D, Valduriez Patrick (2021) Bestneighbor: efficient evaluation of knn queries on large time series databases. Knowl Inf Syst 63:349\u2013378","journal-title":"Knowl Inf Syst"},{"key":"1742_CR19","doi-asserted-by":"publisher","first-page":"876","DOI":"10.1016\/j.ins.2021.10.027","volume":"581","author":"L Li","year":"2021","unstructured":"Li L, Jie X, Li Yu, Cai J (2021) Hctree+: a workload-guided index for approximate knn search. Inf Sci 581:876\u2013890","journal-title":"Inf Sci"},{"key":"1742_CR20","unstructured":"Lv Q, Josephson W, Wang Z, Charikar M, Li K (2007) Multi-probe LSH: efficient indexing for high-dimensional similarity search. In: Proceedings of the 2007 international conference on very large data bases (VLDB), University of Vienna, Austria, September 23-27, 2007, pp 950\u2013961"},{"key":"1742_CR21","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.is.2013.10.006","volume":"45","author":"Y Malkov","year":"2014","unstructured":"Malkov Y, Ponomarenko A, Logvinov A, Krylov V (2014) Approximate nearest neighbor algorithm based on navigable small world graphs. Inf Syst 45:61\u201368","journal-title":"Inf Syst"},{"issue":"4","key":"1742_CR22","doi-asserted-by":"publisher","first-page":"824","DOI":"10.1109\/TPAMI.2018.2889473","volume":"42","author":"YA Malkov","year":"2020","unstructured":"Malkov YA, Yashunin DA (2020) Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Trans Pattern Anal Mach Intell 42(4):824\u2013836","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"issue":"1","key":"1742_CR23","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1137\/0105003","volume":"5","author":"J Munkres","year":"1957","unstructured":"Munkres J (1957) Algorithms for the assignment and transportation problems. J Soc Ind Appl Math 5(1):32\u201338","journal-title":"J Soc Ind Appl Math"},{"key":"1742_CR24","doi-asserted-by":"crossref","unstructured":"Nathan V, Ding J, Alizadeh M, Kraska T (2020) Learning multi-dimensional indexes. In: Proceedings of the 2020 international conference on management of data, SIGMOD Conference 2020, online conference [Portland, OR, USA], June 14\u201319, 2020, pp 985\u20131000","DOI":"10.1145\/3318464.3380579"},{"key":"1742_CR25","unstructured":"Sakurai Y, Yoshikawa M, Uemura S, Kojima H (2000) The a-tree: an index structure for high-dimensional spaces using relative approximation. In: VLDB 2000, pp 516\u2013526. Morgan Kaufmann"},{"issue":"5","key":"1742_CR26","doi-asserted-by":"publisher","first-page":"430","DOI":"10.14778\/2140436.2140440","volume":"5","author":"V Satuluri","year":"2012","unstructured":"Satuluri V, Parthasarathy S (2012) Bayesian locality sensitive hashing for fast similarity search. Proc VLDB Endow 5(5):430\u2013441","journal-title":"Proc VLDB Endow"},{"key":"1742_CR27","doi-asserted-by":"crossref","unstructured":"Silpa-Anan C, Hartley RI (2008) Optimised kd-trees for fast image descriptor matching. In: 2008 IEEE computer society conference on computer vision and pattern recognition (CVPR 2008), 24\u201326 June 2008, Anchorage, Alaska, USA","DOI":"10.1109\/CVPR.2008.4587638"},{"issue":"1","key":"1742_CR28","first-page":"1","volume":"8","author":"Y Sun","year":"2014","unstructured":"Sun Y, Wang W, Qin J, Zhang Y, Lin X (2014) SRS: solving c-approximate nearest neighbor queries in high dimensional euclidean space with a tiny index. PVLDB 8(1):1\u201312","journal-title":"PVLDB"},{"key":"1742_CR29","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1016\/j.asoc.2016.08.021","volume":"49","author":"L Wang","year":"2016","unstructured":"Wang L, Zhong Y, Yin Y (2016) Nearest neighbour cuckoo search algorithm with probabilistic mutation. Appl Soft Comput 49:498\u2013509","journal-title":"Appl Soft Comput"},{"issue":"10","key":"1742_CR30","doi-asserted-by":"publisher","first-page":"793","DOI":"10.14778\/2536206.2536208","volume":"6","author":"Y Wang","year":"2013","unstructured":"Wang Y, Wang P, Pei J, Wang W, Huang S (2013) A data-adaptive and dynamic segmentation index for whole matching on time series. Proc VLDB Endow 6(10):793\u2013804","journal-title":"Proc VLDB Endow"},{"key":"1742_CR31","doi-asserted-by":"crossref","unstructured":"Wu Y, Yu J, Tian Y (2019) Designing succinct secondary indexing mechanism by exploiting column correlations. In: SIGMOD Conference 2019, Amsterdam, The Netherlands, June 30\u2013July 5, 2019, pp 1223\u20131240. ACM,","DOI":"10.1145\/3299869.3319861"},{"key":"1742_CR32","doi-asserted-by":"crossref","unstructured":"Wu Y, Jin R, Zhang X (2014) Fast and unified local search for random walk based k-nearest-neighbor query in large graphs. In: Proceedings of the 2014 ACM SIGMOD international conference on management of data (SIGMOD), Snowbird, UT, USA, June 22-27, 2014, pp 1139\u20131150","DOI":"10.1145\/2588555.2610500"},{"issue":"5","key":"1742_CR33","first-page":"643","volume":"13","author":"B Zheng","year":"2020","unstructured":"Zheng B, Zhao X, Weng L, Hung NQ, Liu H, Jensen CS (2020) PM-LSH: a fast and accurate LSH framework for high-dimensional approximate NN search. PVLDB 13(5):643\u2013655","journal-title":"PVLDB"}],"container-title":["Knowledge and Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-022-01742-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10115-022-01742-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-022-01742-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,2]],"date-time":"2024-10-02T14:18:01Z","timestamp":1727878681000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10115-022-01742-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,24]]},"references-count":33,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["1742"],"URL":"https:\/\/doi.org\/10.1007\/s10115-022-01742-0","relation":{},"ISSN":["0219-1377","0219-3116"],"issn-type":[{"type":"print","value":"0219-1377"},{"type":"electronic","value":"0219-3116"}],"subject":[],"published":{"date-parts":[[2022,8,24]]},"assertion":[{"value":"2 August 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 August 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 August 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 August 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}