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

Abstract: Query processing optimisation 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 ctueue 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) amortined 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.

Key words: Ladder queue, Data stream, Query processing, Storage optimization