论文部分内容阅读
随着互联网行业的快速发展，如何快速高效处理大规模实时数据成为当前研究重点。可持续Top-K查询算法主要是用于流数据的应用上，基于某种函数关系实时选取得分最高的K项。这种算法在一些实时应用中被广泛使用的算法，例如，网络监控、金融分析和实时推荐。MinTopK算法是Di Yang在2011年提出来的可持续Top-K查询算法，是解决以前的算法存在需要重计算的问题。由于重计算操作会需要大量计算资源。MinTopK算法，定义了最小Top-K候选集合，保证后续的查询窗口计算所需要的子集。MinTopK算法维持最小Top-K候选集合，消除需要重计算，比以往的算法有着更好的CPU和内存利用。MinTopK算法是单机串行的算法。由于单机的网络、CPU等资源的限制，无法满足当前大数据量的计算要求。分布式计算方法是一种常见有效的解决方式。 本文研究的是如何将MinTopK算法用于分布式计算，解决流数据的数据量大和计算复杂度高的问题。本文将连续的流数据转化为离散的流数据来处理，设计了并行化的 MinTopK算法的基本模型，同时满足于 MapReduce架构和Spark系统等分布式处理工具的编程模型。从算法的时间复杂度，空间复杂度和通信开销三个方面来，说明本文设计的算法具有无锁的、高效的、空间低和通信量小的特点。 通过实验数据分析，并行化的MinTopK算法相对于原来的算法是具有良好的加速比和扩展性，能够在slide的时间内处理好数据，避免累计时间造成的用户体验不好的问题。通过实验说明Super-Top-K链表的平均长度是2K的，可以将Super-Top-K链表与Top-K候选数据集整合操作在一个计算节点上完成。