{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,26]],"date-time":"2025-04-26T05:28:39Z","timestamp":1745645319381,"version":"3.37.3"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"22","license":[{"start":{"date-parts":[[2022,5,2]],"date-time":"2022-05-02T00:00:00Z","timestamp":1651449600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,5,2]],"date-time":"2022-05-02T00:00:00Z","timestamp":1651449600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100004731","name":"Natural Science Foundation of Zhejiang Province","doi-asserted-by":"publisher","award":["LY16F020026"],"award-info":[{"award-number":["LY16F020026"]}],"id":[{"id":"10.13039\/501100004731","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61522208, 61379033"],"award-info":[{"award-number":["61522208, 61379033"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Soft Comput"],"published-print":{"date-parts":[[2022,11]]},"DOI":"10.1007\/s00500-022-07081-0","type":"journal-article","created":{"date-parts":[[2022,5,2]],"date-time":"2022-05-02T16:03:22Z","timestamp":1651507402000},"page":"12291-12316","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Efficient parallel processing of high-dimensional spatial kNN queries"],"prefix":"10.1007","volume":"26","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0740-5962","authenticated-orcid":false,"given":"Tao","family":"Jiang","sequence":"first","affiliation":[]},{"given":"Bin","family":"Zhang","sequence":"additional","affiliation":[]},{"given":"Dan","family":"Lin","sequence":"additional","affiliation":[]},{"given":"Yunjun","family":"Gao","sequence":"additional","affiliation":[]},{"given":"Qing","family":"Li","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,5,2]]},"reference":[{"issue":"6","key":"7081_CR1","doi-asserted-by":"publisher","first-page":"973","DOI":"10.1016\/j.is.2011.03.010","volume":"36","author":"R Akbarinia","year":"2011","unstructured":"Akbarinia R, Pacitti E, Valduriez P (2011) Best position algorithms for efficient top-k query processing. Inf Syst 36(6):973\u2013989","journal-title":"Inf Syst"},{"issue":"2","key":"7081_CR2","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/s10619-004-0234-6","volume":"17","author":"MH Ali","year":"2005","unstructured":"Ali MH, Saad AA, Ismail MA (2005) The PN-tree: a parallel and distributed multidimensional index. Distrib Parallel Databases 17(2):111\u2013133","journal-title":"Distrib Parallel Databases"},{"issue":"2","key":"7081_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/253262.253263","volume":"26","author":"S Berchtold","year":"1997","unstructured":"Berchtold S, Bohm C, Braunmuller B, Keim DA, Kriegel HP (1997) Fast parallel similarity search in multimedia databases. SIGMOD Rec 26(2):1\u201312","journal-title":"SIGMOD Rec"},{"key":"7081_CR4","doi-asserted-by":"publisher","first-page":"72939","DOI":"10.1109\/ACCESS.2018.2879337","volume":"6","author":"M Cao","year":"2018","unstructured":"Cao M, Jia W, Lv Z et al (2018) Two-pass k nearest neighbor search for feature tracking. IEEE Access 6:72939\u201372951","journal-title":"IEEE Access"},{"key":"7081_CR5","doi-asserted-by":"publisher","first-page":"55248","DOI":"10.1109\/ACCESS.2019.2912647","volume":"7","author":"M Cao","year":"2019","unstructured":"Cao M, Li L, Xie W et al (2019) Parallel k nearest neighbor matching for 3D reconstruction. IEEE Access 7:55248\u201355260","journal-title":"IEEE Access"},{"key":"7081_CR6","doi-asserted-by":"crossref","unstructured":"Challa JS, Goyal P, Nikhil S, Balasubramaniam S, Goyal N (2015) A concurrent k-NN search algorithm for R-tree. In: Proceeding annual ACM India conference, pp. 123\u2013128.","DOI":"10.1145\/2835043.2835050"},{"key":"7081_CR7","doi-asserted-by":"crossref","unstructured":"Chester S, Sidlauskas D, Assent I et al. (2015) Scalable parallelization of skyline computation for multi-core processors. In: ICDE, pp. 1083\u20131094","DOI":"10.1109\/ICDE.2015.7113358"},{"issue":"1","key":"7081_CR8","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1145\/1327452.1327492","volume":"51","author":"J Dean","year":"2008","unstructured":"Dean J, Ghemawat S (2008) MapReduce: simplified data processing on large clusters. Commun ACM 51(1):107\u2013113","journal-title":"Commun ACM"},{"key":"7081_CR9","doi-asserted-by":"crossref","unstructured":"Ouyang D, Wen D, Qin L et al. (2020) Progressive top-K nearest neighbors search in large road networks. In: SIGMOD, pp. 1781\u20131795.","DOI":"10.1145\/3318464.3389746"},{"issue":"1","key":"7081_CR10","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1006\/jcss.1998.1600","volume":"58","author":"R Fagin","year":"1999","unstructured":"Fagin R (1999) Combining fuzzy information from multiple systems. J Comput Syst Sci 58(1):83\u201399","journal-title":"J Comput Syst Sci"},{"issue":"4","key":"7081_CR11","doi-asserted-by":"publisher","first-page":"614","DOI":"10.1016\/S0022-0000(03)00026-6","volume":"66","author":"R Fagin","year":"2003","unstructured":"Fagin R, Lotem J, Naor M (2003) Optimal aggregation algorithms for middleware. J Comput Syst Sci 66(4):614\u2013656","journal-title":"J Comput Syst Sci"},{"key":"7081_CR12","first-page":"827","volume":"7808","author":"X Feng","year":"2013","unstructured":"Feng X, Gao Y, Jiang T et al (2013) Parallel k-Skyband computation on multicore architecture. LNCS 7808:827\u2013837","journal-title":"LNCS"},{"key":"7081_CR13","first-page":"39","volume":"3984","author":"Y Gao","year":"2006","unstructured":"Gao Y, Chen L, Chen G, Chen C (2006) Efficient parallel processing for k-nearest-neighbor search in spatial databases. LNCS 3984:39\u201348","journal-title":"LNCS"},{"key":"7081_CR14","unstructured":"Gieseke F, Heinermann J, Oancea C, Igel C (2014) Buffer k-d trees: processing massive nearest neighbor queries on GPUs. In: Proceeding. of international conference on machine learning, pp. 1\u20139"},{"key":"7081_CR15","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/j.jpdc.2020.11.004","volume":"149","author":"M Gowanlock","year":"2021","unstructured":"Gowanlock M (2021) Hybrid KNN-join: parallel nearest neighbor searches exploiting CPU and GPU architectural features. J Parallel Distrib Comput 149:119\u2013137","journal-title":"J Parallel Distrib Comput"},{"key":"7081_CR16","first-page":"26","volume":"14","author":"G Guzun","year":"2014","unstructured":"Guzun G, Tosado J, Canahuate G (2014) Slicing the dimensionality: top-k query processing for high-dimensional spaces. Trans Large Scale Data Knowl Centered Syst 14:26\u201350","journal-title":"Trans Large Scale Data Knowl Centered Syst"},{"issue":"10","key":"7081_CR17","doi-asserted-by":"publisher","first-page":"2687","DOI":"10.1109\/TKDE.2015.2426691","volume":"27","author":"X Han","year":"2015","unstructured":"Han X, Li J, Gao H (2015) Efficient top-k retrieval on massive data. IEEE Trans Knowl Data Eng 27(10):2687\u20132699","journal-title":"IEEE Trans Knowl Data Eng"},{"issue":"2","key":"7081_CR18","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1145\/320248.320255","volume":"24","author":"GR Hjaltason","year":"1999","unstructured":"Hjaltason GR, Samet H (1999) Distance browsing in spatial databases. ACM Trans Database Syst 24(2):265\u2013318","journal-title":"ACM Trans Database Syst"},{"issue":"2","key":"7081_CR19","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 K-L et al (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"},{"issue":"4","key":"7081_CR20","doi-asserted-by":"publisher","first-page":"1885","DOI":"10.1016\/j.eswa.2013.08.085","volume":"41","author":"T Jiang","year":"2014","unstructured":"Jiang T, Gao Y, Zhang B, Lin D, Li Q (2014) Monochromatic and bichromatic mutual skyline queries. Expert Syst Appl 41(4):1885\u20131900","journal-title":"Expert Syst Appl"},{"key":"7081_CR21","doi-asserted-by":"crossref","unstructured":"Jiang T, Zhang B, Yu F (2017) Efficient parallel processing for kNN queries. In: ICIDE, pp. 88\u201394","DOI":"10.1145\/3178264.3178289"},{"key":"7081_CR22","doi-asserted-by":"crossref","unstructured":"Jin W, Patel JM (2011) Efficient and generic evaluation of ranked queries. In: SIGMOD, pp. 601\u2013612","DOI":"10.1145\/1989323.1989386"},{"key":"7081_CR23","doi-asserted-by":"publisher","first-page":"1347","DOI":"10.1109\/TVCG.2018.2869149","volume":"26","author":"J Jo","year":"2020","unstructured":"Jo J, Seo J, Fekete JD (2020) PANENE: a progressive algorithm for indexing and querying approximate k-nearest neighbors. IEEE Trans Vis Comput Graph 26(2):1347\u20131360","journal-title":"IEEE Trans Vis Comput Gr"},{"issue":"12","key":"7081_CR24","doi-asserted-by":"publisher","first-page":"3103","DOI":"10.1109\/TKDE.2013.149","volume":"26","author":"J Lee","year":"2014","unstructured":"Lee J, Cho H, Hwang S et al (2014) Toward scalable indexing for top-k queries. IEEE Trans Knowl Data Eng 26(12):3103\u20133116","journal-title":"IEEE Trans Knowl Data Eng"},{"issue":"8","key":"7081_CR25","doi-asserted-by":"publisher","first-page":"1475","DOI":"10.1109\/TKDE.2019.2909204","volume":"32","author":"W Li","year":"2020","unstructured":"Li W, Zhang Y, Sun Y et al (2020c) Approximate nearest neighbor search on high dimensional data\u2014experiments, analyses, and improvement. IEEE Trans Knowl Data Eng 32(8):1475\u20131488","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"7081_CR26","doi-asserted-by":"crossref","unstructured":"Li M, Zhang Y, Sun Y et al. (2020a) I\/O efficient approximate nearest neighbor search based on learned functions. In: ICDE, pp. 289\u2013300","DOI":"10.1109\/ICDE48307.2020.00032"},{"key":"7081_CR27","doi-asserted-by":"crossref","unstructured":"Li C, Zhang M, Andersen DG et al. (2020b) Improving approximate nearest neighbor search through learned adaptive early termination. In: SIGMOD, pp. 2539\u20132554","DOI":"10.1145\/3318464.3380600"},{"issue":"9","key":"7081_CR28","first-page":"1443","volume":"13","author":"K Lu","year":"2020","unstructured":"Lu K, Wang H, Wang W, Kudo M (2020) VHP: approximate nearest neighbor search via virtual hypersphere partitioning. PVLDB 13(9):1443\u20131455","journal-title":"PVLDB"},{"issue":"2","key":"7081_CR29","doi-asserted-by":"publisher","first-page":"246","DOI":"10.14778\/3489496.3489506","volume":"15","author":"K Lu","year":"2021","unstructured":"Lu K, Kudo M, Xiao C et al (2021) HVS: hierarchical graph structure based on voronoi diagrams for solving approximate nearest neighbor search. Proc VLDB Endow 15(2):246\u2013258","journal-title":"Proc VLDB Endow"},{"key":"7081_CR30","doi-asserted-by":"crossref","unstructured":"Maillo J, Triguero I, Herrera F (2015) A MapReduce-based k-nearest neighbor approach for big data classification. In: Proceeding IEEE BigDataSE, pp. 167\u2013172","DOI":"10.1109\/Trustcom.2015.577"},{"key":"7081_CR31","doi-asserted-by":"publisher","first-page":"824","DOI":"10.1109\/TPAMI.2018.2889473","volume":"42","author":"YuA Malkov","year":"2020","unstructured":"Malkov YuA, Yashunin DA (2020) 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"},{"key":"7081_CR32","doi-asserted-by":"publisher","first-page":"106970","DOI":"10.1016\/j.patcog.2019.106970","volume":"96","author":"JV Mu\u00f1oz","year":"2019","unstructured":"Mu\u00f1oz JV, Gon\u00e7alves MA, Dias Z et al (2019) Hierarchical clustering-based graphs for large scale approximate nearest neighbor search. Pattern Recognit 96:106970","journal-title":"Pattern Recognit"},{"key":"7081_CR33","doi-asserted-by":"crossref","unstructured":"Nam M, Kim J, Nam B (2016) Parallel tree traversal for nearest neighbor query on the GPU. In: ICPP, pp. 113\u2013122","DOI":"10.1109\/ICPP.2016.20"},{"key":"7081_CR34","doi-asserted-by":"crossref","unstructured":"Pan J, Manocha D (2011) Fast GPU-based locality sensitive hashing for k-nearest neighbor computation. In: ACM SIGSPATIAL, pp. 211\u2013220","DOI":"10.1145\/2093973.2094002"},{"key":"7081_CR35","doi-asserted-by":"crossref","unstructured":"Papadopoulos AN, Manolopoulos Y (1996) Parallel processing of nearest neighbor queries in declustered spatial data. In: Proceeding ACM-GIS conference, pp. 35\u201343","DOI":"10.1145\/258319.258330"},{"key":"7081_CR36","doi-asserted-by":"crossref","unstructured":"Papadopoulos AN, Manolopoulos Y (1998) Similarity query processing using disk arrays. In: SIGMOD, pp. 225\u2013236","DOI":"10.1145\/276305.276325"},{"key":"7081_CR37","doi-asserted-by":"crossref","unstructured":"Patwary MMA, Satish NR, Sundaram N et al. (2016) PANDA: extreme scale parallel k-nearest neighbor on distributed architectures. In: IPDPS, pp. 494\u2013503","DOI":"10.1109\/IPDPS.2016.57"},{"key":"7081_CR38","doi-asserted-by":"crossref","unstructured":"Ram P, Sinha K (2019) Revisiting kd-tree for nearest neighbor search. In: SIGKDD, pp. 1378\u20131388","DOI":"10.1145\/3292500.3330875"},{"issue":"2","key":"7081_CR39","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1145\/568271.223794","volume":"24","author":"N Roussopoulos","year":"1995","unstructured":"Roussopoulos N, Kelley S, Vincent F (1995) Nearest neighbor queries. ACM SIGMOD Rec 24(2):71\u201379","journal-title":"ACM SIGMOD Rec"},{"key":"7081_CR40","doi-asserted-by":"crossref","unstructured":"Shahvarani A, Jacobsen HA (2021) Distributed stream KNN join. In: SIGMOD conference, pp. 1597\u20131609","DOI":"10.1145\/3448016.3457269"},{"key":"7081_CR41","doi-asserted-by":"publisher","first-page":"15427","DOI":"10.1007\/s00500-020-04875-y","volume":"24","author":"J Tao","year":"2020","unstructured":"Tao J, Zhang B, Lin D, Gao Y, Li Q (2020) Efficient column-oriented processing for mutual subspace skyline queries. Soft Comput 24:15427\u201315445","journal-title":"Soft Comput"},{"key":"7081_CR42","doi-asserted-by":"crossref","unstructured":"Tao Y, Yi K, Sheng C et al. (2009) Quality and efficiency in high dimensional nearest neighbor search. In SIGMOD, pp. 563\u2013576","DOI":"10.1145\/1559845.1559905"},{"issue":"11","key":"7081_CR43","doi-asserted-by":"publisher","first-page":"1964","DOI":"10.14778\/3476249.3476255","volume":"14","author":"M Wang","year":"2021","unstructured":"Wang M, Xu X, Yue Q et al (2021) A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search. Proc VLDB Endow 14(11):1964\u20131978","journal-title":"Proc VLDB Endow"},{"issue":"1","key":"7081_CR44","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.eswa.2016.01.012","volume":"53","author":"B Zhang","year":"2016","unstructured":"Zhang B, Jiang T, Bao Z, Wong R, Chen L (2016a) Monochromatic and bichromatic reverse top-k group nearest neighbor queries. Expert Syst Appl 53(1):57\u201374","journal-title":"Expert Syst Appl"},{"key":"7081_CR45","doi-asserted-by":"crossref","unstructured":"Zhang S, Sun C, He Z (2016b) ListMerge: accelerating top-k aggregation queries over large number of lists. In: Proceeding of the 21st InInternational Conference on DASFAA, pp. 67\u201381","DOI":"10.1007\/978-3-319-32049-6_5"}],"container-title":["Soft Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00500-022-07081-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00500-022-07081-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00500-022-07081-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,30]],"date-time":"2022-09-30T06:31:29Z","timestamp":1664519489000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00500-022-07081-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,2]]},"references-count":45,"journal-issue":{"issue":"22","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["7081"],"URL":"https:\/\/doi.org\/10.1007\/s00500-022-07081-0","relation":{},"ISSN":["1432-7643","1433-7479"],"issn-type":[{"type":"print","value":"1432-7643"},{"type":"electronic","value":"1433-7479"}],"subject":[],"published":{"date-parts":[[2022,5,2]]},"assertion":[{"value":"28 March 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 May 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"TJ declares that he\/she has no conflict of interest. BZ declares that he\/she has no conflict of interest. TJ declares that he\/she has no conflict of interest. DL declares that he\/she has no conflict of interest. YG declares that he\/she has no conflict of interest. QL declares that he\/she has no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"This article does not contain any studies with human participants or animals performed by any of the authors.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}},{"value":"Informed consent was obtained from all individual participants included in the study.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Informed consent"}}]}}