{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,10]],"date-time":"2026-09-10T06:07:25Z","timestamp":1789020445910,"version":"build-2803163510"},"reference-count":69,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,9,10]],"date-time":"2026-09-10T00:00:00Z","timestamp":1788998400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,9,10]],"date-time":"2026-09-10T00:00:00Z","timestamp":1788998400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100014597","name":"Universidade da Coru\u00f1a","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100014597","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Geoinformatica"],"published-print":{"date-parts":[[2026,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    The\n                    <jats:italic>K<\/jats:italic>\n                    Nearest Neighbors Query (\n                    <jats:italic>K<\/jats:italic>\n                    NNQ) is a fundamental distance-based query with applications in Geographic Information Systems (GIS) and many other domains. The\n                    <jats:italic>K<\/jats:italic>\n                    Nearest Neighbors Join Query (\n                    <jats:italic>K<\/jats:italic>\n                    NNJQ) combines\n                    <jats:italic>K<\/jats:italic>\n                    NNQ with the join operation to find the\n                    <jats:italic>K<\/jats:italic>\n                    nearest neighbors from a dataset\n                    <jats:italic>P<\/jats:italic>\n                    to every object in another dataset\n                    <jats:italic>Q<\/jats:italic>\n                    . Due to the large number of distance computations involved,\n                    <jats:italic>K<\/jats:italic>\n                    NNJQ is an expensive operation that poses a challenge for in-memory systems. In this paper, we propose and evaluate novel in-memory algorithms for\n                    <jats:italic>K<\/jats:italic>\n                    NNQ and\n                    <jats:italic>K<\/jats:italic>\n                    NNJQ using the compact data structure\n                    <jats:inline-formula>\n                      <jats:tex-math>$$k^2$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    -tree. The proposed algorithms exploit hierarchical spatial decomposition together with grouping, pre-processing and progressive pruning techniques. In addition, we develop two new plane-sweep algorithms for\n                    <jats:italic>K<\/jats:italic>\n                    NNQ and\n                    <jats:italic>K<\/jats:italic>\n                    NNJQ, that improve the brute-force algorithms by reducing redundant computations. We conduct an extensive experimental evaluation using real-world spatial datasets to evaluate the performance of our\n                    <jats:italic>K<\/jats:italic>\n                    NNQ and\n                    <jats:italic>K<\/jats:italic>\n                    NNJQ algorithms, comparing them with KD-tree and R*-tree based algorithms. Our results highlight the efficiency of pruning techniques in\n                    <jats:inline-formula>\n                      <jats:tex-math>$$k^2$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    -trees, which reduce distance computations and response time by up to an order of magnitude in\n                    <jats:italic>K<\/jats:italic>\n                    NNJQ, in comparison with the equivalent KD-tree, R*-tree and plane-sweep algorithms.\n                  <\/jats:p>","DOI":"10.1007\/s10707-026-00591-1","type":"journal-article","created":{"date-parts":[[2026,9,10]],"date-time":"2026-09-10T05:45:35Z","timestamp":1789019135000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["K Nearest neighbor join algorithms for spatial data using compact and plain data structures in main memory"],"prefix":"10.1007","volume":"30","author":[{"given":"Guillermo","family":"de Bernardo","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5455-6088","authenticated-orcid":false,"given":"Miguel R.","family":"Penabad","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Antonio","family":"Corral","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Vassilakopoulos","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nieves R.","family":"Brisaboa","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,9,10]]},"reference":[{"key":"591_CR1","doi-asserted-by":"publisher","unstructured":"Papadopoulos AN, Manolopoulos Y (2005) Nearest neighbor search: a database perspective. Springer. https:\/\/doi.org\/10.1007\/0-387-27544-4","DOI":"10.1007\/0-387-27544-4"},{"issue":"2","key":"591_CR2","doi-asserted-by":"publisher","first-page":"629","DOI":"10.3390\/S23020629","volume":"23","author":"N Ukey","year":"2023","unstructured":"Ukey N, Yang Z, Li B, Zhang G, Hu Y, Zhang W (2023) Survey on exact knn queries over high-dimensional data space. Sensors 23(2):629. https:\/\/doi.org\/10.3390\/S23020629","journal-title":"Sensors"},{"issue":"1","key":"591_CR3","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1186\/S40537-024-00973-Y","volume":"11","author":"RK Halder","year":"2024","unstructured":"Halder RK, Uddin MN, Uddin A, Aryal S, Khraisat A (2024) Enhancing k-nearest neighbor algorithm: a comprehensive review and performance analysis of modifications. J Big Data 11(1):113. https:\/\/doi.org\/10.1186\/S40537-024-00973-Y","journal-title":"J Big Data"},{"key":"591_CR4","unstructured":"Khandelwal U, Levy O, Jurafsky D, Zettlemoyer L, Lewis M (2020) Generalization through memorization: nearest neighbor language models. In: International conference on learning representations"},{"key":"591_CR5","unstructured":"Lewis P, Perez E, Piktus A, Petroni F, Karpukhin V, Goyal N, K\u00fcttler H, Lewis M, Yih W-t, Rockt\u00e4schel T, Riedel S, Kiela D (2020) Retrieval-augmented generation for knowledge-intensive NLP tasks. In: Advances in neural information processing systems, vol 33, pp 9459\u20139474"},{"issue":"11s","key":"591_CR6","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1145\/3510409","volume":"54","author":"P S\u00e1nchez","year":"2022","unstructured":"S\u00e1nchez P, Bellog\u00edn A (2022) Point-of-interest recommender systems based on location-based social networks: a survey from an experimental perspective. ACM Comput Surv 54(11s):223\u2013122337. https:\/\/doi.org\/10.1145\/3510409","journal-title":"ACM Comput Surv"},{"key":"591_CR7","doi-asserted-by":"publisher","unstructured":"Plattner H, Zeier A (2011) In-memory data management: an inflection point for enterprise applications. Springer. https:\/\/doi.org\/10.1007\/978-3-642-19363-7","DOI":"10.1007\/978-3-642-19363-7"},{"key":"591_CR8","doi-asserted-by":"publisher","unstructured":"Navarro G (2016) Compact data structures - a practical approach. Cambridge University Press, https:\/\/doi.org\/10.1017\/CBO9781316588284","DOI":"10.1017\/CBO9781316588284"},{"key":"591_CR9","doi-asserted-by":"publisher","DOI":"10.1016\/J.INS.2024.120732","volume":"674","author":"G Bernardo","year":"2024","unstructured":"Bernardo G, Penabad MR, Corral A, Brisaboa NR (2024) Classic distance join queries using compact data structures. Inf Sci 674:120732. https:\/\/doi.org\/10.1016\/J.INS.2024.120732","journal-title":"Inf Sci"},{"issue":"1","key":"591_CR10","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1145\/3355491.3355494","volume":"11","author":"P Bouros","year":"2019","unstructured":"Bouros P, Mamoulis N (2019) Spatial joins: what\u2019s next? ACM SIGSPATIAL Special 11(1):13\u201321. https:\/\/doi.org\/10.1145\/3355491.3355494","journal-title":"ACM SIGSPATIAL Special"},{"issue":"8","key":"591_CR11","doi-asserted-by":"publisher","first-page":"3635","DOI":"10.1109\/TKDE.2024.3364183","volume":"36","author":"M Li","year":"2024","unstructured":"Li M, Wang H, Dai H, Li M, Chai C, Gu R, Chen F, Chen Z, Li S, Liu Q, Chen G (2024) A survey of multi-dimensional indexes: past and future trends. IEEE Trans Knowl Data Eng 36(8):3635\u20133655. https:\/\/doi.org\/10.1109\/TKDE.2024.3364183","journal-title":"IEEE Trans Knowl Data Eng"},{"issue":"9","key":"591_CR12","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. https:\/\/doi.org\/10.1145\/361002.361007","journal-title":"Commun ACM"},{"key":"591_CR13","doi-asserted-by":"publisher","unstructured":"Beckmann N, Kriegel H, Schneider R, Seeger B (1990) The r*-tree: an efficient and robust access method for points and rectangles. In: ACM SIGMOD international conference on management of data. SIGMOD, pp 322\u2013331. https:\/\/doi.org\/10.1145\/93597.98741","DOI":"10.1145\/93597.98741"},{"issue":"6","key":"591_CR14","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. https:\/\/doi.org\/10.1007\/S10115-003-0122-9","journal-title":"Knowl Inf Syst"},{"key":"591_CR15","doi-asserted-by":"publisher","unstructured":"Zhang J, Mamoulis N, Papadias D, Tao Y (2004) All-nearest-neighbors queries in spatial databases. In: 16th International conference on scientific and statistical database management, SSDBM 2004. pp 297\u2013306. https:\/\/doi.org\/10.1109\/SSDBM.2004.12","DOI":"10.1109\/SSDBM.2004.12"},{"key":"591_CR16","doi-asserted-by":"publisher","unstructured":"Guttman A (1984) R-trees: a dynamic index structure for spatial searching. In: 1984 ACM SIGMOD international conference on management of data, SIGMOD 1984, pp 47\u201357. https:\/\/doi.org\/10.1145\/602259.602266","DOI":"10.1145\/602259.602266"},{"key":"591_CR17","doi-asserted-by":"publisher","unstructured":"Chen Y, Patel JM (2007) Efficient evaluation of all-nearest-neighbor queries. In: 23rd International conference on data engineering, ICDE 2007, pp 1056\u20131065. https:\/\/doi.org\/10.1109\/ICDE.2007.368964","DOI":"10.1109\/ICDE.2007.368964"},{"issue":"2","key":"591_CR18","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/J.CAG.2006.11.011","volume":"31","author":"J Sankaranarayanan","year":"2007","unstructured":"Sankaranarayanan J, Samet H, Varshney A (2007) A fast all nearest neighbor algorithm for applications involving large point-clouds. Comput Graph 31(2):157\u2013174. https:\/\/doi.org\/10.1016\/J.CAG.2006.11.011","journal-title":"Comput Graph"},{"key":"591_CR19","unstructured":"Samet H (2006) Foundations of multidimensional and metric data structures. Academic Press, San Francisco"},{"key":"591_CR20","doi-asserted-by":"publisher","unstructured":"Patel JM, DeWitt DJ (1996) Partition based spatial-merge join. In: 1996 ACM SIGMOD international conference on management of data, SIGMOD 1996, pp 259\u2013270. https:\/\/doi.org\/10.1145\/233269.233338","DOI":"10.1145\/233269.233338"},{"key":"591_CR21","doi-asserted-by":"publisher","unstructured":"Xia C, Lu H, Ooi BC, Hu J (2004) Gorder: an efficient method for KNN join processing. In: 30th International conference on very large data bases, VLDB 2004, pp 756\u2013767. https:\/\/doi.org\/10.1016\/B978-012088469-8.50067-X","DOI":"10.1016\/B978-012088469-8.50067-X"},{"issue":"6","key":"591_CR22","doi-asserted-by":"publisher","first-page":"7462","DOI":"10.1016\/J.ESWA.2010.12.077","volume":"38","author":"H Chen","year":"2011","unstructured":"Chen H, Chang Y (2011) All-nearest-neighbors finding based on the hilbert curve. Expert Syst Appl 38(6):7462\u20137475. https:\/\/doi.org\/10.1016\/J.ESWA.2010.12.077","journal-title":"Expert Syst Appl"},{"issue":"4","key":"591_CR23","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. https:\/\/doi.org\/10.1016\/J.INFSOF.2006.05.006","journal-title":"Inf Softw Technol"},{"issue":"2","key":"591_CR24","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, Yu C, Zhang R (2005) idistance: an adaptive B$$ ^{\\text{+ }}$$-tree based indexing method for nearest neighbor search. ACM Trans Database Syst 30(2):364\u2013397. https:\/\/doi.org\/10.1145\/1071610.1071612","journal-title":"ACM Trans Database Syst"},{"issue":"1","key":"591_CR25","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/S10707-009-0076-5","volume":"14","author":"C Yu","year":"2010","unstructured":"Yu C, Zhang R, Huang Y, Xiong H (2010) High-dimensional knn joins with incremental updates. GeoInformatica 14(1):55\u201382. https:\/\/doi.org\/10.1007\/S10707-009-0076-5","journal-title":"GeoInformatica"},{"key":"591_CR26","doi-asserted-by":"publisher","unstructured":"Wang J, Lin L, Huang T, Wang J, He Z (2010) Efficient k-nearest neighbor join algorithms for high dimensional sparse data. https:\/\/doi.org\/10.48550\/arXiv.1011.2807","DOI":"10.48550\/arXiv.1011.2807"},{"key":"591_CR27","doi-asserted-by":"publisher","unstructured":"Emrich T, Graf F, Kriegel H, Schubert M, Thoma M (2010) Optimizing all-nearest-neighbor queries with trigonometric pruning. In: 22nd International conference on scientific and statistical database management, SSDBM 2010, pp 501\u2013518. https:\/\/doi.org\/10.1007\/978-3-642-13818-8_35","DOI":"10.1007\/978-3-642-13818-8_35"},{"key":"591_CR28","doi-asserted-by":"publisher","unstructured":"White DA, Jain RC (1996) Similarity indexing with the ss-tree. In: 12th International conference on data engineering, ICDE 1996, pp 516\u2013523. https:\/\/doi.org\/10.1109\/ICDE.1996.492202","DOI":"10.1109\/ICDE.1996.492202"},{"key":"591_CR29","doi-asserted-by":"publisher","unstructured":"Yang C, Yu X, Liu Y (2014) Continuous KNN join processing for real-time recommendation. In: 14th IEEE international conference on data mining, ICDM 2014, pp 640\u2013649. https:\/\/doi.org\/10.1109\/ICDM.2014.20","DOI":"10.1109\/ICDM.2014.20"},{"key":"591_CR30","doi-asserted-by":"publisher","unstructured":"Ukey N, Yang Z, Zhang G, Liu B, Li B, Zhang W (2022) Efficient knn join over dynamic high-dimensional data. In: 33rd Australasian database conference on databases theory and applications, ADC 2022, pp 63\u201375. https:\/\/doi.org\/10.1007\/978-3-031-15512-3_5","DOI":"10.1007\/978-3-031-15512-3_5"},{"issue":"1","key":"591_CR31","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1109\/TKDE.2015.2453954","volume":"28","author":"L Chen","year":"2016","unstructured":"Chen L, Gao Y, Chen G, Zhang H (2016) Metric all-k-nearest-neighbor search. IEEE Trans Knowl Data Eng 28(1):98\u2013112. https:\/\/doi.org\/10.1109\/TKDE.2015.2453954","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"591_CR32","unstructured":"Ciaccia P, Patella M, Zezula P (1997) M-tree: an efficient access method for similarity search in metric spaces. In: 23rd International conference on very large data bases, VLDB 1997, pp 426\u2013435. http:\/\/www.vldb.org\/conf\/1997\/P426.PDF"},{"issue":"6","key":"591_CR33","doi-asserted-by":"publisher","first-page":"1194","DOI":"10.1007\/S11390-016-1692-9","volume":"31","author":"H Zhang","year":"2016","unstructured":"Zhang H, Xing Z, Chen L, Gao Y (2016) Efficient metric all-k-nearest-neighbor search on datasets without any index. J Comput Sci Technol 31(6):1194\u20131211. https:\/\/doi.org\/10.1007\/S11390-016-1692-9","journal-title":"J Comput Sci Technol"},{"key":"591_CR34","doi-asserted-by":"publisher","unstructured":"Smid MHM (2000) Closest-point problems in computational geometry. Handbook of Computational Geometry. Elsevier, Amsterdam, pp 877\u2013935. https:\/\/doi.org\/10.1016\/B978-044482537-7\/50021-8","DOI":"10.1016\/B978-044482537-7\/50021-8"},{"key":"591_CR35","doi-asserted-by":"publisher","unstructured":"Clarkson KL (1983) Fast algorithms for the all nearest neighbors problem. In: 24th Annual symposium on foundations of computer science, FOCS 1983, pp 226\u2013232. https:\/\/doi.org\/10.1109\/SFCS.1983.16","DOI":"10.1109\/SFCS.1983.16"},{"key":"591_CR36","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/BF02187718","volume":"4","author":"PM Vaidya","year":"1989","unstructured":"Vaidya PM (1989) An o(n log n) algorithm for the all-nearest neighbors problem. Discr Comput Geomet 4:101\u2013115. https:\/\/doi.org\/10.1007\/BF02187718","journal-title":"Discr Comput Geomet"},{"key":"591_CR37","doi-asserted-by":"publisher","unstructured":"Hinrichs KH, Nievergelt J, Schorn P (1988) A sweep algorithm and its implementation: the all-nearest-neighbors problem revisited. In: 14th International workshop on graph-theoretic concepts in computer science, WG 1988, pp 442\u2013457. https:\/\/doi.org\/10.1007\/3-540-50728-0_62","DOI":"10.1007\/3-540-50728-0_62"},{"issue":"4","key":"591_CR38","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1007\/BF01178779","volume":"29","author":"KH Hinrichs","year":"1992","unstructured":"Hinrichs KH, Nievergelt J, Schorn P (1992) An all-round sweep algorithm for 2-dimensional nearest-neighbor problems. Acta Inf 29(4):383\u2013394. https:\/\/doi.org\/10.1007\/BF01178779","journal-title":"Acta Inf"},{"key":"591_CR39","doi-asserted-by":"publisher","unstructured":"Ma H, Li J (2019) A true o(n log n) algorithm for the all-k-nearest-neighbors problem. In: 13th International conference on combinatorial optimization and applications, COCOA 2019, pp 362\u2013374. https:\/\/doi.org\/10.1007\/978-3-030-36412-0_29","DOI":"10.1007\/978-3-030-36412-0_29"},{"issue":"10","key":"591_CR40","doi-asserted-by":"publisher","first-page":"1016","DOI":"10.14778\/2336664.2336674","volume":"5","author":"W Lu","year":"2012","unstructured":"Lu W, Shen Y, Chen S, Ooi BC (2012) Efficient processing of k nearest neighbor joins using mapreduce. Proc VLDB Endow 5(10):1016\u20131027. https:\/\/doi.org\/10.14778\/2336664.2336674","journal-title":"Proc VLDB Endow"},{"key":"591_CR41","doi-asserted-by":"publisher","unstructured":"Zhang C, Li F, Jestes J (2012) Efficient parallel knn joins for large data in mapreduce. In: 15th International conference on extending database technology, EDBT 2012, pp 38\u201349. https:\/\/doi.org\/10.1145\/2247596.2247602","DOI":"10.1145\/2247596.2247602"},{"key":"591_CR42","doi-asserted-by":"publisher","first-page":"985","DOI":"10.1016\/J.INS.2019.10.030","volume":"512","author":"F Garc\u00eda-Garc\u00eda","year":"2020","unstructured":"Garc\u00eda-Garc\u00eda F, Corral A, Iribarne L, Vassilakopoulos M, Manolopoulos Y (2020) Efficient distance join query processing in distributed spatial data management systems. Inf Sci 512:985\u20131008. https:\/\/doi.org\/10.1016\/J.INS.2019.10.030","journal-title":"Inf Sci"},{"key":"591_CR43","doi-asserted-by":"publisher","unstructured":"Xie D, Li F, Yao B, Li G, Zhou L, Guo M (2016) Simba: Efficient in-memory spatial analytics. In: 2016 ACM SIGMOD international conference on management of data, SIGMOD 2016, pp 1071\u20131085. https:\/\/doi.org\/10.1145\/2882903.2915237","DOI":"10.1145\/2882903.2915237"},{"issue":"4","key":"591_CR44","doi-asserted-by":"publisher","first-page":"925","DOI":"10.1109\/TKDE.2015.2503768","volume":"28","author":"G Chatzimilioudis","year":"2016","unstructured":"Chatzimilioudis G, Costa C, Zeinalipour-Yazti D, Lee W, Pitoura E (2016) Distributed in-memory processing of all k nearest neighbor queries. IEEE Trans Knowl Data Eng 28(4):925\u2013938. https:\/\/doi.org\/10.1109\/TKDE.2015.2503768","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"591_CR45","doi-asserted-by":"publisher","first-page":"30","DOI":"10.3389\/FDATA.2020.00030","volume":"3","author":"M Tang","year":"2020","unstructured":"Tang M, Yu Y, Mahmood AR, Malluhi QM, Ouzzani M, Aref WG (2020) Locationspark: in-memory distributed spatial query processing and optimization. Front Big Data 3:30. https:\/\/doi.org\/10.3389\/FDATA.2020.00030","journal-title":"Front Big Data"},{"issue":"1","key":"591_CR46","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1186\/S40537-022-00587-2","volume":"9","author":"A Zeidan","year":"2022","unstructured":"Zeidan A, Vo HT (2022) Efficient spatial data partitioning for distributed knn joins. J Big Data 9(1):77. https:\/\/doi.org\/10.1186\/S40537-022-00587-2","journal-title":"J Big Data"},{"issue":"3","key":"591_CR47","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1080\/03081079.2023.2173750","volume":"52","author":"F Garcia-Garcia","year":"2023","unstructured":"Garcia-Garcia F, Corral A, Iribarne L, Vassilakopoulos M (2023) Efficient distributed algorithms for distance join queries in spark-based spatial analytics systems. Int J Gen Syst 52(3):206\u2013250. https:\/\/doi.org\/10.1080\/03081079.2023.2173750","journal-title":"Int J Gen Syst"},{"key":"591_CR48","doi-asserted-by":"publisher","unstructured":"Li R, Wang R, Liu J, Yu Z, He H, He T, Ruan S, Bao J, Chen C, Gu F, Hong L, Zheng Y (2021) Distributed spatio-temporal k nearest neighbors join. In: 29th International conference on advances in geographic information systems, SIGSPATIAL Conference 2021, pp 435\u2013445. https:\/\/doi.org\/10.1145\/3474717.3484209","DOI":"10.1145\/3474717.3484209"},{"issue":"2","key":"591_CR49","doi-asserted-by":"publisher","first-page":"861","DOI":"10.1109\/TBDATA.2024.3442539","volume":"11","author":"R Li","year":"2025","unstructured":"Li R, Li J, Zhou M, Wang R, He H, Chen C, Bao J, Zheng Y (2025) Learning-based distributed spatio-temporal k nearest neighbors join. IEEE Trans Big Data 11(2):861\u2013878. https:\/\/doi.org\/10.1109\/TBDATA.2024.3442539","journal-title":"IEEE Trans Big Data"},{"key":"591_CR50","doi-asserted-by":"publisher","unstructured":"Shahvarani A, Jacobsen H (2021) Distributed stream KNN join. In: 2021 ACM SIGMOD international conference on management of data, SIGMOD 2021, pp 1597\u20131609. https:\/\/doi.org\/10.1145\/3448016.3457269","DOI":"10.1145\/3448016.3457269"},{"key":"591_CR51","doi-asserted-by":"publisher","first-page":"1243289","DOI":"10.1155\/2018\/1243289","volume":"2018","author":"H Cho","year":"2018","unstructured":"Cho H (2018) Efficient shared execution processing of k-nearest neighbor joins in road networks. Mob Inf Syst 2018:1243289\u20131124328917. https:\/\/doi.org\/10.1155\/2018\/1243289","journal-title":"Mob Inf Syst"},{"key":"591_CR52","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. https:\/\/doi.org\/10.1016\/J.JPDC.2020.11.004","journal-title":"J Parallel Distrib Comput"},{"key":"591_CR53","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1016\/j.is.2013.08.003","volume":"39","author":"NR Brisaboa","year":"2014","unstructured":"Brisaboa NR, Ladra S, Navarro G (2014) Compact representation of web graphs with extended functionality. Inf Syst 39:152\u2013174. https:\/\/doi.org\/10.1016\/j.is.2013.08.003","journal-title":"Inf Syst"},{"key":"591_CR54","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1016\/j.tcs.2021.09.012","volume":"892","author":"F Santolaya","year":"2021","unstructured":"Santolaya F, Caniup\u00e1n M, Gajardo L, Romero M, Torres-Avil\u00e9s R (2021) Efficient computation of spatial queries over points stored in k$$ ^{\\text{2 }}$$-tree compact data structures. Theoret Comput Sci 892:108\u2013131. https:\/\/doi.org\/10.1016\/j.tcs.2021.09.012","journal-title":"Theoret Comput Sci"},{"key":"591_CR55","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1016\/j.ins.2019.08.007","volume":"506","author":"NR Brisaboa","year":"2020","unstructured":"Brisaboa NR, Cerdeira-Pena A, Bernardo G, Navarro G, Pedreira O (2020) Extending general compact querieable representations to GIS applications. Inf Sci 506:196\u2013216. https:\/\/doi.org\/10.1016\/j.ins.2019.08.007","journal-title":"Inf Sci"},{"key":"591_CR56","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/J.IS.2018.10.001","volume":"80","author":"C Quijada-Fuentes","year":"2019","unstructured":"Quijada-Fuentes C, Penabad MR, Ladra S, Guti\u00e9rrez G (2019) Set operations over compressed binary relations. Inf Syst 80:76\u201390. https:\/\/doi.org\/10.1016\/J.IS.2018.10.001","journal-title":"Inf Syst"},{"issue":"2","key":"591_CR57","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1007\/S10115-014-0770-Y","volume":"44","author":"S \u00c1lvarez-Garc\u00eda","year":"2015","unstructured":"\u00c1lvarez-Garc\u00eda S, Brisaboa NR, Fern\u00e1ndez JD, Mart\u00ednez-Prieto MA, Navarro G (2015) Compressed vertical partitioning for efficient RDF management. Knowl Inf Syst 44(2):439\u2013474. https:\/\/doi.org\/10.1007\/S10115-014-0770-Y","journal-title":"Knowl Inf Syst"},{"key":"591_CR58","doi-asserted-by":"publisher","unstructured":"Berg M, Cheong O, Kreveld MJ, Overmars MH (2008) Computational geometry: algorithms and applications. Springer, Heidelberg. https:\/\/doi.org\/10.1007\/978-3-540-77974-2 (3rd Edition)","DOI":"10.1007\/978-3-540-77974-2"},{"key":"591_CR59","doi-asserted-by":"publisher","unstructured":"Shekhar S, Xiong H (2017) Encyclopedia of GIS. In: Zhou X (ed) Springer, New York. https:\/\/doi.org\/10.1007\/978-3-319-17885-1","DOI":"10.1007\/978-3-319-17885-1"},{"issue":"1","key":"591_CR60","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1145\/1206049.1206056","volume":"32","author":"EH Jacox","year":"2007","unstructured":"Jacox EH, Samet H (2007) Spatial join techniques. ACM Trans Database Syst 32(1):7. https:\/\/doi.org\/10.1145\/1206049.1206056","journal-title":"ACM Trans Database Syst"},{"key":"591_CR61","doi-asserted-by":"publisher","unstructured":"Roumelis G, Vassilakopoulos M, Corral A, Manolopoulos Y (2014) A new plane-sweep algorithm for the k-closest-pairs query. In: 40th International conference on current trends in theory and practice of computer science, SOFSEM 2014, pp 478\u2013490. https:\/\/doi.org\/10.1007\/978-3-319-04298-5_42","DOI":"10.1007\/978-3-319-04298-5_42"},{"issue":"4","key":"591_CR62","doi-asserted-by":"publisher","first-page":"571","DOI":"10.1007\/S10707-016-0246-1","volume":"20","author":"G Roumelis","year":"2016","unstructured":"Roumelis G, Corral A, Vassilakopoulos M, Manolopoulos Y (2016) New plane-sweep algorithms for distance-based join queries in spatial databases. GeoInformatica 20(4):571\u2013628. https:\/\/doi.org\/10.1007\/S10707-016-0246-1","journal-title":"GeoInformatica"},{"key":"591_CR63","unstructured":"Dinis J, Mamede M (2002) A sweep line algorithm for nearest neighbour queries. In: 14th Canadian conference on computational geometry, CCCG 2002, pp 123\u2013127"},{"issue":"1","key":"591_CR64","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.datak.2003.08.007","volume":"49","author":"A Corral","year":"2004","unstructured":"Corral A, Manolopoulos Y, Theodoridis Y, Vassilakopoulos M (2004) Algorithms for processing k-closest-pair queries in spatial databases. Data Knowl Eng 49(1):67\u2013104. https:\/\/doi.org\/10.1016\/j.datak.2003.08.007","journal-title":"Data Knowl Eng"},{"key":"591_CR65","doi-asserted-by":"publisher","unstructured":"Eldawy A, Mokbel MF (2015) Spatialhadoop: a mapreduce framework for spatial data. In: 31st IEEE international conference on data engineering, ICDE 2015, pp 1352\u20131363. https:\/\/doi.org\/10.1109\/ICDE.2015.7113382","DOI":"10.1109\/ICDE.2015.7113382"},{"key":"591_CR66","doi-asserted-by":"publisher","unstructured":"Roussopoulos N, Kelley S, Vincent F (1995) Nearest neighbor queries. In: 1995 ACM SIGMOD international conference on management of data, SIGMOD 1995, pp 71\u201379. https:\/\/doi.org\/10.1145\/223784.223794","DOI":"10.1145\/223784.223794"},{"key":"591_CR67","doi-asserted-by":"publisher","unstructured":"Hwang S, Kwon K, Cha SK, Lee BS (2003) Performance evaluation of main-memory r-tree variants. In: 8th International symposium on advances in spatial and temporal databases, SSTD 2003, pp 10\u201327. https:\/\/doi.org\/10.1007\/978-3-540-45072-6_2","DOI":"10.1007\/978-3-540-45072-6_2"},{"key":"591_CR68","series-title":"Schriftenreihe des Fachbereichs Elektrotechnik und Informatik","first-page":"39","volume-title":"Document Image Analysis with the Gamera Framework","author":"C Dalitz","year":"2009","unstructured":"Dalitz C (2009) Kd-trees for document layout analysis. In: Dalitz C (ed) Document Image Analysis with the Gamera Framework, vol 8. Schriftenreihe des Fachbereichs Elektrotechnik und Informatik. Shaker Verlag, Aachen, Germany, pp 39\u201352"},{"issue":"6","key":"591_CR69","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/S10766-023-00755-8","volume":"51","author":"P Velentzas","year":"2023","unstructured":"Velentzas P, Vassilakopoulos M, Corral A, Antonopoulos C (2023) Gpu-based algorithms for processing the k nearest-neighbor query on spatial data using partitioning and concurrent kernel execution. Int J Parallel Prog 51(6):275\u2013308. https:\/\/doi.org\/10.1007\/S10766-023-00755-8","journal-title":"Int J Parallel Prog"}],"container-title":["GeoInformatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10707-026-00591-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10707-026-00591-1","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10707-026-00591-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,9,10]],"date-time":"2026-09-10T05:45:41Z","timestamp":1789019141000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10707-026-00591-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,9,10]]},"references-count":69,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,12]]}},"alternative-id":["591"],"URL":"https:\/\/doi.org\/10.1007\/s10707-026-00591-1","relation":{},"ISSN":["1384-6175","1573-7624"],"issn-type":[{"value":"1384-6175","type":"print"},{"value":"1573-7624","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,9,10]]},"assertion":[{"value":"12 November 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 May 2026","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 August 2026","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 September 2026","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare no competing interests.","order":1,"name":"Ethics","label":"Competing interests","group":{"name":"EthicsHeading","label":"Declarations"}}],"article-number":"33"}}