高效的子空间可逆skyline查询算法

Efficient reverse skyline querie algorithm in subspaces

提出了一种高效的子空间可逆skyline查询算法RSQS.该算法采用基于分区的B+树对可逆Skyline进行计算,不同于传统的R-tree修剪方法;RSQS利用提出的几种修剪策略,包括相互修剪、预计算、尽早终止搜索等,采用过滤-精炼框架实现,能快速地修剪搜索空间,避免了大部分的I/O操作.实验结果表明:RSQS算法具有极高的修剪能力和很高的效率:在二维子空间中每个对象平均仅需与约1.2个其他对象比较.

A reverse skyline query （RSQ） can identify the influence of a query object on a multidimensional dataset with regard to a vector of distances. An efficient algorithm, RSQS （reverse skyline queries in subspaces）, is proposed. In the paper, we firstly analyzed the characteristics of RSQ in subspaces and then provided some pruning rules for it, for example, mutual pruning policy, pre-eomputing method so as to directly choose the reverse skyline objects, early stopping seovrch, and filter-refine policy, etc. These pruning rules dramatically reduce the search space so that RSQS only has a few of I/O operations. At last, RSQS were implemented on two type B＋ tree indexes, which can efficiently prune non reverse skyline objects. Several groups of comprehensive experiments have been conducted using three real data sets. The results show that RSQS is effective and efficient. Especially, RSQS provides a high pruning capacity because each object only needs to compare 1.2 times with other objects in two dimensional subspaces.