A Quad-tree Based Algorithm For Skyline Query

Skyline query, a sub-area of data mining, has various applications such as multi-criterion decision making, visualization and user preference queries. Recently, in database and information retrieval, the problem of how to efficiently compute Skyline has attracted extensive attention. Current technologies so far mainly focus on batch processing and online processing while the partition methods basically depend on physical division or use dimensional values of sections and they lack of in-depth analysis of the intrinsic relations between the regions partitioned.In this paper, we delve into the configuration features of Quad-tree index mechanism firstly, and then systematically explore a Quad-tree based algorithm QBSQ for computing skyline points which contributes to a better performance than traditional ones for skyline queries. This algorithm partitions data points dynamically by means of the configuration characters of Quad-tree, and then deletes points dominated by other(s) while constructing the tree. We analyze the dominant relations between partitioned regions simultaneously, and realize that some regions do have non-domination. By filtration and reduction of the amount of work for domination checking between those regions, our algorithm improves execution efficiency. Besides,we propose an improved algorithm——QBSQ* which given the lack of QBSQ inhigh-dimension space. The algorithm solves Skyline query problem in high-dimension space by means of a partition method for low-dimension space. It draw rein of memory options and thus increases its feasibility. Finally, we validate our algorithms with extensive experiments in many datasets and the results have shown that QBSQ and its improved algorithm are correct and efficient.