Efficient Query Processing over Uncertain Data

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


Title: "Efficient Query Processing over Uncertain Data"

By

Mr. Xiang Lian


Abstract

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, which, 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.


Date:			Friday, 21 August 2009

Time:			3:00pm – 5:00pm

Venue:			Room 3494
 			Lifts 25-26

Chairman:		Prof. Ajay Joneja (IELM)

Committee Members:	Prof. Lei Chen (Supervisor)
 			Prof. Dik-Lun Lee
 			Prof. Frederick Lochovsky
 			Prof. Yang Xiang (MATH)
 			Prof. David Cheung (Comp. Sci., HKU)


**** ALL are Welcome ****