{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,12]],"date-time":"2025-12-12T13:50:35Z","timestamp":1765547435480,"version":"build-2065373602"},"reference-count":48,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2025,6,12]],"date-time":"2025-06-12T00:00:00Z","timestamp":1749686400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["42471505","AB25069111","YFC3800700"],"award-info":[{"award-number":["42471505","AB25069111","YFC3800700"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Guangxi Key Researchand Development Program","award":["42471505","AB25069111","YFC3800700"],"award-info":[{"award-number":["42471505","AB25069111","YFC3800700"]}]},{"name":"National Key Research and Development Program of China","award":["42471505","AB25069111","YFC3800700"],"award-info":[{"award-number":["42471505","AB25069111","YFC3800700"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>In recent years, with the development of sensor technology, the volume of spatial data has grown exponentially. However, this data is often unevenly distributed, and traditional indexing methods cannot predict the overall data distribution when data are continuously inserted into the database. This makes them inefficient for indexing large-scale, unevenly distributed spatial data. This paper proposes a hybrid indexing method based on the grid-indexing and R-tree methods, called R-MLGTI (R-Multi-Level Grid\u2013Tree Index). The method first divides the two-dimensional space using the Z-curve to form multiple sub-grid regions. When incrementally inserting data, R-MLGTI calculates the grid encoding of the data and computes the c(G) of the corresponding grid G to measure the sparsity or density within the grid region, where c(G) is a metric that quantifies the data density within grid G. All data in sparse grids are indexed by R-trees associated with grid encodings. In dense grid areas, a finer-grained space-filling curve is recursively applied for further spatial division. This process forms multiple sub-grids until the data within all sub-grids becomes sparse, at which point the original data is re-indexed according to the sparse grids. Finally, this paper presents a prototype system of the in-memory R-MLGTI and conducts benchmark tests for incremental data import and range queries. The incremental data insertion performance of R-MLGTI is lower than that of the grid-indexing and R-tree methods; however, on various unevenly distributed simulated datasets, the average query time for different query regions in R-MLGTI is about 6.49% faster than that of the grid-indexing method and about 51.78% faster than that of the R-tree method. On a real dataset, Landsat 7 EMT, which contains 2,585,203 records, the average query time for various query ranges is 61.39% faster than that of the grid-indexing method and 17.01% faster than that of the R-tree method. Experiments show that R-MLGTI performs better than the traditional R-tree and grid-indexing methods in large-scale, unevenly distributed spatial data query requests.<\/jats:p>","DOI":"10.3390\/ijgi14060231","type":"journal-article","created":{"date-parts":[[2025,6,12]],"date-time":"2025-06-12T06:42:48Z","timestamp":1749710568000},"page":"231","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["R-MLGTI: A Grid- and R-Tree-Based Hybrid Index for Unevenly Distributed Spatial Data"],"prefix":"10.3390","volume":"14","author":[{"given":"Yuqin","family":"Li","sequence":"first","affiliation":[{"name":"School of Computer Science, China University of Geosciences, Wuhan 430074, China"},{"name":"Engineering Research Center of Natural Resource Information Management and Digital Twin Engineering Software, Ministery of Education, Wuhan 430074, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0680-5427","authenticated-orcid":false,"given":"Jining","family":"Yan","sequence":"additional","affiliation":[{"name":"School of Computer Science, China University of Geosciences, Wuhan 430074, China"},{"name":"Engineering Research Center of Natural Resource Information Management and Digital Twin Engineering Software, Ministery of Education, Wuhan 430074, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0394-2357","authenticated-orcid":false,"given":"Xiaohui","family":"Huang","sequence":"additional","affiliation":[{"name":"School of Computer Science, China University of Geosciences, Wuhan 430074, China"}]},{"given":"Xiangyou","family":"He","sequence":"additional","affiliation":[{"name":"School of Computer Science, China University of Geosciences, Wuhan 430074, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1503-9701","authenticated-orcid":false,"given":"Ze","family":"Deng","sequence":"additional","affiliation":[{"name":"School of Computer Science, China University of Geosciences, Wuhan 430074, China"}]},{"given":"Yunliang","family":"Chen","sequence":"additional","affiliation":[{"name":"School of Computer Science, China University of Geosciences, Wuhan 430074, China"}]}],"member":"1968","published-online":{"date-parts":[[2025,6,12]]},"reference":[{"key":"ref_1","first-page":"2944","article-title":"The relationship between urbanization and land use in Guiyang city","volume":"44","author":"Chen","year":"2019","journal-title":"Earth Sci."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"0204","DOI":"10.34133\/remotesensing.0204","article-title":"Global Natural and Planted Forests Mapping at Fine Spatial Resolution of 30 m","volume":"4","author":"Xiao","year":"2024","journal-title":"J. Remote Sens."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1080\/20964471.2022.2033149","article-title":"Global land 1\u00b0 mapping dataset of XCO2 from satellite observations of GOSAT and OCO-2 from 2009 to 2020","volume":"7","author":"Sheng","year":"2023","journal-title":"Big Earth Data"},{"key":"ref_4","first-page":"100099","article-title":"Research progress on carbon sources and sinks of farmland ecosystems","volume":"11","author":"Li","year":"2023","journal-title":"Resour. Environ. Sustain."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1175","DOI":"10.1080\/17538947.2021.1937352","article-title":"Impacts of heterogeneous CO2 on water and carbon fluxes across the global land surface","volume":"14","author":"Tian","year":"2021","journal-title":"Int. J. Digit. Earth"},{"key":"ref_6","unstructured":"Shekhar, S., Evans, M.R., Gunturi, V., Yang, K., and Cugler, D.C. (2012, January 17\u201318). Benchmarking spatial big data. Proceedings of the Specifying Big Data Benchmarks: First Workshop, WBDB 2012, San Jose, CA, USA, 8\u20139 May 2012, and Second Workshop, WBDB 2012, Pune, India. Revised Selected Papers."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"15","DOI":"10.5194\/isprsarchives-XL-4-W2-15-2013","article-title":"Modeling and expression of vector data in the hexagonal discrete global grid system","volume":"40","author":"Tong","year":"2013","journal-title":"Int. Arch. Photogramm. Remote Sens. Spat. Inf. Sci."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/s12145-018-0362-6","article-title":"Method for managing and querying geo-spatial data using a grid-code-array spatial index","volume":"12","author":"Li","year":"2019","journal-title":"Earth Sci. Inform."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1145\/1071610.1071612","article-title":"iDistance: An adaptive B+-tree based indexing method for nearest neighbor search","volume":"30","author":"Jagadish","year":"2005","journal-title":"ACM Trans. Database Syst. (TODS)"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Guttman, A. (1984, January 18\u201321). R-trees: A dynamic index structure for spatial searching. Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data, Boston, MA, USA.","DOI":"10.1145\/602264.602266"},{"key":"ref_11","unstructured":"Li, G., and Tang, J. (2011, January 19\u201320). A new R-tree spatial index based on space grid coordinate division. Proceedings of the 2011, International Conference on Informatics, Cybernetics, and Computer Engineering (ICCE2011), Melbourne, Australia. Volume 2: Information Systems and Computer Engineering."},{"key":"ref_12","unstructured":"Sellis, T., Roussopoulos, N., and Faloutsos, C. (1987, January 1\u20134). The R+-tree: A dynamic index for multi-dimensional objects. Proceedings of the 13th VLDB Conference, Brighton, UK."},{"key":"ref_13","unstructured":"Kamel, I., and Faloutsos, C. (1994, January 12\u201315). Hilbert R-Tree: An Improved Rtree Using Fractals. Proceedings of the VLDB, Citeseer, Santiago de Chile, Chile."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"320","DOI":"10.3390\/ijgi4010320","article-title":"Categorization and conversions for indexing methods of discrete global grid systems","volume":"4","author":"Amiri","year":"2015","journal-title":"ISPRS Int. J. Geo-Inf."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/j.cageo.2013.08.012","article-title":"A pole-oriented discrete global grid system: Quaternary quadrangle mesh","volume":"61","author":"Zhou","year":"2013","journal-title":"Comput. Geosci."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Huang, M., Hu, P., and Xia, L. (2010, January 18\u201320). A grid based trajectory indexing method for moving objects on fixed network. Proceedings of the 2010 18th International Conference on Geoinformatics, Beijing, China.","DOI":"10.1109\/GEOINFORMATICS.2010.5567771"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1145\/348.318586","article-title":"The grid file: An adaptable, symmetric multikey file structure","volume":"9","author":"Nievergelt","year":"1984","journal-title":"ACM Trans. Database Syst. (TODS)"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1016\/j.cageo.2015.09.013","article-title":"Incorporation of the Penman\u2013Monteith potential evapotranspiration method into a Palmer Drought Severity Index tool","volume":"85","author":"Ficklin","year":"2015","journal-title":"Comput. Geosci."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Guan, X., Bo, C., Li, Z., and Yu, Y. (2017, January 2\u20134). ST-hash: An efficient spatiotemporal index for massive trajectory data in a NoSQL database. Proceedings of the 2017 25th International Conference on Geoinformatics, Buffalo, NY, USA.","DOI":"10.1109\/GEOINFORMATICS.2017.8090927"},{"key":"ref_20","unstructured":"Huang, Z. (2013). Research on Hybrid Index Based on Multi-Level Grid and STR Tree. [Master\u2019s Thesis, Zhejiang University]."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Tang, X., Han, B., and Chen, H. (2016, January 17\u201319). A hybrid index for multi-dimensional query in HBase. Proceedings of the 2016 4th International Conference on Cloud Computing and Intelligence Systems (CCIS), Beijing, China.","DOI":"10.1109\/CCIS.2016.7790279"},{"key":"ref_22","unstructured":"Sieranoja, S. (2015). High Dimensional kNN-Graph Construction Using Space Filling Curves. [Master\u2019s Thesis, It\u00e4-Suomen yliopisto]."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Laurini, R., and Thompson, D. (1992). Fundamentals of Spatial Information Systems, Academic Press.","DOI":"10.1016\/B978-0-08-092420-5.50014-1"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Zhai, W., Qi, C., Cheng, C., and Li, S. (2017, January 23\u201328). Spatial data management method with GeoSOT grid. Proceedings of the 2017 IEEE International Geoscience and Remote Sensing Symposium (IGARSS), Fort Worth, TX, USA.","DOI":"10.1109\/IGARSS.2017.8128177"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Cheng, C., Tong, X., Chen, B., and Zhai, W. (2016). A subdivision method to unify the existing latitude and longitude grids. ISPRS Int. J. Geo-Inf., 5.","DOI":"10.3390\/ijgi5090161"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Qi, K., Cheng, C., Hu, Y., Fang, H., Ji, Y., and Chen, B. (2017). An improved identification code for city components based on discrete global grid system. ISPRS Int. J. Geo-Inf., 6.","DOI":"10.3390\/ijgi6120381"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"34003","DOI":"10.1117\/1.JRS.10.034003","article-title":"Integration and management of massive remote-sensing data based on GeoSOT subdivision model","volume":"10","author":"Li","year":"2016","journal-title":"J. Appl. Remote Sens."},{"key":"ref_28","unstructured":"Zhai, W., Yang, Z., Wang, L., Wu, F., and Cheng, C. (2015, January 26\u201331). The non-sql spatial data management model in big data time. Proceedings of the 2015 IEEE international geoscience and remote sensing symposium (IGARSS), Milan, Italy."},{"key":"ref_29","first-page":"66","article-title":"An efficient integer coding and computing method for multiscale time segment","volume":"45","author":"Tong","year":"2016","journal-title":"Acta Geod. Cartogr. Sin."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1080\/20964471.2020.1844933","article-title":"STGI: A spatio-temporal grid index model for marine big data","volume":"4","author":"Qu","year":"2020","journal-title":"Big Earth Data"},{"key":"ref_31","first-page":"12007","article-title":"HBase-based spatial-temporal index model for trajectory data","volume":"Volume 1004","author":"Liu","year":"2022","journal-title":"IOP Conference Series: Earth and Environmental Science"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"39815","DOI":"10.1109\/ACCESS.2019.2906871","article-title":"A geographic meshing and coding method based on adaptive Hilbert-Geohash","volume":"7","author":"Guo","year":"2019","journal-title":"IEEE Access"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1109\/JMASS.2020.3035649","article-title":"A high-performance spatial range query-based data discovery method on massive remote sensing data via adaptive geographic meshing and coding","volume":"2","author":"Huang","year":"2020","journal-title":"IEEE J. Miniaturization Air Space Syst."},{"key":"ref_34","first-page":"12005","article-title":"A spatiotemporal trajectory data index based on the Hilbert curve code","volume":"Volume 502","author":"Wu","year":"2020","journal-title":"IOP Conference Series: Earth and Environmental Science"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"2011","DOI":"10.1007\/s10586-022-03723-y","article-title":"HCIndex: A Hilbert-Curve-based clustering index for efficient multi-dimensional queries for cloud storage systems","volume":"26","author":"Wang","year":"2023","journal-title":"Clust. Comput."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1111\/tgis.12094","article-title":"A hybrid spatial index for massive point cloud data management and visualization","volume":"18","author":"Yang","year":"2014","journal-title":"Trans. GIS"},{"key":"ref_37","first-page":"249","article-title":"A sub-three-dimensional R-tree index expansion method that takes into account multiple levels of detail","volume":"40","author":"Gong","year":"2011","journal-title":"J. Surv. Mapping"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"1231","DOI":"10.14778\/1920841.1920994","article-title":"Vor-tree: R-trees with Voronoi diagrams for efficient processing of spatial nearest neighbor queries","volume":"3","author":"Sharifzadeh","year":"2010","journal-title":"Proc. VLDB Endow."},{"key":"ref_39","first-page":"597","article-title":"A LiDAR point cloud data management method integrating octree and 3D R-tree","volume":"41","author":"Gong","year":"2012","journal-title":"J. Surv. Mapping"},{"key":"ref_40","first-page":"377","article-title":"Research on the spatial index structure of hybrid tree in 3D GIS","volume":"22","author":"Song","year":"2006","journal-title":"J. Shenyang Jianzhu Univ."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"146010","DOI":"10.1109\/ACCESS.2021.3115510","article-title":"Research on hybrid index based on 3D multi-level adaptive grid and R+ Tree","volume":"9","author":"Liu","year":"2021","journal-title":"IEEE Access"},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Liu, Z., Chen, L., Yang, A., Ma, M., and Cao, J. (2021). Hiindex: An efficient spatial index for rapid visualization of large-scale geographic vector data. ISPRS Int. J. Geo-Inf., 10.","DOI":"10.3390\/ijgi10100647"},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Zhang, Y., Zhang, A., Gao, M., and Liang, Y. (2022). Research on Three-Dimensional Electronic Navigation Chart Hybrid Spatial Index Structure Based on Quadtree and R-Tree. ISPRS Int. J. Geo-Inf., 11.","DOI":"10.3390\/ijgi11050319"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"2605","DOI":"10.14778\/3603581.3603598","article-title":"LMSFC: A Novel Multidimensional Index Based on Learned Monotonic Space Filling Curves","volume":"16","author":"Gao","year":"2023","journal-title":"Proc. VLDB Endow."},{"key":"ref_45","unstructured":"(2025, January 12). R-Tree Implementation in Java. Available online: https:\/\/github.com\/davidmoten\/rtree."},{"key":"ref_46","unstructured":"TheDeathFar (2025, January 12). An Implementation of HilbertTree by Java. Available online: https:\/\/github.com\/TheDeathFar\/HilbertTree."},{"key":"ref_47","unstructured":"(2025, January 12). Java Microbenchmark Harness (JMH). Available online: https:\/\/openjdk.org\/projects\/code-tools\/jmh\/."},{"key":"ref_48","unstructured":"(2025, January 12). Landsat 7 Enhanced Thematic Mapper Plus Level-1, Collection 1 [Dataset]. 2017, Available online: https:\/\/www.usgs.gov\/centers\/eros\/science\/usgs-eros-archive-landsat-archives-landsat-7-enhanced-thematic-mapper-plus-etm?qt-science_center_objects=0#qt-science_center_objects."}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/14\/6\/231\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T17:50:45Z","timestamp":1760032245000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/14\/6\/231"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,12]]},"references-count":48,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2025,6]]}},"alternative-id":["ijgi14060231"],"URL":"https:\/\/doi.org\/10.3390\/ijgi14060231","relation":{},"ISSN":["2220-9964"],"issn-type":[{"type":"electronic","value":"2220-9964"}],"subject":[],"published":{"date-parts":[[2025,6,12]]}}}