基于聚类的逆向Skyline查询算法

Efficient Reverse Skyline Queries Based on Clustering

逆向Skyline查询能够应用到诸如决策支持、用户偏好支持以及市场行为分析等方面。由于参考对象q的存在,在执行逆向Skyline查询的过程中数据空间被划分成许多分区。然而,存在的算法都没有考虑这个问题的影响,直接使用原始数据集建立索引结构。本文提出了一种新的逆向Skyline查询方法CRSQ,它考虑了这个问题。CRSQ首先根据查询对象q对数据进行聚类,然后建立R-tree索引,最后利用高效修剪策略修剪索引搜索空间。实验结果表明CRSQ算法是有效的,它相对于没有聚类技术的算法获得了50%以上的性能提高。

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.