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 (∀n≤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(logd 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(δ) time to update the current result per new data element and O(log s) time to update the trigger list per result change, where δ 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.
展开▼
机译：我们考虑了针对迄今看到的数据流中最新的N个元素有效计算天际线的问题。具体来说，我们研究了n个n个天际线查询；也就是说，计算最近的n（∀n≤N）个元素的天际线。首先，我们开发了一种有效的修剪技术，以尽量减少要保留的元素数量。可以证明，平均而言，仅存储最近N个元素中的O（log d N）个元素就足以支持在d维中对所有N个天际线查询的精确计算。如果每个维度上的数据分布是独立的，则为空格。然后，针对存储的元素，提出了一种新颖的编码方案以及有效的更新技术，从而在d维空间中计算n个n的天际线查询会占用O（log N + s）时间，该时间减少为如果数据分布是独立的，则为O（d log log N + s），其中s是天际点数。第三，提供了一种新颖的基于触发器的技术来处理N个连续的n个天际线查询，其中O（δ）时间用于更新每个新数据元素的当前结果，O（log s）时间用于根据结果更改来更新触发器列表，其中δ是元素从当前结果更改为新结果的次数。最后，我们将技术扩展到针对最近的N个元素中的任意窗口计算天际线。除了理论上的性能保证之外，我们的大量实验表明，新技术可以支持非常快速的数据流上的在线天际线查询计算。
展开▼
