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