Progressive skyline computation in database systems
Progressive skyline computation in database systems
复制标题
DOI：
10.1145/1061318.1061320
复制
发表时间：
2005-03-01
影响因子：
1.8
通讯作者：
Seeger, B
中科院分区：
文献类型：
--
作者：
Papadias, D;Tao, YF;Seeger, B
d维数据集的天际线包含所有维度上不受任何其他点支配的点。Skyline计算最近在数据库社区中受到了相当大的关注，特别是对于可以快速返回初始结果而无需阅读整个数据库的渐进式方法。然而，所有现有的算法都存在一些严重的缺点，限制了它们在实际中的应用。在这篇文章中，我们开发的分支定界天际线（BBS），一个算法的基础上最近的邻居搜索，这是I/O最优的，也就是说，它只执行一个单一的访问，这些节点可能包含天际线点。BBS易于实现并且支持所有类型的渐进处理（例如，用户偏好、任意维度等）。此外，我们提出了几个有趣的变化的天际线计算，并显示如何BBS可以应用于其有效的处理。
The skyline of a d-dimensional dataset contains the points that are not dominated by any other point on all dimensions. Skyline computation has recently received considerable attention in the database community, especially for progressive methods that can quickly return the initial results without reading the entire database. All the existing algorithms, however, have some serious shortcomings which limit their applicability in practice. In this article we develop branch-and-bound skyline (BBS), an algorithm based on nearest-neighbor search, which is I/O optimal, that is, it performs a single access only to those nodes that may contain skyline points. BBS is simple to implement and supports all types of progressive processing (e.g., user preferences, arbitrary dimensionality, etc). Furthermore, we propose several interesting variations of skyline computation, and show how BBS can be applied for their efficient processing.