滑动窗口连续查询结果存储优化

Storage Optimization for Continuous Query over Sliding Window Based on Ladder Queue

在数据流滑动窗口查询研究领域中,考虑查询结果失效的连续查询成为了一个新的研究热点。查询结果的维护代价直接影响连续查询效率。根据对不同更新模式连续查询结果的分析,提出了一种带分支链表的梯队列来维护滑动窗口连续查询结果。它利用分支链表结构收集具有相同截止期的数据,采用梯队列的"产卵"机制,能适应具有各种不同分布的数据维护,且能达到O(1)的均摊(amortized)时间复杂度。实验表明,该结构显著提高了滑动窗口连续查询效率,明显优于同类结构。

Query processing optimization based on update pattern awareness is a new hot topic in the research field of continuous queries over sliding window. Efficiency of continuous query processing highly depends on overhead of result state maintenance. This investigation proposed a ladder queue with branch lists to maintain result state of continuous query. The trunk list and the branch list were designed into the ladder queue. The ladder queue used the branch lists to gather the result tuples with the identical expiration time, and employed ＂spawning＂ mechanism to achieve O（1） amortized access time complexity for result data under the different distributions. Our experiments showed that the new ladder queue can improve the performance of query processing greatly and outperforms other data structures.