概率数据上基于emd距离的并行top-k相似性连接算法

以无线传感器网络为代表的新型数据应用和以图像处理为基础的传统数据应用都产生了大规模的概率数据.在概率数据的管理中，top-k相似性连接操作返回最相似的k对概率数据，具有重要应用价值.直方图是最常用的概率数据模型之一，而emd（earthmover’sdistance）距离因其较强的鲁棒性可更准确地量化直方图概率数据之间的相似性.然而emd距离的计算却具有三次方的时间复杂度，给基于emd距离的top-k相似性连接带来巨大挑战.基于流行的mapreduce并行处理框架，利用emd距离对偶线性规划问题的优良特性，提出了两种大规模概率数据上基于emd距离的top-k相似性连接算法.首先提出基于块嵌套循环连接思想的基本解决方法，命名为top-kbnlj算法.进而改进数据划分策略，提出基于数据局部性进行数据划分的top-kdlpj算法，有效降低了mapreduce作业执行过程中的数据传输量.使用大规模真实数据集对两种算法进行评估，证实了本文提出的top-kdlpj算法的高效性和处理大规模数据集时的良好扩展性.