Font Size: a A A

Study On Skyline Query Processing Techniques On Uncertain Data

Posted on:2010-11-24Degree:MasterType:Thesis
Country:ChinaCandidate:J J WuFull Text:PDF
GTID:2218330368999847Subject:Computer software and theory
Abstract/Summary:PDF Full Text Request
With the deeper development of human knowledge, the uncertainty of data widely existing in computer applications has got more attentions from researchers. Due to probability, skyline queries studied deeply and widely in the traditional database fields can't be used in uncertain database directly.Skyline queries on uncertain data become a hot topic recently because of the important applications for multi-decision, wireless sensor networks and data mining. The existing algorithms can not meet the demands of some users, so new skyline query algorithms are needed to study. Thus, this thesis proposes two skyline queries on uncertain data. This thesis contributes four points as follows:(1) First, the concept of probabilistic threshold skyline and the basic algorithm is proposed. Then the improved algorithm is given. In the improved algorithm, the skylines of some tuples are used as filters. One filter is the skyline of the tuples which have a maybe confidence not less than 0.5 and they are not probabilistic threshold skyline. The other filter is the skyline of the tuples which have a maybe confidence less than 0.5 and they are not probabilistic threshold skyline. In queries, the object will be compared with filter, if the object is filtered out, no further calculations.(2) In the assumption that tuples are dependent, the probabilistic threshold skyline query algorithm with rule is put forward. The rules of this thesis consider two major aspects:mutually exclusive rule and coexistence rule. The mutually exclusive rule is defined as among all tuples involved in the rule, at most one tuple can appear in a possible world. The coexistence exclusive rule is defined as among all tuples involved in the rule, all tuples must appear in the same possible world.(3) The concept of uncertain skyline is defined and the basic uncertain skyline query algorithms based on sort and based on R-tree are proposed. An improved algorithm is put forward to improve the algorithm efficiency. In the improved algorithm, if tuple is not dominated by the current skyline and the maybe confidence is not less than 0.5, only the skyline containing the tuple is developed.(4) At last, through a large number of experiments, it proves all algorithms are correct and effective.
Keywords/Search Tags:uncertain data, probabilistic threshold skyline query, rule, uncertain skyline query
PDF Full Text Request
Related items