Efficient query processing over uncertain data

Uncertain data management has become increasingly important in many real-world applications such as sensor network monitoring, location-based services (LBS), biometric databases, moving object search, and so on. Compared to precise data, each uncertain object in an uncertain database is not an exact data point, but, instead, resides within a so-called uncertainty region following some probabilistic distribution. As a consequence, the distance between any two uncertain objects becomes a random variable rather than a fixed value, and thus the existing techniques proposed for answering queries on precise data points cannot be directly applied to the uncertain scenario. In this thesis, we investigate probabilistic queries on both static and dynamically moving uncertain objects. In particular, queries in static uncertain databases include probabilistic group nearest neighbor (PGNN), probabilistic reverse nearest neighbor (PRNN), and probabilistic reverse skyline (PRSQ) queries, whereas that in uncertain moving object databases includes the probabilistic consistent k-nearest neighbor (con-kNN) query. Due to the intrinsic differences between uncertain and certain data, we formally re-define these query types in uncertain databases, which provides the confidence guarantee of the query answers. Most importantly, to tackle the efficiency problem of query processing, we propose effective pruning methods to facilitate reducing the search space for each query type, and seamlessly integrate them into an efficient query procedure. We also formulate and tackle some useful and important variants of these query types. We demonstrate through extensive experiments the effectiveness of our proposed pruning methods and the efficiency of the query processing approaches under various settings