Scalable skyline computation using object-based space partitioning
Scalable skyline computation using object-based space partitioning
复制标题
DOI：
10.1145/1559845.1559897
复制
发表时间：
2009-06
期刊：
影响因子：
--
通讯作者：
Shiming Zhang;N. Mamoulis;D. Cheung
中科院分区：
文献类型：
--
作者：
Shiming Zhang;N. Mamoulis;D. Cheung
Skyline运算符从一组多维对象返回一个不受其他对象主导的优质对象的子集。该操作在大型数据集的多目标分析中被认为非常重要。尽管已经提出了大量的天际线方法，但其中大多数集中于最小化I/O成本。但是，在高维空间中，由于在扫描数据库时将对象与当前的天际线点进行比较所需的大量计算，因此问题很容易成为CPU。基于此观察，我们为天际线提出了一种动态索引技术，可以集成到基于最新的基于排序的天际线算法中，以提高其计算性能。新的索引和优势检查方法得到了理论分析的支持，而我们的实验表明，它可以很好地扩展输入大小和维度，这不仅是因为避免了不必要的优势检查，而且还因为它允许借助于位行动操作的有效优势检查。
The skyline operator returns from a set of multi-dimensional objects a subset of superior objects that are not dominated by others. This operation is considered very important in multi-objective analysis of large datasets. Although a large number of skyline methods have been proposed, the majority of them focuses on minimizing the I/O cost. However, in high dimensional spaces, the problem can easily become CPU-bound due to the large number of computations required for comparing objects with current skyline points while scanning the database. Based on this observation, we propose a dynamic indexing technique for skyline points that can be integrated into state-of-the-art sort-based skyline algorithms to boost their computational performance. The new indexing and dominance checking approach is supported by a theoretical analysis, while our experiments show that it scales well with the input size and dimensionality not only because unnecessary dominance checks are avoided but also because it allows efficient dominance checking with the help of bitwise operations.