DeltaSky: Optimal Maintenance of Skyline Deletions without Exclusive Dominance Region Generation
DeltaSky: Optimal Maintenance of Skyline Deletions without Exclusive Dominance Region Generation
复制标题
DOI：
10.1109/icde.2007.367894
复制
发表时间：
2007-04
期刊：
影响因子：
--
通讯作者：
Ping Wu;D. Agrawal;Ö. Eğecioğlu;A. E. Abbadi
中科院分区：
文献类型：
--
作者：
Ping Wu;D. Agrawal;Ö. Eğecioğlu;A. E. Abbadi
本文讨论的问题，有效地维护一个物化的天际线视图，以响应天际线删除。虽然在skyline查询计算方面已经取得了重大进展，但同样重要但在很大程度上尚未解决的问题是skyline删除的增量维护。以前的工作建议使用所谓的独占优势区（EDR），以实现最佳的I/O性能的删除维护。然而，EDR的形状在更高维度中变得极其复杂，并且尚未开发出用于其计算的算法。我们推导出一个系统的方法来分解一个d维EDR到一个集合的超矩形。我们证明了这样的超矩形的数量是O（md），其中m是当前天际线结果的大小。然后，我们提出了一种新的算法DeltaSky确定是否一个中间R-树MBR与EDR相交，而不显式计算EDR本身。这将EDR交集检查的最差情况复杂度从O（md）降低到O（md）。因此，DeltaSky帮助分支和边界天际线算法实现删除维护的I/O最优性，只找到删除后新出现的天际线点。我们讨论的实施问题，并表明，DeltaSky可以有效地实现使用一个额外的B-树。此外，我们提出了两种优化技术，进一步降低了实际中的平均成本。大量的实验表明，DeltaSky实现了数量级的性能增益超过替代解决方案。
This paper addresses the problem of efficient maintenance of a materialized skyline view in response to skyline removals. While there has been significant progress on skyline query computation, an equally important but largely unanswered issue is on the incremental maintenance for skyline deletions. Previous work suggested the use of the so called exclusive dominance region (EDR) to achieve optimal I/O performance for deletion maintenance. However, the shape of an EDR becomes extremely complex in higher dimensions, and algorithms for its computation have not been developed. We derive a systematic way to decompose a d-dimensional EDR into a collection of hyper-rectangles. We show that the number of such hyper-rectangles is O(md), where m is the current skyline result size. We then propose a novel algorithm DeltaSky which determines whether an intermediate R-tree MBR intersects with the EDR without explicitly calculating the EDR itself. This reduces the worse case complexity of the EDR intersection check from O(md) to O(md). Thus DeltaSky helps the branch and bound skyline algorithm achieve I/O optimality for deletion maintenance by finding only the newly appeared skyline points after the deletion. We discuss implementation issues and show that DeltaSky can be efficiently implemented using one extra B-Tree. Moreover, we propose two optimization techniques which further reduce the average cost in practice. Extensive experiments demonstrate that DeltaSky achieves orders of magnitude performance gain over alternative solutions.