Research On Continuous K-dominant Skyline Query Algorithms

Skyline query has been widely used for multi-criteria decision making, data mining,etc. However, by increasing the number of attributes, the probability that a point dominatesanother one is reduced significantly. As a result, the number of skyline points becomestoo numerous to provide any useful information. Recently, k-dominant skyline query hasbeen introduced, which can reduce the number of retrieved points by relaxing the definitionof dominance. On the issue of k-dominant skyline query on static data set, the existingalgorithms are either time-consuming on building index or too much double-counting onhigh-dimensional space. On the issue of continuous k-dominant skyline query, both pruningalgorithm and divide and conquer strategy are difcult to maintain the k-dominant skylinewhen a data point is deleted from the data set.By analyzing the shortcomings of existing algorithms and combining with the intrinsicproperties of k-dominant skyline query, we propose new algorithms to solve the problemof k-dominant skyline query on both static and continuous environment in this thesis. Themain contribution of this paper can be divided into the following:(1)we propose a concept of non-dominant relation. Two points with weaken dominantpower are hard to dominate each and two points with strong dominant power are also difcultto dominate each other. Through calculating the dominant power of each point in the thesis,we compare strong power point with weak point and avoid unnecessary comparison, thussaving a lot of time.(2)Based on the problems existing on both indexing and no-indexing algorithms, wepropose a simplified pre-sorted algorithm(SPA) to solve the problem of k-dominant skylinecomputation. The key idea of this algorithm is introducing an average data point, and cal-culating each point’s dominant power by comparing with the average point, then sorting thepoints using dominant power. This sort is not only a significant reduction in the time of thepre-sorting, but also greatly reduce the meaningless comparison between the data points.(3)We propose the concept of quasi-skyline point. On the issue of continuous k-dominant skyline query, due to the maintenance of traditional skyline points requires a lotof computation, using traditional skyline points to prune the data points is not a good strat-egy. In this thesis we propose the concept of quasi-skyline point. The maintenance of quasi-skyline is easier than traditional skyline, so it will greatly increase the efciency ofcontinuous k-dominant skyline query.(4)We propose an idea of keeping dominant relations. On the problem of continuousk-dominant skyline query, any update of the data points is likely to afect the data set ofk-dominant skyline. If any update requires to recompute the k-dominant skyline, it will beinefcient. In this thesis, we retain some of the important dominant relations between datapoints, so when the data updates it will be convenient to find the data points you need towake up, thus improve the time efciency of the algorithm.Finally, the theoretical analysis and simulation experiments present the comparisonbetween existing methods and our new algorithms. At the same time we apply the newalgorithms into real data environment. Theoretical arguments and experimental data showthat our algorithms are more efcient than all of the existing methods.