很多交互系统需要实时返回潜在的数据空间中最重要的前k条记录,即为top-k查询。当今大数据时代,面对海量更加复杂的数据,输出这种top-k记录是一个非常具有挑战性的问题。传统的方案主要采用基于阈值的方法,然而对分布式系统来说,这些方法是比较耗时的,并且需要巨大的通信量。随着网络流量的增加,这些问题会变得无法解决。本文提出了一种新颖的top-k算法PCMRA(Data Partitioning and COIT Indexing Top-k query Algorithm based on MapReduce)。该解决方案构造了预处理结构COIT(候选对象索引表),并采用数据分割策略和并行编程框架MapReduce,一轮通信就可以完成top-k查询。此外本文还对算法给出了正确性证明和理论分析,并且实验表明该算法仅需要较小的空间开销和较短的时间代价,即可筛选出较少的候选对象,大幅度节约了计算和通信资源,并且算法具有良好的可扩展性。
展开▼
