Study On Novel Spatial Query Processing Techniques For Uncertain Objects

The research on spatial database originated from the field of map making and processing of remote sensing image data in1970s, which is employed to make all kinds of the matic maps quickly with remote sensing resource. Along with the development of GIS (geographical information system), CAD/CAM, Robots, Multimedia System, Digital Earth, Mobile Communication, Location Service, etc., more and more attentation on spatial database has been paid. Location-based service, especially, brings tremendous challenges to data processing in spatial database. How to process the data in LBS efficiently, is one of the most important issues for determining the prospects of spatial database applications, and thus arouses extensive attention in academia as well as industry. At present, there have been some researches on LBS-based spatial queries. The uncertainty of objects exists commonly in some applications involving spatial queries, which is due to the inaccuracy of measurement instructions and the data inherent attributes. How to model, pre-process and process some novel queries on uncertain objects remains a problem that urgently needs to be resolved.This dissertation concludes the uncertain phenomena and issues of spatial data management and analyzes the state of arts about uncertain data management in spatial database. We classify spatial uncertainty into positionally uncertainty and existentally uncertainty. On account of the uncertainty, novel models and methods are proposed for index construction, closest pair queries and group nearest neighbor queries, and thus a distinctive process framework is built. These techniques can efficiently improve the capability and effectiveness of spatial data management, and furthermore support novel spatial query applications in complex circumstances.Specifically, this dissertation conducts in-depth studies into several spatial query processing techniques, including closest pair query, range closest pair query, group nearest neighbor query and group nearest group query. The key problems about data modeling, index construction and query optimization, which base on uncertain objects are covered. Specifically, the major work includes:(1) We study the problem of closest pairs query on uncertain objects in spatial database and propose Top-K probabilistic closest pair query processing method and probabilistic threshold closest pair query processing method. We analyze the characters of positional uncertain objects, give the corresponding data models and propose an index structure based on clustering. Based on the properties of the index and closest pairs query, we propose several useful optimization strategies of the query and give proper proofs. These strategies are applied to the probabilistic closest pair queries to enhance the processing efficiency.(2) We discuss the problem of range closest pairs query on uncertain objects and propose the processing method of probablisitic closest pair queries with two kinds of range constraints. We study the range closest pairs query on uncertain objects in spatial database. U-clustering tree is established which is based on U tree and the problem of range closest pairs query based on positionally uncertain objects is proposed. Spatial pruning methods and probabilistic pruning methods are produced to enhance the processing performance. Based on these methods, efficient query processing algorithms are proposed to process strict range closest pairs query and loose range closest pairs query. These algorithms improve the query efficiency and eliminate the cost of disk accesses.(3) We investigate the problem of group nearest neighbor queries over extentially uncertain objects in spatial database and propose the processing algorithm of probabilistic group nearest neighbor queries. We study the group nearest neighbor queries on extentially uncertain objects in spatial database. A data model of extentially uncertainty focus on some special applications is proposed, based on which we design an augmented R-tree to reduce the processing time of probabilistic group nearest neighbor query. In addition, according to the characteristics of uncertain objects, two kinds of query algorithms based on excluding probability are described, i.e., the algorithm based on candidate sets and the algorithm based on pruning sets, which can improve the processing efficiency and satisfy the accuracy requirements.(4) We study the problem of constrained group nearest group queries over extentially uncertain objects and propose two algorithms for certain spatial objects and uncertain spatial objects, respectively. Focus on some special applications, we describe the semantics of constrained group nearest group based on group nearest group query. A query method of constrained group nearest group based on constrained clustering is studied, and the query efficiency is enhanced by efficient pruning strategies. By extending the constrained group nearest group queries over certain objects, two kinds of probabilistic group nearest group queries based on extentially uncertain objects are proposed and the corresponding processing methods are presented, which can eliminate the cost of the query searching.In conclusion, this dissertation aims at the specific features and challenges of uncertain objects involved in spatial queries, and studies the key techniques of spatial query processing over uncertain objects, covering the techniques of index construction, query optimizing methods. And thus, efficient and robust novel spatial query processing methods over uncertain spatial uncertain objects can be offered for different spatial query applications with special requirements. The study of this dissertation improve user’s ability to get knowledge of the uncertain spatial information and provide powerful support for some special applications, such as earthquake rescue, etc.