The Study Of Novel Spatial Query Processing Techniques In Complex Spatial Environments

Along with developing positioning techniques and communication techniques, and increasing requirements for spatial information, spatial data management has acquired great attention in recent years. The query processing technique is the most common and most important application in spatial data management. For example, a driver would like to search his/her nearest restaurant, or the gas stations that can be arrived with remaining gas. Currently, many existing works have proposed solutions for spatial query processing, including efficient indexing techniques and efficient query processing techniques. These solutions are constrained in simple spatial environments. However, in real world, spatial environments are very complex, e.g. there are many obstacles in space, and there are a lot of roads which constrict objects movements. Existing techniques do not consider characteristics of complex spatial environments, and they can not exactly and efficiently process spatial queries in such complex spatial environments. Thus, it is necessary to design novel space models according to different spatial environments, design novel distance metrics, and propose novel query processing techniques for spatial queries.This dissertation analyzes and summarizes existing space models and query processing techniques. After that, this dissertation deeply studies several complex space environments and designs efficient query processing techniques based on these space environments. In detail, the contributions are summarized as follows:● This dissertation proposes efficient techniques for similarity pairs query over trajectories of moving objects in semi-constraint space. Semi-constraint space is a novel spatial environment contracted from indoor space etc., which divides the whole space into several discrete areas. This spatial environment does not take into consideration the distance between moving objects inside the same area, and different areas are connected through physical paths. Each trajec-tory in semi-constraint space is a series of symbolic label, where each label represents a logic area in semi-constraint space. The distances between two logic areas are pre-defined by the system which reflect real distances between two logic areas. This dissertation studies similarity analysis over logic trajec-tories in semi-constraint space. In order to improve the efficiency of baseline method, this dissertation proposes the Co-occurrence degree based pruning method and the length difference ratio based pruning method. These prun-ing methods avoid comparisons between each trajectory pair and therefore improve the query efficiency.● This dissertation proposes query processing methods based on efficient index-ing technique for k nearest neighbor queries, reverse nearest neighbor queries and range queries over road network via wireless broadcast systems. In the wireless broadcast system, the server continuously broadcasts data, the clients receive data according to their requirements and the clients are not able to upload data to the server. The objective of processing spatial queries via wireless broadcast system is reducing the access latency and the tuning time. This dissertation divides the road network into several smaller regions, and pre-computes the lower and upper bounds between each two regions. Based on these, an efficient index is built. Due to this index containing some pre-computed information, the user can efficiently judge the necessary packages through accepting the index. Besides, the necessary packages for an user can be reduced by reasonably organizing the index, and therefore the system can achieve a balance between tuning time and access latency. Based on this index, this dissertation proposes efficient query processing techniques for k nearest neighbor queries, reverse nearest neighbor queries and range queries.● This dissertation proposes efficient pruning and verification method for the vis-ible k nearest neighbor query over uncertain objects in the obstructed space. In the obstructed space, the distances between two objects are measured by visible distance. Due to errors of measurement equipments and data transmis-sion, the positions of objects are usually uncertain. In this dissertation, the uncertain objects are constrained in their probabilistic constrained triangles and the uncertain objects follow specified probabilistic density functions. In order to execute visible k nearest neighbors query, this dissertation proposes a pruning-refinement process framework. This dissertation proposes the k-bound pruning, visible center pruning and invisible objects pruning methods, by which a small candidate set is required. Then, this dissertation refines the candidate set and get the final results through sampling method and efficient incremental refinement method based on lower and upper bounds.● This dissertation propose pruning-verification framework for continuous vis- ible k nearest neighbor queries over moving objects in the obstructed space, where the query object and data objects constantly move in space. This dis-sertation assigns a safe region for each object (including the query object), and updates the locations of all moving objects in each T timestamps, which guar-antees that all the objects are inside their safe regions in T timestamps. Based on safe regions, this dissertation proposes a pruning-refinement query frame-work. This dissertation firstly proposes the safe region based pruning, which prunes objects through the distance between safe regions of objects. Then, this dissertation prunes objects through computing invisible time period for invis-ible candidate objects. Besides, through taking the moving direction of query object into consideration, this dissertation improves the invisible time period based pruning method and increases the invisible time period. Therefore, the invisible time period of objects are increased and the number of candidate objects is reduced. Based on these pruning methods, this work detects the real positions of candidate objects and executes refining algorithm to get the final results.In a word, focusing on typical characteristics of complex spatial environments and challenges, this dissertation studies key problems of spatial queries and proposes efficient query processing methods and frameworks. Our work provides effective support for processing spatial queries over complex space models.