K-Dominant Skyline Computation Using Simplified Presort
Lei Zhao · Journal of Chinese Computer Systems · 2013
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 dominates another one is reduced significantly.As a result,the number of skyline points becomes too numerous to provide any useful information.Recently,k-dominant skyline query has been introduced,which can reduce the number of retrieved points by relaxing the definition of dominance.Existing k-dominant skyline query algorithms are divided into no indexing and index based types.The no indexing algorithm performs poorly on high dimensional space and anti-correlated data.And the index-based algorithm spends a lot of time to build the index.The overall efficiency is not high.In this paper,we propose a simplified pre-sorted algorithm(SPA) to solve the problem of k-dominant skyline computation.Theoretical arguments and experimental data show that the SPA algorithm is more efficient than all of the existing methods.