| Spatial data engine is one of the key components of urban geological environment spatial data management system.Its main goal is to provide dynamic and efficient spatial data storage and query services for various applications related to spatiotemporal perspective of urban geological environment and intelligent control.The structure of spatial data index and various spatial query algorithms based on spatial index play an important role in the overall performance of spatial data engine.The spatial data of urban geological environment are characterized by large volume,high dimension,uneven spatial distribution and complex geometric form Based on these characteristics,the existing spatial index and spatial query technologies have the following problems in practical application.(1)In terms of spatial data index,the mainstream spatial index structures,represented by R-tree and VoR-tree,cannot meet the efficient access requirements for large-scale and uneven spatial data of geological environment;(2)In terms of spatial query based on spatial approximation,the mainstream reverse k nearest neighbor query algorithms,represented by the leading performance SLICE,cannot response fastly in large-scale query scenarios,so it cannot effectively support spatial interpolation analysis in practical applications;(3)In terms of Spatial query based on boundary constraints,the mainstream spatial region query algorithms,represented by Oracle Spatial PIP,have the defects of low effective hit ratio of candidate set and large amount of redundant spatial computation,so it is difficult to quickly return the query results when facing the query region with very irregular geometry.To solve the above problems,the following researches are carried out in this paper:(1)Design a new spatial index structure to support efficient spatial data retrieval;(2)Research and put forward a high-performance spatial query method for urban geological environment data;(3)Develop a spatial data engine based on new spatial index structure and spatial query method and carry out application demonstration.Based on these research work,the research results of this paper are mainly shown in the following aspects.(1)A multi-layer Voronoi Diagrams(MVD)index is designed and proposed by building Voronoi Diagrams layer by layer.Based on MVD index,a nearest neighbor query method named MVD-NN is proposed,and the kNN query method MVDkNN is implemented by extending the MVD-NN algorithm with the design idea of VRkNN.(2)Based on the characteristics of three typical Conic curves: circle,ellipse and hyperbola,an RkNN verification method is proposed,which uses the verified data points to assist in verifying other data points.A candidate set generation method with a lower candidate set size than the existing algorithms is implemented by Voronoi diagram.Finally,a new RkNN query algorithm named CSD-RkNN is formed by combining the above RkNN verification method and candidate set generation method.(3)Using the Voronoi diagram of data points,according to the data points with the query area of spatial topological relations will classify all of the data points,to define the boundary point,the internal point and external point,boundary neighbor points,absolute internal and external points several different categories such as the concept of absolute,according to the different categories between points on the Delaunay graph connectivity,design is put forward by identifying a boundary points to reduce the redundant I/O and redundant new space region query method to compute the spatial relationships.(4)Based on the proposed index structure and spatial query method,a set of spatial data management solution is designed,and a set of spatial data service engine of urban geological environment is developed and implemented according to the solution,which supports a series of spatial query functions,such as NN,kNN,Bi-RkNN,Mono-RkNN,Region and Buffer.The data Service engine adopts Geo JSON as the format of spatial object,publishes data services through Web Service,supports two storage modes of local storage and HDFS distributed storage,and has good scalability.Based on more than 30,000 geological borehole data and more than 140,000 surface POI data distributed throughout Shenzhen,the demonstration application of spatial data management and query oriented to geological environment is carried out,and the good application effect is obtained,which verifies the effectiveness of the method presented in this paper.The innovation of this paper is mainly reflected in the following aspects.(1)The proposed MVD adops multi-layer network structure rather than tree-like structure,and then avoid the nodes imbalances and overlapping problems.Therefore,the nearest neighbor query algorithm(MVD-NN)implemented on it is better than the state-of-theart R-tree based nearest neighbor query algorithm(BFS)in terms of I/O performance and query efficiency.(2)The proposed CSD-RkNN algorithm reduces the size of the candidate set by using the characteristics of Voronoi diagram,and improves the verification efficiency of most candidates by using the conic curve discriminance(CSD).So its I/O performance and query efficiency are better than the state-of-the-art RkNN algorithm(SLICE).(3)The proposed BPI-Region algorithm divides the internal points and the external points into two set which are completely disconnected on the Delaunay graph by using the border points(i.e.,the points whose Voronoi cell intersect the borderline of the query region),avoiding most of the redundant verification of internal points and redundant access to external points.So,the I/O performance and query efficiency of the algorithm outperforms that of the state-of-the-art R-tree based area query algorithm(Ocracle Spatial PIP). |
PDF Full Text Request