基于高速乱序流的Top-k连续查询算法
Top-k连续查询是流数据管理领域的经典问题,它监听窗口内的数据.当窗口滑动时,该查询返回窗口内分值最高的k个元素.许多学者已针对该问题展开研究,并提出一系列高效算法.然而,现有算法的假设条件是流数据是以顺序的形式到达窗口,这一假设在实际应用中显然是不成立的.更重要的是·这些算法对于数据间的时序关系非常敏感,这导致它们在乱序环境下无法高效工作.鉴于乱序流的普遍性和top-k连续查询的重要性,该文基于滑动窗口模型研究高速乱序环境下的top-k连续查询问题.和传统的问题定义不同,该查询返回窗口中满足时序约束条件的k个分值最高的对象.该文提出查询处理框架GSTopK支持该查询.该框架的核心思想是维护窗口中对象集合的一个子集.当窗口滑动时,新的查询结果可在该子集中找到.为了高效维护候选集,GSTopK一方面需高效过滤新流入窗口的数据中不可能成为查询结果的对象,从而降低候选集的更新频率.另一方面,GSTopK需降低乱序对算法带来影响.为达到上述两个目标,该文首先提出边界窗口和边界对象的概念.以此为基础,该文提出了两种面向不同分布的哈希过滤器.它们将边界对象的分值作为键值从而过滤产生于不同时刻的乱序数据.对于被过滤的对象,算法保证它们不会成为查询结果.对于无法被过滤的对象,该文提出一种基于栈操作的候选对象维护算法.和已有算法相比,该算法不仅效率更高而且对数据的时序关系不敏感.假设窗口长度为N,流速为s,GSTopK可将原有算法的时间复杂度从O(N)降低到O(max(1,Nk/s2)).最后,通过大量实验验证了该文所提出算法的有效性.
top-k查询、乱序流数据、哈希表、组栈、边界对象
41
TP311(计算技术、计算机技术)
国家优秀青年科学基金61322208;国家自然科学基金61702344,61272178,U1401256,61532021
2018-09-20（万方平台首次上网日期，不代表论文的发表时间）
共16页
1693-1708
