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

摘要：

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

关键词：梯队列、数据流、查询处理、存储优化

所属期刊栏目：37

分类号：TP311(计算技术、计算机技术)

资助基金：国家高技术研究发展计划863计划项目2007AA01Z309;国家自然科学基金60873030;国家国防预研基金9140A04010209JW0504和9140A15040208JW0501;湖北省自然科学基金

在线出版日期：2010-08-31（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：191-195