Efficiently and effectively processing probabilistic queries on uncertain data
Wenjie Zhang · UNSWorks (UNSW Sydney) · 2022
Uncertainty is inherent in data collected from many important, novel applications such as large sensor networks, WWW, data cleanings and integration, environmental surveillance and market analysis. The sources of uncertainty in these applications vary from data randomness and incompleteness, limitations of measuring equipments, delay or loss in data transfer. As a rapidly growing amount of uncertain data is collected, it is highly desirable to conduct advanced analysing and query processing over uncertain data. The following five important aspects for uncertain data management are investigated in this thesis. We study the problem of probabilistic top-k skyline queries. A model for the top-k skyline operator is proposed combining the feature of top-k objects and that of skyline. Based on this model, an efficient exact algorithm and a randomized algorithm with & -approximation guarantee are developed for discrete and continuous cases, respectively. We extend skyline operator to streaming environment and study the problem of probabilistic skyline queries over sliding windows. We characterize the minimum information needed in continuously computing probabilistic skyline against a sliding window. Then novel, efficient techniques are developed to process a continuous, probabilistic skyline query. As the top-k dominating query is another important method for multi-criterion decision making, we study lop-k dominating queries on uncertain data. The problem is formally defined in a probability threshold fashion. Then, a threshold-based algorithm is developed to compute the exact solution. To overcome some inherent computational deficiency in an exact computation, we develop an efficient randomized algorithm with an accuracy guarantee. We study the problem of quantile-•based KNN over multi-valued objects. Two different quantile distances are proposed. While the first distance can be computed in polynomial time, the second problem is NP-hard. A set of efficient, novel algorithms have been proposed to give an exact solution for the first problem and an approximate solution for the second problem with the approximation ratio 2. To overcome some deficiencies of existing uncertain index structures, we propose VI-tree which can efficiently support various queries including range queries, similarity joins and their size estimation as well as top-k range query, over multi-dimensional uncertain objects against continuous or discrete cases.