作者：朱睿; 王斌; 杨晓春; 王国仁乱序流数据哈希表组栈边界对象
摘要：Top-k 连续查询是流数据管理领域的经典问题，它监听窗口内的数据.当窗口滑动时,该查询返回窗口内分值最高的 k 个元素.许多学者已针对该问题展开研究，并提出一系列高效算法.然而，现有算法的假设条件是流数据是以顺序的形式到达窗口，这一假设在实际应用中显然是不成立的.更重要的是，这些算法对于数据间的时序关系非常敏感，这导致它们在乱序环境下无法高效工作.鉴于乱序流的普遍性和top-k 连续查询的重要性，该文基于滑动窗口模型研究高速乱序环境下的top-k 连续查询问题.和传统的问题定义不同,该查询返回窗口中满足时序约束条件的 k 个分值最高的对象.该文提出查询处理框架GSTopK支持该查询.该框架的核心思想是维护窗口中对象集合的一个子集.当窗口滑动时，新的查询结果可在该子集中找到.为了高效维护候选集，GSTopK一方面需高效过滤新流入窗口的数据中不可能成为查询结果的对象,从而降低候选集的更新频率.另一方面，GSTopK需降低乱序对算法带来影响.为达到上述两个目标,该文首先提出边界窗口和边界对象的概念.以此为基础,该文提出了两种面向不同分布的哈希过滤器.它们将边界对象的分值作为键值从而过滤产生于不同时刻的乱序数据.对于被过滤的对象，算法保证它们不会成为查询结果.对于无法被过滤的对象,该文提出一种基于栈操作的候选对象维护算法.和已有算法相比,该算法不仅效率更高而且对数据的时序关系不敏感.假设窗口长度为 N ，流速为 s ，GSTopK可将原有算法的时间复杂度从 O（N） 降低到 O （max（ 1,Nk/s^2 ）） .最后,通过大量实验验证了该文所提出算法的有效性.
注：因版权方要求，不能公开全文，如需全文，请咨询杂志社
