QBHSQ: A Quad-tree Based Algorithm for High-dimension Skyline Query

摘要

Query all skyline points in large high-dimension dataset is quite challenging and its space and computation overhead are massive. This paper presents QBHSQ, a novel Quad-tree based algorithm for skyline query in large high-dimension dataset. QBHSQ utilizes a partial dimension subset to partition dataset on high dimensional space by means of the configuration characters of quad-tree. Since amount of domination checking operators among non-domination sub-datasets can be reduced and large numbers of data points in high dimensional space are deleted while constructing tree, QBHSQ contributes to a better computation and space performance than traditional ones. Extensive experiments demonstrate the efficiency and the scalability of proposed algorithm.