基于重用技术的相互Skyline查询算法

Reusing technology-based mutual Skyline query algorithm

提出了一种新的Skyline查询,即相互Skyline查询(MSQ).给定一个对象集合P和一个查询对象q,MSQ返回一个对象集合,它的每个对象既在q的动态Skyline中,同时也在q的可逆Skyline中.基于传统的R-tree索引、重用堆信息技术以及启发式的修剪策略,显著降低了I/O成本,改进了基于BBS算法和BBRS算法实现的MSQ算法.几个真实数据集的实验表明提出的算法有效而高效,比一般MSQ算法快几个数量级.

A novel Skyline query,namely,mutual Skyline query （MSQ） was proposed. Given a set of objects P and a query object q,a MSQ returns from P,the set of objects that were among the dynamic Skyline of q; meanwhile,among the reverse Skyline of q. Although MSQ has played an important role in many applications,such as multi-criteria decision making,market analysis,and task allocation,it cannot be efficiently computed by existing Skyline query algorithms. The first piece of work for tackling MSQ efficiently was presented. A conventional data-partitioning index （e.g.,R-tree,etc） on the data sets was used in this approach; the state-of-the-art Skyline query techniques including BBS （branch and bound Skyline） and BBRS （branch and bound reverse Skyline） algorithm were employed,the reuse heap technique and heuristic search policy were used so as to deduce the I/O cost. An extensive empirical study demonstrates the efficiency and effectiveness of our proposed algorithm. It outperforms the simple algorithm usually by orders of magnitude under all problem instances.