Integrated Spatial Query Processing Over Geospatial Data Services

Geospatial Data Service is a kind of web service which supports access to stored geospatial data. Publishing, accessing and processing geospatial data through geospatial data services are becoming more and more popular with the development of web service techniques. Currently, there are numerous geospatial data services online. One single geospatial data service has limited data which can't always satisfy various application requirements. Users lack efficient methods to fully utilize online geospatial services and query among different geospatial data services in an integrated way. Recently, geospatial data services integration has been gotten extensive attentions and become a hot issue for both GIS and spatial database realms.Many current research for spatial data integration over geospatial data services focuses on the system architecture, integration mechanism and prototype implementation. While few of integrated spatial query has been reported. To study the issues of integrated spatial query over geospatial data services, this paper gives a comprehensive discussion and analysis on former work in related areas. Towards the application needs of urban spatial information services, we study integrated spatial query processing including progressive spatial join query over GML, adaptive multi-way spatial join query and integrated k nearest neighbors query. We also apply our achievements to practical applications. The main work and innovations are detailed as follows:(1) To process integrated join query over GML, We propose an efficient progressive spatial join query algorithm (PSJ). To avoid the buffer for unprocessed data overflow and frequently flushing data from memory to disk in memory join stage, we propose an adaptive filter-refinement policy to process spatial join, which can ensure the performance of the memory-join-stage for PSJ.(2) To deal with memory overflow for PSJ, we propose a dynamic concurrent flushing policy (DCFP) based on resident degree, which takes into account the relative distribution and transmission velocity of the input datasets. It makes join query process in memory-join stage more efficient. We also develop an optimal data access schedule algorithm based on BEA (Bond Energy Algorithm) to reduce redundant I/O cost in disk-join stage.(3) Based on analysis of the characteristics of multi-way spatial join query, we present a general spatial join graph (GSJG) model which can express any type of multi-way spatial join query and transform the problem of its query optimization into the problem of binary spanning tree search for GSJG. Based on GSJG, it is easier to find a global optimal query execution plan for multi-way spatial join, especially for complex multi-way spatial join query with ring join.(4) According to the characteristics of the memory-join stage and disk-join stage for integrated multi-way spatial join query, we define the concept of efficient binary spanning tree (EBST), and study the cost estimation model for corresponding EBST. Based on GSJG and the cost model, we propose an optimal operator scheduling algorithm (OJP) for memory-join stage and a query optimization algorithm (BUOST) for disk-join stage. Both OJP and BUOST algorithm use exhaustive search method to select the efficient spanning tree with the minimum cost, which has been proved effective and efficient in practical spatial information application.(5) In order to process integrated k nearest neighbors (k-NN) query, we present a geospatial data source R tree index (GDSR tree) and a data source filter algorithm (GDSFilter). By using the minimal and maximal distance from the query point to the feature collection as pruning lower bound and upper bound to retrieve GDSR tree, GDSFilter can efficiently filter those geospatial data services which don't contribute to the query result. We enhance the adaptability of existing k-NN query algorithm for candidate geospatial data source, which takes into account all kind of relations between query window and data space of geospatial data services. The presented algorithms efficiently reduce the transmission data volume and the response time of integrated k-NN query.Based on the above achievements, we design an integrated spatial query processing prototype. In order to put our achievements into practice, we make some modifications for the prototype and apply it into the urban spatial information services system, which had validated the efficiency and practicability of our presented techniques.