{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:22Z","timestamp":1740109342111,"version":"3.37.3"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2023,5,19]],"date-time":"2023-05-19T00:00:00Z","timestamp":1684454400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,5,19]],"date-time":"2023-05-19T00:00:00Z","timestamp":1684454400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62002274","61902299","61976168"],"award-info":[{"award-number":["62002274","61902299","61976168"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002858","name":"China Postdoctoral Science Foundation","doi-asserted-by":"publisher","award":["2019TQ0239","2019M663636"],"award-info":[{"award-number":["2019TQ0239","2019M663636"]}],"id":[{"id":"10.13039\/501100002858","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012226","name":"Fundamental Research Funds for the Central Universities","doi-asserted-by":"publisher","award":["XJS210303"],"award-info":[{"award-number":["XJS210303"]}],"id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Knowl Inf Syst"],"published-print":{"date-parts":[[2023,10]]},"DOI":"10.1007\/s10115-023-01899-2","type":"journal-article","created":{"date-parts":[[2023,5,19]],"date-time":"2023-05-19T08:01:53Z","timestamp":1684483313000},"page":"4185-4212","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Accelerating massive queries of approximate nearest neighbor search on high-dimensional data"],"prefix":"10.1007","volume":"65","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3743-5249","authenticated-orcid":false,"given":"Yingfan","family":"Liu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chaowei","family":"Song","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hong","family":"Cheng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaofang","family":"Xia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiangtao","family":"Cui","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,5,19]]},"reference":[{"issue":"1","key":"1899_CR1","first-page":"1","volume":"8","author":"Y Sun","year":"2015","unstructured":"Sun Y, Wang W, Qin J, Zhang Y, Lin X (2015) SRS: solving c-approximate nearest neighbor queries in high dimensional Euclidean space with a tiny index. PVLDB 8(1):1\u201312","journal-title":"PVLDB"},{"issue":"1","key":"1899_CR2","first-page":"1","volume":"9","author":"Q Huang","year":"2016","unstructured":"Huang Q, Feng J, Zhang Y, Fang Q, Ng W (2016) Query-aware locality-sensitive hashing for approximate nearest neighbor search. PVLDB 9(1):1\u201312","journal-title":"PVLDB"},{"issue":"11","key":"1899_CR3","doi-asserted-by":"publisher","first-page":"2227","DOI":"10.1109\/TPAMI.2014.2321376","volume":"36","author":"M Muja","year":"2014","unstructured":"Muja M, Lowe DG (2014) Scalable nearest neighbor algorithms for high dimensional data. IEEE Trans Pattern Anal Mach Intell 36(11):2227\u20132240","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"issue":"1","key":"1899_CR4","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1109\/TPAMI.2010.57","volume":"33","author":"H Jegou","year":"2011","unstructured":"Jegou H, Douze M, Schmid C (2011) Product quantization for nearest neighbor search. IEEE Trans Pattern Anal Mach Intell 33(1):117\u2013128","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"issue":"6","key":"1899_CR5","doi-asserted-by":"publisher","first-page":"1247","DOI":"10.1109\/TPAMI.2014.2361319","volume":"37","author":"A Babenko","year":"2014","unstructured":"Babenko A, Lempitsky V (2014) The inverted multi-index. IEEE Trans Pattern Anal Mach Intell 37(6):1247\u20131260","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"key":"1899_CR6","unstructured":"https:\/\/github.com\/spotify\/annoy"},{"key":"1899_CR7","unstructured":"https:\/\/github.com\/searchivarius\/nmslib"},{"key":"1899_CR8","doi-asserted-by":"publisher","first-page":"1475","DOI":"10.1109\/TKDE.2019.2909204","volume":"32","author":"W Li","year":"2019","unstructured":"Li W, Zhang Y, Sun Y, Wang W, Li M, Zhang W, Lin X (2019) Approximate nearest neighbor search on high dimensional data\u2014experiments, analyses, and improvement. IEEE Trans Knowl Data Eng 32:1475\u20131488","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"1899_CR9","doi-asserted-by":"publisher","first-page":"824","DOI":"10.1109\/TPAMI.2018.2889473","volume":"42","author":"Y Malkov","year":"2018","unstructured":"Malkov Y, Yashunin D (2018) Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Trans Pattern Anal Mach Intell 42:824\u2013836","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"issue":"5","key":"1899_CR10","first-page":"461","volume":"12","author":"C Fu","year":"2019","unstructured":"Fu C, Xiang C, Wang C, Cai D (2019) Fast approximate nearest neighbor search with the navigating spreading-out graph. PVLDB 12(5):461\u2013474","journal-title":"PVLDB"},{"key":"1899_CR11","doi-asserted-by":"crossref","unstructured":"Baranchuk D, Babenko A, Malkov Y (2018) Revisiting the inverted indices for billion-scale approximate nearest neighbors. In: ECCV, pp 202\u2013216","DOI":"10.1007\/978-3-030-01258-8_13"},{"issue":"6","key":"1899_CR12","doi-asserted-by":"publisher","first-page":"728","DOI":"10.1007\/s10115-003-0122-9","volume":"6","author":"C B\u00f6hm","year":"2004","unstructured":"B\u00f6hm C, Krebs F (2004) The k-nearest neighbour join: turbo charging the KDD process. Knowl Inf Syst 6(6):728\u2013749","journal-title":"Knowl Inf Syst"},{"key":"1899_CR13","doi-asserted-by":"crossref","unstructured":"Dong W, Moses C, Li K (2011) Efficient k-nearest neighbor graph construction for generic similarity measures. In: Proceedings of the 20th international conference on world wide web, pp 577\u2013586","DOI":"10.1145\/1963405.1963487"},{"key":"1899_CR14","unstructured":"Liu Y, Cheng H, Cui J (2021) Revisiting k-nearest neighbor graph construction on high-dimensional data: experiments and analyses. arXiv Preprint arXiv:2112.02234"},{"issue":"4","key":"1899_CR15","first-page":"449","volume":"8","author":"M Then","year":"2014","unstructured":"Then M, Kaufmann M, Chirigati F, Hoang-Vu T-A, Pham K, Kemper A, Neumann T, Vo HT (2014) The more the merrier: efficient multi-source graph traversal. PVLDB 8(4):449\u2013460","journal-title":"PVLDB"},{"key":"1899_CR16","doi-asserted-by":"crossref","unstructured":"Dong W, Moses C, Li K (2011) Efficient k-nearest neighbor graph construction for generic similarity measures. In: WWW, pp 577\u2013586","DOI":"10.1145\/1963405.1963487"},{"key":"1899_CR17","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":"9","key":"1899_CR18","first-page":"1989","volume":"10","author":"J Chen","year":"2009","unstructured":"Chen J, Fang HR, Saad Y (2009) Fast approximate kNN graph construction for high dimensional data via recursive Lanczos bisection. J Mach Learn Res 10(9):1989\u20132012","journal-title":"J Mach Learn Res"},{"issue":"9","key":"1899_CR19","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1145\/361002.361007","volume":"18","author":"JL Bentley","year":"1975","unstructured":"Bentley JL (1975) Multidimensional binary search trees used for associative searching. Commun ACM 18(9):509\u2013517","journal-title":"Commun ACM"},{"key":"1899_CR20","doi-asserted-by":"crossref","unstructured":"Guttman A (1984) R-trees: a dynamic index structure for spatial searching. In: SIGMOD, pp 47\u201357","DOI":"10.1145\/971697.602266"},{"key":"1899_CR21","unstructured":"Berchtold S, Keim DA, Kriegel H-P (1996) The X-tree: an index structure for high-dimensional data. In: VLDB, pp 28\u201339"},{"issue":"2","key":"1899_CR22","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1145\/1071610.1071612","volume":"30","author":"HV Jagadish","year":"2005","unstructured":"Jagadish HV, Ooi BC, Tan KL, Yu C, Zhang R (2005) iDistance: an adaptive B$$^+$$-tree based indexing method for nearest neighbor search. ACM Trans Database Syst 30(2):364\u2013397","journal-title":"ACM Trans Database Syst"},{"key":"1899_CR23","doi-asserted-by":"crossref","unstructured":"Tao Y, Yi K, Sheng C, Kalnis P (2009) Quality and efficiency in high dimensional nearest neighbor search. In: SIGMOD, pp 563\u2013576","DOI":"10.1145\/1559845.1559905"},{"key":"1899_CR24","doi-asserted-by":"crossref","unstructured":"Gan J, Feng J, Fang Q, Ng W (2012) Locality sensitive hashing scheme based on dynamic collision counting. In: SIGMOD, pp 541\u2013552","DOI":"10.1145\/2213836.2213898"},{"issue":"9","key":"1899_CR25","first-page":"745","volume":"7","author":"Y Liu","year":"2014","unstructured":"Liu Y, Cui J, Huang Z, Li H, shen H (2014) SK-LSH\u202f: an efficient index structure for approximate nearest neighbor search. PVLDB 7(9):745\u2013756","journal-title":"PVLDB"},{"key":"1899_CR26","doi-asserted-by":"crossref","unstructured":"Uribe-Paredes R, Valero-Lara P, Arias E, S\u00e1nchez JL, Cazorla D (2011) Similarity search implementations for multi-core and many-core processors. In: HPCS. IEEE, pp 656\u2013663","DOI":"10.1109\/HPCSim.2011.5999889"},{"issue":"5","key":"1899_CR27","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1007\/s10766-013-0239-8","volume":"41","author":"B Gedik","year":"2013","unstructured":"Gedik B (2013) Auto-tuning similarity search algorithms on multi-core architectures. Int J Parallel Prog 41(5):595\u2013620","journal-title":"Int J Parallel Prog"},{"key":"1899_CR28","unstructured":"Gieseke F, Heinermann J, Oancea C, Igel C (2014) Buffer kd trees: processing massive nearest neighbor queries on GPUs. In: ICML, pp 172\u2013180"},{"issue":"10","key":"1899_CR29","doi-asserted-by":"publisher","first-page":"1388","DOI":"10.1109\/TC.2018.2823760","volume":"67","author":"M Kim","year":"2018","unstructured":"Kim M, Liu L, Choi W (2018) A GPU-aware parallel index for processing high-dimensional big data. IEEE Trans Comput 67(10):1388\u20131402","journal-title":"IEEE Trans Comput"},{"key":"1899_CR30","doi-asserted-by":"crossref","unstructured":"Kim J, Hong S, Nam B (2012) A performance study of traversing spatial indexing structures in parallel on GPU. In: HPCC. IEEE, pp 855\u2013860","DOI":"10.1109\/HPCC.2012.121"},{"key":"1899_CR31","doi-asserted-by":"crossref","unstructured":"Pan J, Manocha D (2011) Fast GPU-based locality sensitive hashing for k-nearest neighbor computation. In: SIGSPATIAL GIS, pp 211\u2013220","DOI":"10.1145\/2093973.2094002"},{"key":"1899_CR32","doi-asserted-by":"crossref","unstructured":"Pan J, Manocha D (2012) Bi-level locality sensitive hashing for k-nearest neighbor computation. In: ICDE. IEEE, pp 378\u2013389","DOI":"10.1109\/ICDE.2012.40"},{"key":"1899_CR33","doi-asserted-by":"crossref","unstructured":"Matsumoto T, Yiu ML (2015) Accelerating exact similarity search on CPU-GPU systems. In: ICDM. IEEE, pp 320\u2013329","DOI":"10.1109\/ICDM.2015.125"},{"key":"1899_CR34","doi-asserted-by":"crossref","unstructured":"Wang Y, Shrivastava A, Wang J, Ryu J (2018) FLASH: randomized algorithms accelerated over CPU-GPU for ultra-high dimensional similarity search. In: SIGMOD, pp 889\u2013903","DOI":"10.1145\/3183713.3196925"},{"key":"1899_CR35","doi-asserted-by":"crossref","unstructured":"Xia C, Lu H, Ooi BC, Hu J (2004) Gorder: an efficient method for KNN join processing. In: VLDB, pp 756\u2013767","DOI":"10.1016\/B978-012088469-8\/50067-X"},{"issue":"4","key":"1899_CR36","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1016\/j.infsof.2006.05.006","volume":"49","author":"C Yu","year":"2007","unstructured":"Yu C, Cui B, Wang S, Su J (2007) Efficient index-based KNN join processing for high-dimensional data. Inf Softw Technol 49(4):332\u2013344","journal-title":"Inf Softw Technol"},{"issue":"2","key":"1899_CR37","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1145\/1071610.1071612","volume":"30","author":"HV Jagadish","year":"2005","unstructured":"Jagadish HV, Ooi BC, Tan KL, Yu C, Zhang R (2005) iDistance: an adaptive B$$^+$$-tree based indexing method for nearest neighbor search. ACM Trans Database Syst 30(2):364\u2013397","journal-title":"ACM Trans Database Syst"},{"key":"1899_CR38","doi-asserted-by":"crossref","unstructured":"Yao B, Li F, Kumar P (2010) K nearest neighbor queries and KNN-joins in large relational databases (almost) for free. In: ICDE, pp 4\u201315","DOI":"10.1109\/ICDE.2010.5447837"},{"key":"1899_CR39","doi-asserted-by":"crossref","unstructured":"Lu W, Shen Y, Chen S, Ooi B (2012) Efficient processing of k nearest neighbor joins using mapreduce, pp 1016\u20131027","DOI":"10.14778\/2336664.2336674"},{"key":"1899_CR40","doi-asserted-by":"crossref","unstructured":"Zhang C, Li F, Jestes J (2012) Efficient parallel KNN joins for large data in MapReduce. In: EDBT, pp 38\u201349","DOI":"10.1145\/2247596.2247602"},{"key":"1899_CR41","unstructured":"Bader DA, Madduri K (2006) Designing multithreaded algorithms for breadth-first search and st-connectivity on the cray MTA-2. In: ICPP, pp 523\u2013530"},{"key":"1899_CR42","doi-asserted-by":"crossref","unstructured":"Chhugani J, Satish N, Kim C, Sewall J, Dubey P (2012) Fast and efficient graph traversal algorithm for CPUs: maximizing single-node efficiency. In: IPDPS, pp 378\u2013389","DOI":"10.1109\/IPDPS.2012.43"},{"key":"1899_CR43","doi-asserted-by":"crossref","unstructured":"Liu H, Huang HH, Hu Y (2016) iBFS: concurrent breadth-first search on GPUs. In: SIGMOD, pp 403\u2013416","DOI":"10.1145\/2882903.2882959"},{"key":"1899_CR44","doi-asserted-by":"crossref","unstructured":"Wei H, Yu JX, Lu C, Lin X (2016) Speedup graph processing by graph ordering. In: SIGMOD, pp 1813\u20131828","DOI":"10.1145\/2882903.2915220"}],"container-title":["Knowledge and Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-023-01899-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10115-023-01899-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-023-01899-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,22]],"date-time":"2023-08-22T17:09:34Z","timestamp":1692724174000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10115-023-01899-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,19]]},"references-count":44,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2023,10]]}},"alternative-id":["1899"],"URL":"https:\/\/doi.org\/10.1007\/s10115-023-01899-2","relation":{},"ISSN":["0219-1377","0219-3116"],"issn-type":[{"type":"print","value":"0219-1377"},{"type":"electronic","value":"0219-3116"}],"subject":[],"published":{"date-parts":[[2023,5,19]]},"assertion":[{"value":"5 January 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 April 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 April 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 May 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}