武守晓，房 俊

(1.北方工业大学 大规模流数据集成与分析技术北京市重点实验室 北京 100144；2.北方工业大学 数据工程研究院 北京 100144)

0 引言

目前处理乱序流的主流方法是基于缓存的方法。基于缓存的方法使用开辟的缓冲区等待迟到数据，对缓冲区内数据进行排序，以避免系统处理乱序数据。传统的基于缓存的K-slack[1]方法和MP-K-slack[2]方法无法做到对缓冲区大小自适应，在时延变小的情况下会浪费系统资源。AQ-K-slack[3]虽然实现了缓冲区自适应，但无法应用于top-k连续查询这类复杂的聚合函数。在具体的top-k连续查询算法中，SMA算法[4]利用k-skyband对象在有序流上快速进行top-k连续查询，但需要维护大量的k-skyband对象，内存耗费大，并且该方法只能在有序流上使用。MinTopk算法[5]维护了一个最小的top-k候选集，每次计算都从该候选集中得出结果，大大减少了计算量，但在乱序流上使用会有误差。GSTopk算法[6]对MinTopk算法进行了一些改良，使其能在乱序流下立刻给出近似结果，可以在时效性要求较高的情况下使用。在上述算法的基础上，本文提出一种面向高速乱序数据流的top-k连续查询方法。首先使用基于缓存的乱序流处理技术，舍弃缓存数据重排序步骤，缓存时长的确定使用缓存时长自适应算法，在保证用户允许的最小正确率的情况下计算出最小缓存时长，其次使用改造的MinTopk算法计算当前窗口的top-k结果集。实验结果表明，该方法能有效权衡查询精度和查询时延之间的关系，对窗口内数据执行快速且高效的查询并得出结果，使乱序流下的top-k连续查询收到了良好的效果。……