ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2020, Vol. 57 ›› Issue (2): 333-345.doi: 10.7544/issn1000-1239.2020.20190565

Special Issue: 2020大数据与智能存储系统前沿技术专题

Previous Articles     Next Articles

Efficient Index and Query Algorithm Based on Geospatial Big Data

Zhao Huihui1,2, Zhao Fan2,3, Chen Renhai1,2, and Feng Zhiyong1,2   

  1. 1(College of Intelligence and Computing, Tianjin University, Tianjin 300350);2(Shenzhen Research Institute of Tianjin University, Shenzhen, Guangdong 518000);3(Tianjin International Engineering Institute, Tianjin University, Tianjin 300350)
  • Online:2020-02-01
  • Supported by: 
    This work was supported by the National Natural Science Foundation of China (61702357, 61672377), the Shenzhen Science and Technology Foundation (JCYJ20170816093943197), the Natural Science Foundation of Tianjin (18JCQNJC00300), and the Beiyang Scholar Foundation of Tianjin University (2019XRG-0004).

Abstract: In recent years, with the rapid development of advanced technologies such as intelligent target recognition, electronic sensors, collaborative control and computer networks, intelligent transportation systems have achieved qualitative leapfrogging. Modern intelligent transportation systems can realize intelligent transportation of vehicles, roads and clouds management platform. However, the intelligent transportation system relies on a large amount of two-dimensional geospatial information data generated every day. Therefore, how to efficiently store and query large-scale geospatial data is of great significance for the future popularization and development of the intelligent transportation system. However, due to the complexity of urban traffic information, large amount of data, and fast update speed, the current spatial indexing technology is difficult to efficiently search for two-dimensional geospatial information data. In order to optimize the storage organization structure of two-dimensional geospatial information data under spatial big data and improve retrieval efficiency, this paper proposes a spatial index tree construction algorithm for multi-layer slice recursion of two-dimensional geospatial information data (multi-layer slice recursive, MSR). The proposed algorithm first sorts and divides the first dimension of the map data to generate FD slices. Then, the second dimension of the map data in the FD slice is sorted to generate SD slices, and in the SD slice, the current slice and the adjacent slices are divided into spatial objects. Finally, data clustering operation is performed on the comparison between the length of the spatial object and the node capacity, and the MSR Tree is recursively generated from the bottom up by judging whether all the slices complete the clustering operation. Experimental results show that the query performance of the 2-dimensional space storage structure constructed by the MSR algorithm is better than the most representative spatial indexing technology based on the R-tree batch-loading algorithm (sort tile recursive, STR), STR-grid hybrid algorithm (str-grid), and efficient geometric range query (EGRQ).

Key words: two-dimensional geospatial information, spatial indexing technology, big geo-data, MSR algorithm, clustering

CLC Number: