{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T11:25:00Z","timestamp":1762341900648,"version":"build-2065373602"},"reference-count":27,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2022,7,12]],"date-time":"2022-07-12T00:00:00Z","timestamp":1657584000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100012166","name":"National Key R&amp;D Program of China","doi-asserted-by":"publisher","award":["2021YFC3101503","41830964"],"award-info":[{"award-number":["2021YFC3101503","41830964"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["2021YFC3101503","41830964"],"award-info":[{"award-number":["2021YFC3101503","41830964"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>Grid remapping is one of the most fundamental functions in Earth simulation systems, and is essentially a kind of data interpolation. The key to an efficient interpolation method is how to quickly find the relevant grid points required for interpolation. With the rise of unstructured grid models, the demand for general and efficient interpolation search algorithms is becoming stronger and stronger. KD (K-dimensional) tree has proven to be effective in dealing with unstructured grids. However, it is unable to tackle the cyclic boundary conditions in Earth simulation systems, which restricts the application of KD tree. Taking the nearest neighbor search as an example, this paper introduces two new KD tree-based multi-dimensional data search methods, which break through the limitations of the original method with regards to the cyclic boundary. One method is based on target points duplication, and the other method is based on source points duplication. Their time complexity and space complexity are analyzed and verified by carefully designed experiments. The results show that the method based on target points duplication generally performs better than that based on source points duplication when the data are basically evenly distributed.<\/jats:p>","DOI":"10.3390\/ijgi11070392","type":"journal-article","created":{"date-parts":[[2022,7,12]],"date-time":"2022-07-12T20:52:41Z","timestamp":1657659161000},"page":"392","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["General Data Search Algorithms for Earth Simulation Systems with Cyclic Boundaries"],"prefix":"10.3390","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4451-2756","authenticated-orcid":false,"given":"Yu","family":"Cao","sequence":"first","affiliation":[{"name":"College of Meteorology and Oceanography, National University of Defense Technology, Changsha 410073, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2066-6064","authenticated-orcid":false,"given":"Yan","family":"Chen","sequence":"additional","affiliation":[{"name":"College of Meteorology and Oceanography, National University of Defense Technology, Changsha 410073, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4334-3882","authenticated-orcid":false,"given":"Huizan","family":"Wang","sequence":"additional","affiliation":[{"name":"College of Meteorology and Oceanography, National University of Defense Technology, Changsha 410073, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0461-9367","authenticated-orcid":false,"given":"Xiaojiang","family":"Zhang","sequence":"additional","affiliation":[{"name":"College of Meteorology and Oceanography, National University of Defense Technology, Changsha 410073, China"}]},{"given":"Wenjing","family":"Zhao","sequence":"additional","affiliation":[{"name":"College of Meteorology and Oceanography, National University of Defense Technology, Changsha 410073, China"}]}],"member":"1968","published-online":{"date-parts":[[2022,7,12]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"411","DOI":"10.5194\/esd-6-411-2015","article-title":"Climate and carbon cycle dynamics in a CESM simulation from 850 to 2100 CE","volume":"6","author":"Lehner","year":"2015","journal-title":"Earth Syst. Dyn."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"2204","DOI":"10.1175\/1520-0493(1999)127<2204:FASOCR>2.0.CO;2","article-title":"First- and second-order conservative remapping schemes for grids in spherical coordinates","volume":"127","author":"Jones","year":"1999","journal-title":"Mon. Weather Rev."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1268","DOI":"10.4028\/www.scientific.net\/AMM.599-601.1268","article-title":"Application of Inverse Distance Weighted Interpolation Method in Finite Temperature Point Temperature Field","volume":"599\u2013601","author":"Zhang","year":"2014","journal-title":"Appl. Mech. Mater."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/s12145-012-0106-y","article-title":"Grid interpolation algorithm based on nearest neighbor fast search","volume":"5","author":"Huang","year":"2012","journal-title":"Earth Sci. Inform."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Kim, K.-H., Shim, P.-S., and Shin, S. (2019). An alternative bilinear interpolation method between spherical grids. Atmosphere, 10.","DOI":"10.3390\/atmos10030123"},{"key":"ref_6","unstructured":"Guttman, A. (1988). R-Trees: A Dynamic Index Structure for Spatial Searching. Readings in Database Systems, Morgan Kaufmann Publishers Inc."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Emrich, T., Graf, F., Kriegel, H., Schubert, M., and Thoma, M. (2010). Optimizing All-Nearest-Neighbor Queries with Trigonometric Pruning. Scientific and Statistical Database Management, Springer.","DOI":"10.1007\/978-3-642-13818-8_35"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1169","DOI":"10.1109\/TKDE.2004.48","article-title":"An Efficient Cost Model for Optimization of Nearest Neighbor Search in Low and Medium Dimensional Spaces","volume":"16","author":"Tao","year":"2004","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_9","unstructured":"Jones, P.W. (1998). A User\u2019s Guide for SCRIP: A Spherical Coordinate Remapping and Interpolation Package, Available online: http:\/\/forge.ipsl.jussieu.fr\/igcmg\/export\/1677\/CPL\/oasis3\/trunk\/src\/mod\/oasis3\/doc\/SCRIPusers.pdf."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1145\/361002.361007","article-title":"Multidimensional binary search trees used for associative searching","volume":"18","author":"Bentley","year":"1975","journal-title":"Commun. ACM"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1145\/355744.355745","article-title":"An algorithm for finding best matches in logarithmic expected time","volume":"3","author":"Friedman","year":"1977","journal-title":"ACM Trans. Math. Softw."},{"key":"ref_12","first-page":"50","article-title":"Building a Balanced k-d Tree in O(kn log n) Time","volume":"4","author":"Brown","year":"2015","journal-title":"J. Comput. Graph. Tech."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Cao, Y., Zhang, X.J., Duan, B.H., Zhao, W., and Wang, H. (2020, January 16\u201318). An Improved Method to Build the KD Tree Based on Presorted Results. Proceedings of the 11th International Conference on Software Engineering and Service Science, Beijing, China.","DOI":"10.1109\/ICSESS49938.2020.9237636"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"8883945","DOI":"10.1155\/2020\/8883945","article-title":"A new method to construct the KD tree based on presorted results","volume":"2020","author":"Cao","year":"2020","journal-title":"Complexity"},{"key":"ref_15","unstructured":"Agarwal, P.K., Fox, K., Munagala, K., and Nath, A. (July, January 26). Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures. Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS\u2019 16), San Francisco, CA, USA."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"667","DOI":"10.1137\/15M1026377","article-title":"Parallel Algorithms for Nearest Neighbor Search Problems in High Dimensions","volume":"38","author":"Xiao","year":"2016","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Patwary, M., Satish, N.R., Sundaram, N., Liu, J., Sadowski, P., Racah, E., Byna, S., Tull, C., Bhimji, W., and Dubey, P. (2016, January 23\u201327). PANDA: Extreme Scale Parallel K-Nearest Neighbor on Distributed Architectures. Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS), Chicago, IL, USA.","DOI":"10.1109\/IPDPS.2016.57"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Hu, L., Nooshabadi, S., Ahmadi, M., and Linjia, H. (2015, January 24\u201327). Massively Parallel KD-tree Construction and Nearest Neighbor Search Algorithms. Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS), Lisbon, Portugal.","DOI":"10.1109\/ISCAS.2015.7169256"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Hou, W., Li, D., Xu, C., and Li, T. (2018, January 10\u201312). An Advanced k Nearest Neighbor Classification Algorithm Based on KD-tree. Proceedings of the 2018 IEEE International Conference of Safety Produce Informatization (IICSPI), Chongqing, China.","DOI":"10.1109\/IICSPI.2018.8690508"},{"key":"ref_20","unstructured":"Havran, V., and Bittner, J. (2002, January 4\u20138). On Improving KD-Trees for Ray Shooting. Proceedings of the 10th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision\u2019 2002 (WSCG 2002), Pilsen, Czechia."},{"key":"ref_21","first-page":"81","article-title":"The applied research of improved ICP algorithm based on KD Tree in point Cloud registration","volume":"34","author":"Guo","year":"2015","journal-title":"Microcomput. Its Appl."},{"key":"ref_22","first-page":"3218","article-title":"Multi-dimensional cloud index based on KD-tree and R-tree","volume":"34","author":"He","year":"2014","journal-title":"J. Comput. Appl."},{"key":"ref_23","first-page":"132","article-title":"Efficient mesh deformation and flow field interpolation method for unstructured mesh","volume":"39","author":"Guo","year":"2018","journal-title":"Acta Aeronaut. Astronaut. Sin."},{"key":"ref_24","first-page":"21","article-title":"KD tree method for efficient wall distance computation of mesh","volume":"39","author":"Guo","year":"2017","journal-title":"J. Natl. Univ. Def. Technol."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Cao, Y., Wang, B., Zhao, W.J., Zhang, X., and Wang, H. (2020, January 14\u201316). Research on Searching Algorithms for Unstructured Grid Remapping Based on KD Tree. Proceedings of the 3rd International Conference on Computer and Communication Engineering Technology, Beijing, China.","DOI":"10.1109\/CCET50901.2020.9213175"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1093\/comjnl\/5.1.10","article-title":"Quicksort","volume":"5","author":"Hoare","year":"1962","journal-title":"Comput. J."},{"key":"ref_27","unstructured":"Cormen, T., Leiserson, C., and Rivest, R. (2009). Introduction to Algorithms, The MIT Press. [3rd ed.]."}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/11\/7\/392\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T23:48:46Z","timestamp":1760140126000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/11\/7\/392"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,12]]},"references-count":27,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2022,7]]}},"alternative-id":["ijgi11070392"],"URL":"https:\/\/doi.org\/10.3390\/ijgi11070392","relation":{},"ISSN":["2220-9964"],"issn-type":[{"type":"electronic","value":"2220-9964"}],"subject":[],"published":{"date-parts":[[2022,7,12]]}}}