Stabbing the sky: efficient skyline computation over sliding windows
Stabbing the sky: efficient skyline computation over sliding windows
复制标题
DOI：
10.1109/icde.2005.137
复制
发表时间：
2005-04
期刊：
影响因子：
--
通讯作者：
Xuemin Lin;Yidong Yuan;Wei Wang-;Hongjun Lu
中科院分区：
文献类型：
--
作者：
Xuemin Lin;Yidong Yuan;Wei Wang-;Hongjun Lu
我们考虑的问题，有效地计算天际线对最近的N个元素的数据流中看到迄今为止。具体来说，我们研究了N的N天际线查询，也就是说，计算最近的n（/spl forall/n/spl les/N）元素的天际线。首先，我们开发了一种有效的修剪技术，以尽量减少要保留的元素的数量。可以表明，如果每个维度上的数据分布是独立的，则平均仅存储来自最近N个元素的O（log/sup d/ N）个元素足以支持d维空间中的所有N个中的n个skyline查询的精确计算。然后，提出了一种新的编码方案，连同有效的更新技术，存储的元素，使计算一个N的N的天际线查询在d维空间需要O（log N+s）的时间减少到O（d log N + s），如果数据分布是独立的，其中s是天际线点的数量。第三，提供了一种新颖的基于触发器的技术来处理连续的N个中的N个skyline查询，其中每个新数据元素更新当前结果的时间为O（/spl delta/），每个结果变化更新触发器列表的时间为O（log s），其中/spl delta/是从当前结果到新结果的元素变化的数量。最后，我们将我们的技术扩展到计算最近N个元素中任意窗口的天际线。除了理论上的性能保证，我们广泛的实验表明，新技术可以支持非常快速的数据流上的在线skyline查询计算。
We consider the problem of efficiently computing the skyline against the most recent N elements in a data stream seen so far. Specifically, we study the n-of-N skyline queries; that is, computing the skyline for the most recent n (/spl forall/n/spl les/N) elements. Firstly, we developed an effective pruning technique to minimize the number of elements to be kept. It can be shown that on average storing only O(log/sup d/ N) elements from the most recent N elements is sufficient to support the precise computation of all n-of-N skyline queries in a d-dimension space if the data distribution on each dimension is independent. Then, a novel encoding scheme is proposed, together with efficient update techniques, for the stored elements, so that computing an n-of-N skyline query in a d-dimension space takes O(log N+s) time that is reduced to O(d log log N+s) if the data distribution is independent, where s is the number of skyline points. Thirdly, a novel trigger based technique is provided to process continuous n-of-N skyline queries with O(/spl delta/) time to update the current result per new data element and O(log s) time to update the trigger list per result change, where /spl delta/ is the number of element changes from the current result to the new result. Finally, we extend our techniques to computing the skyline against an arbitrary window in the most recent N element. Besides theoretical performance guarantees, our extensive experiments demonstrated that the new techniques can support on-line skyline query computation over very rapid data streams.