Research On Key Technologies Of Some Queries Over Multi-dimensional Uncertain Data

Along with the development of data collection techniques and data process-ing techniques, a great deal of uncertain data are produced in many application fields such as sensor network monitoring, medical image managements, Location-Based Services and so on. Recently, uncertain data management has received more and more attention. To store and represent rich semantics, in many real-world applications data objects contain more than one uncertain attributes (e.g., hori-zontal and vertical coordinates of spatial location information), which are termed multi-dimensional uncertain data. Compared to query processing techniques for one-dimensional uncertain data, due to the complex semantics of multi-dimensional uncertain data, the query processing techniques for multi-dimensional uncertain data face greater challenges in time and space efficiency. Besides, the complexity of the query on multi-dimensional uncertain data becomes prohibitive (even NP-hard) due to imprecision or temporal constraints of query conditions. Currently, existing techniques cannot apply to answering complex queries on multi-dimensional uncer-tain data efficiently. How to model and query multi-dimensional uncertain data with complex query conditions is a hot and burning topic in area of uncertain data management.This dissertation studies and summarizes existing Top-?, optimal location se-lection, and reverse nearest neighbor query techniques. For handling many kinds of uncertain data, the dissertation proposes novel models and methods for Top-k, op-timal location selection, and reverse nearest neighbor queries. These techniques can improve the efficiency of query processing over multi-dimensional uncertain data, and therefore support query requirements in more complex applications.Specifically, this dissertation focuses on Top-? queries and spatial queries on multi-dimensional uncertain data, majorly including Fuzzy Top-? Query, Fuzzy Ranking Query with Multiple Fuzzy Thresholds, Group Location Selection Query and Interval Reverse Nearest Neighbor Query. These four novel query techniques cover key problems of query processing on multi-dimensional uncertain data (ob-jects). In detail, the contributions are summarized as follows:(1) Fuzzy Top-? query on multi-dimensional uncertain objects. Under fuzzy query conditions, the fuzzy Top-? query can return k objects which have i-th (1?i?k) largest scores of the fuzzy score function. For multi-dimensional un-certain data with continuous probability distributions, the score function of this query takes both fuzzy query conditions and data probability into account. Mean-while, the dissertation proposes an efficient framework for fuzzy Top-k queries on multi-dimensional uncertain objects with continuous probability distributions and an efficient method to improve the query efficiency by reducing the dimensionality of multi-dimensional data.(2) Fuzzy ranking query with multiple fuzzy thresholds based on possible world model. The ranking function of a fuzzy Top-k; query gives the unique rank for each object and returns the first k highest ranks. However, the ranking function of a fuzzy ranking query gives the rank for each position and returns the answers whose ranks to be ranked j-th (1< j< k) are largest respectively. In the case of fuzzy query conditions with multiple fuzzy thresholds, the dissertation designs a novel query-fuzzy ranking query with multiple fuzzy thresholds which retrieves fixed number of results under multiple fuzzy thresholds. The proposed pruning technique improves the effectiveness. Besides, the dissertation addresses an efficient query processing algorithm to answer the fuzzy ranking query with multiple fuzzy thresholds over multi-dimensional uncertain data with discrete probability distributions.(3) Group location selection query on uncertain spatial objects. In optimal location selection area, the dissertation addresses a new type of optimal location selection query termed group location selection query. The group location selection query finds a minimum number of locations such that building facilities at these locations would cover all the given uncertain objects with a guaranteed error. The dissertation proposes an efficient framework and a series of effective algorithms.(4) Interval reverse nearest neighbor query based on Markov model. In re-search area of reverse nearest neighbor query on spatial and temporal database, the dissertation proposes interval reverse nearest neighbor queries on uncertain moving objects with Markov correlations, which can return the objects maintaining reverse nearest neighboring relations to the query object for the longest time. To improve the efficiency, the dissertation presents spatial and probabilistic pruning methods in the query process. An effective verification method is also proposed to further improve the efficiency.In conclusion, this dissertation focuses on queries over multi-dimensional un-certain data with efficient and robust techniques, which supports the query require-ments from different applications. Extensive experiments also verify the effectiveness and efficiency of the proposed methods.