{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:28:48Z","timestamp":1760236128607,"version":"build-2065373602"},"reference-count":48,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2021,10,27]],"date-time":"2021-10-27T00:00:00Z","timestamp":1635292800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100012166","name":"National Key Research and Development Program of China","doi-asserted-by":"publisher","award":["2018YFB0505304","2018YFC1503505"],"award-info":[{"award-number":["2018YFB0505304","2018YFC1503505"]}],"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":["41771416"],"award-info":[{"award-number":["41771416"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>Support for region queries is crucial in geographic information systems, which process exact queries through spatial indexing to filter features and subsequently refine the selection. Although the filtering step has been extensively studied, the refinement step has received little attention. This research builds upon the QR-tree index, which decomposes space into hierarchical grids, registers features to the grids, and builds an R-tree for each grid, to develop a new QRB-tree index with two levels of optimization. In the first level, a bucket is introduced in every grid in the QR-tree index to accelerate the loading and search steps of a query region for the grids within the query region. In the second level, the number of candidate features to be eliminated is reduced by limiting the features to those registered to the grids covering the corners of the query region. Subsequently, an approach for determining the maximal grid level, which significantly affects the performance of the QR-tree index, is proposed. Direct comparisons of time costs with the QR-tree index and geohash index show that the QRB-tree index outperforms the other two approaches for rough queries in large query regions and exact queries in all cases.<\/jats:p>","DOI":"10.3390\/ijgi10110727","type":"journal-article","created":{"date-parts":[[2021,10,27]],"date-time":"2021-10-27T22:00:23Z","timestamp":1635372023000},"page":"727","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["QRB-tree Indexing: Optimized Spatial Index Expanding upon the QR-tree Index"],"prefix":"10.3390","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5900-0000","authenticated-orcid":false,"given":"Jieqing","family":"Yu","sequence":"first","affiliation":[{"name":"NASG Key Laboratory of Land Environment and Disaster Monitoring, China University of Mining and Technology, Xuzhou 221116, China"},{"name":"School of Environmental Science and Spatial Informatics, China University of Mining and Technology, Xuzhou 221116, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9847-9536","authenticated-orcid":false,"given":"Yi","family":"Wei","sequence":"additional","affiliation":[{"name":"School of Environmental Science and Spatial Informatics, China University of Mining and Technology, Xuzhou 221116, China"}]},{"given":"Qi","family":"Chu","sequence":"additional","affiliation":[{"name":"School of Environmental Science and Spatial Informatics, China University of Mining and Technology, Xuzhou 221116, China"}]},{"given":"Lixin","family":"Wu","sequence":"additional","affiliation":[{"name":"School of Geosciences and Info-Physics, Central South University, Changsha 410083, China"}]}],"member":"1968","published-online":{"date-parts":[[2021,10,27]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1080\/20964471.2018.1432115","article-title":"Big spatial vector data management: A review","volume":"2","author":"Yao","year":"2018","journal-title":"Big Earth Data"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1080\/17538947.2016.1264490","article-title":"Big Earth Data: A new challenge and opportunity for Digital Earth\u2019s development","volume":"10","author":"Guo","year":"2016","journal-title":"Int. J. Digit. Earth"},{"key":"ref_3","unstructured":"OGC (2011). OpenGIS\u00ae Implementation Standard for Geographic information\u2014Simple Feature Accessx\u2013Part 1: Common Architecture, Open Geospatial Consortium. OGC 06-103r4."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-031-01884-8","article-title":"Spatial Data Management","volume":"Volume 3","author":"Mamoulis","year":"2011","journal-title":"Synthesis. Lectures on. Data Management"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Kothuri, R.K., and Ravada, S. (2001, January 12\u201315). Efficient Processing of Large Spatial Queries Using Interior Approximations. Proceedings of the 7th International Symposium, SSTD 2001, Redondo Beach, CA, USA. Advances in Spatial and Temporal Databases.","DOI":"10.1007\/3-540-47724-1_21"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/S0164-1212(01)00138-8","article-title":"Heuristic approach for early separated filter and refinement strategy in spatial query optimization","volume":"62","author":"Park","year":"2002","journal-title":"J. Syst. Softw."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Kothuri, R.K.V., Ravada, S., and Abugov, D. (2002, January 4\u20136). Quadtree and R-tree indexes in oracle spatial: A comparision using GIS data. Proceedings of the ACM SIGMOD International Conference on Management of Data, Madison, WI, USA.","DOI":"10.1145\/564691.564755"},{"key":"ref_8","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."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF00288933","article-title":"Quad trees a data structure for retrieval on composite keys","volume":"4","author":"Finkel","year":"1974","journal-title":"Acta Inform."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1080\/13658810110043603","article-title":"Continuous indexing of hierarchical subdivisions of the globe","volume":"15","author":"Bartholdi","year":"2001","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1080\/13658810110095075","article-title":"Ellipsoidal quadtrees for indexing of global geographical data","volume":"16","author":"Ottoson","year":"2002","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"2177","DOI":"10.1007\/s10586-017-1014-1","article-title":"A basis of spatial big data analysis with map-matching system","volume":"20","author":"Cho","year":"2017","journal-title":"Clust. Comput."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"2140","DOI":"10.1080\/13658816.2018.1484124","article-title":"A data model and algorithms for a spatial data marketplace","volume":"32","author":"Sakr","year":"2018","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1016\/j.isprsjprs.2020.03.010","article-title":"Global multi-scale grid integer coding and spatial indexing: A novel approach for big earth observation data","volume":"163","author":"Lei","year":"2020","journal-title":"ISPRS J. Photogramm. Remote. Sens."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Guttman, A. (1984, January 18\u201321). R-trees: A dynamic index structure for spatial searching. Proceedings of the ACM management of data (SIGMOD), Boston, MA, USA.","DOI":"10.1145\/602259.602266"},{"key":"ref_16","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 Thirteenth International Conference on Very Large Data Bases: 1987, 13th VLDB, Brighton, UK."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1145\/93605.98741","article-title":"The R*-tree: An efficient and robust access method for points and rectangles","volume":"19","author":"Beckmann","year":"1990","journal-title":"ACM SIGMOD Rec."},{"key":"ref_18","unstructured":"Kamel, I., and Faloutsos, C. (1993, January 12\u201315). Hilbert R-tree: An improved R-tree using fractals. Proceedings of the 20th International Conference on Very Large Databases, Santiago, Chile."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1328911.1328920","article-title":"The priority R-tree: A Practically Efficient and Worst-Case Optimal","volume":"4","author":"Arge","year":"2008","journal-title":"R-tree. ACM Trans. Algorithms"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"719","DOI":"10.1007\/s00778-008-0120-3","article-title":"The RUM-tree: Supporting frequent updates in R-trees using memos","volume":"18","author":"Silva","year":"2009","journal-title":"VLDB J."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1177\/0165551519828616","article-title":"LAZY R-tree: The R-tree with lazy splitting algorithm","volume":"46","author":"Yang","year":"2019","journal-title":"J. Inf. Sci."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1145\/3137586.3137590","article-title":"A Survey of Traditional and MapReduce-Based Spatial Query Processing Approaches","volume":"46","author":"Singh","year":"2017","journal-title":"SIGMOD Rec."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/s41060-020-00208-2","article-title":"Grid-R-tree: A data structure for efficient neighborhood and nearest neighbor queries in data mining","volume":"10","author":"Goyal","year":"2020","journal-title":"Int. J. Data Sci. Anal."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1504\/IJSNET.2014.064434","article-title":"Indexing method for moving sensor node retrieval","volume":"15","author":"Lee","year":"2014","journal-title":"Int. J. Sens. Netw."},{"key":"ref_25","unstructured":"Fu, Y.-C., Hu, Z.-Y., Guo, W., and Zhou, D.-R. (2003, January 5). QR-tree: A hybrid spatial index structure. Proceedings of the 2003 International Conference on Machine Learning and Cybernetics (IEEE Cat. No.03EX693), Xi\u2019an, China."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1017\/S0373463307004043","article-title":"A Spatial Indexing Approach for High Performance Location Based Services","volume":"60","author":"Huang","year":"2007","journal-title":"J. Navig."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1007\/978-3-642-25661-5_68","article-title":"Study of Spatial Data Index Structure Based on Hybrid Tree","volume":"Volume 123","author":"Wang","year":"2011","journal-title":"Knowledge Engineering and Management"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"752","DOI":"10.4028\/www.scientific.net\/AMR.187.752","article-title":"Spatial Join Queries Based on QR-tree","volume":"187","author":"Yang","year":"2011","journal-title":"Adv. Mater. Res."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Mao, H., and Bian, F. (2007, January 21\u201325). Design and Implementation of QR+Tree Index Algorithms. Proceedings of the 2007 International Conference on Wireless Communications, Networking and Mobile Computing, Shanghai, China.","DOI":"10.1109\/WICOM.2007.1468"},{"key":"ref_30","first-page":"385","article-title":"QR*-Tree: An Adaptive Space-Partitioning Index for Monitoring Moving Objects","volume":"33","author":"Phan","year":"2017","journal-title":"J. Inf. Sci. Eng."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Guo, J., Guo, W., and Zhou, D. (2006, January 20\u201324). Indexing of Constrained Moving Objects for Current and Near Future Positions in GIS. Proceedings of the First International Multi-Symposiums on Computer and Computational Sciences (IMSCCS\u201906), Hangzhou, China.","DOI":"10.1109\/IMSCCS.2006.235"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/s00778-002-0067-8","article-title":"Speeding up construction of PMR quadtree-based spatial indexes","volume":"11","author":"Hjaltason","year":"2002","journal-title":"VLDB J."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Hohl, A., Casas, I., Delmelle, E., and Tang, W. (2016, January 27\u201330). Hybrid Indexing for Parallel Analysis of Spatiotemporal Point Patterns. Proceedings of the 9th International Conference on Geographic information Science, Montreal, QC, Canada.","DOI":"10.21433\/B3114824R3WG"},{"key":"ref_34","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_35","first-page":"3972","article-title":"Research on a hybrid spatial index structure","volume":"11","author":"Gu","year":"2011","journal-title":"J. Colloid Interface Sci."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"728","DOI":"10.1007\/s12517-020-05752-6","article-title":"Geological tetrahedral model-oriented hybrid spatial indexing structure based on Octree and 3D R*-tree","volume":"13","author":"Wang","year":"2020","journal-title":"Arab. J. Geosci."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Du Mouza, C., Litwin, W., and Rigaux, P. (2007, January 15\u201320). SD-Rtree: A Scalable Distributed Rtree. Proceedings of the 2007 IEEE 23rd International Conference on Data Engineering, Istanbul, Turkey.","DOI":"10.1109\/ICDE.2007.367875"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1109\/MCSE.2014.48","article-title":"Evaluating Geospatial Geometry and Proximity Queries Using Distributed Hash Tables","volume":"16","author":"Malensek","year":"2014","journal-title":"Comput. Sci. Eng."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Elashry, A., Shehab, A., Riad, A.M., and Aboul-Fotouh, A. (2018). 2DPR-tree: Two-Dimensional Priority R-tree Algorithm for Spatial Partitioning in SpatialHadoop. ISPRS Int. J. Geo-Inf., 7.","DOI":"10.3390\/ijgi7050179"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"1656","DOI":"10.1080\/17538947.2020.1778804","article-title":"DAPR-tree: A distributed spatial data indexing scheme with data access patterns to support Digital Earth initiatives","volume":"13","author":"Xia","year":"2020","journal-title":"Int. J. Digit. Earth"},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Han, D., and Stroulia, E. (July, January 28). HGrid: A Data Model for Large Geospatial Data Sets in HBase. Proceedings of the 2013 IEEE Sixth International Conference on Cloud Computing, Santa Clara, CA, USA.","DOI":"10.1109\/CLOUD.2013.78"},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Park, S.-Y., and Bae, H.-Y. (2005, January 9\u201312). A Distributed Spatial Index for Time-Efficient Aggregation Query Processing in Sensor Networks. Proceedings of the Computational Science\u2014ICCS, Singapore.","DOI":"10.1007\/11428831_50"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"1175","DOI":"10.1109\/TPDS.2009.131","article-title":"Stabilizing Distributed R-trees for Peer-to-Peer Content Routing","volume":"21","author":"Bianchi","year":"2010","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_44","first-page":"4231","article-title":"Hadoop-based QR-tree index","volume":"12","author":"Feng","year":"2013","journal-title":"Comput. Eng. Des."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"e5202","DOI":"10.1002\/cpe.5202","article-title":"An improved integrated Grid and MapReduce-Hadoop architecture for spatial data: Hilbert TGS R-tree-based IGSIM","volume":"31","author":"Singh","year":"2019","journal-title":"Concurr. Comput. Pract. Exp."},{"key":"ref_46","unstructured":"Morton, G.M. (1966). A computer oriented geodetic data base and a new technique in file sequencing. IBM Ger. Sci. Symp. Ser., 294\u2013897."},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Huffman, C. (2015). Storage, Syngress.","DOI":"10.1016\/B978-0-12-416701-8.00003-X"},{"key":"ref_48","first-page":"e6029","article-title":"High-performance implementation of a two-bit geohash coding technique for nearest neighbor search","volume":"33","author":"Varalakshmi","year":"2020","journal-title":"Concurr. Comput. Pract. Exp."}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/10\/11\/727\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:21:21Z","timestamp":1760167281000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/10\/11\/727"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,27]]},"references-count":48,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2021,11]]}},"alternative-id":["ijgi10110727"],"URL":"https:\/\/doi.org\/10.3390\/ijgi10110727","relation":{},"ISSN":["2220-9964"],"issn-type":[{"type":"electronic","value":"2220-9964"}],"subject":[],"published":{"date-parts":[[2021,10,27]]}}}