论文部分内容阅读
相似性连接操作在网页副本检测、实体识别、数据清洗和图像检索等领域都有很广泛的应用,随着数据规模的不断增大,利用分布式并行框架处理大规模数据的相似性连接已经吸引了越来越多的科研工作者和商业公司的关注。而EMD(Earth Mover’s Distance)和Bregman Divergence等复杂距离度量因较强的鲁棒性及相似性度量结果更符合人类视觉等原因,被广泛应用于度量图像及语音等类型数据的相似性,但现有的关于上述复杂距离度量的相似性连接算法多只适用于集中式环境,无法满足大规模数据的处理需求,因此本文研究了利用MapReduce分布式并行处理框架解决面向复杂距离度量的大规模数据相似性连接的问题。首先基于块嵌套循环思想,使用随机均匀的数据划分方式,提出了MapReduce框架下基本的EMD-BNLJ算法和Breg-BNLJ算法,其中EMD-BNLJ算法可解决面向EMD距离的大规模数据Top-k相似性自连接问题,Breg-BNLJ算法可解决面向Bregman Divergence距离的大规模数据相似性连接问题。其次根据EMD距离对偶问题的特性,将原始数据映射到一维空间,之后设计了基于一维空间内数据位置局部性的数据划分策略,减少了不必要的通信开销,并通过采样估算计算代价设计了基于Quantile的负载均衡策略,保证了算法的负载均衡性,进而提出了面向EMD距离的大规模数据Top-k EMD-DLPJ目似性自连接算法。在真实数据集上进行的丰富实验证实,EMD-DLPJ算法的通信开销最多为EMD-BNLJ算法的1/5,而执行效率最高为EMD-BNLJ算法的6.9倍。最后利用Bregman Divergence距离计算的特点,设计了以VA-File分割原始数据空间的数据划分策略,可提前过滤掉不必要的距离计算,减少通信开销,进一步通过采样估算计算代价设计了基于前缀的数据分组策略,保证了算法的负载均衡性,进而提出了面向Bregman Divergence距离的大规模数据Breg-VAFJ相似性连接算法。在多种真实数据集上的大量实验证实,Breg-VAFJ算法的通信开销最多为Breg-BNLJ算法的1/3,而执行效率最高为Breg-BNLJ算法的4.8倍。本文研究了面向复杂距离度量EMD和Bregman Divergence的基于MapReduce的相似性连接技术,根据各距离的计算特性设计了可精确控制的针对原始数据集的数据划分方法,取代了基本的随机均匀划分方法,减少了MapReduce作业的通信开销。同时通过采样估算计算代价,设计了对应的负载均衡策略,有效地保证了MapReduce作业的负载均衡性。最终在多个真实数据集上的大量实验证实了本文提出的算法的高效性。