Efficient Reverse Skyline Queries Based on Clustering
Yang Ping · Journal of Hengyang Normal University · 2010
Reverse skyline queries(RSQ) have many important applications such as decision-support,preference support,and market behavior analyzing.Due to the existence of reference object q,the data space generally is divided into many partitions according to q during the procedure of executing RSQ.However,existing algorithms do not consider the problem and directly build the index using the original data sets.In the paper,we propose a novel algorithm for reverse skyline query,namely CRSQ(clustering for reverse skyline queries),taking it into consideration.CRSQ firstly clusters all objects according to q and then indexes them into an R-tree index.At last,CRSQ executes the query on R-tree by some efficient pruning policies.The results of extensive experiments show that our method is effective and efficient and it wins at least a 50 % performance improvement compared with the algorithm without clustering method.