论文部分内容阅读
相似对搜索广泛应用于信息检索、数据挖掘、数据库等计算机科学领域,也是大量实际应用中的关键步骤,例如副本检测、协同过滤以及聚类等,因而得到深入研究。串行相似对搜索算法主要基于过滤策略减少查询对象的相似候选项。然而,随着相似性阈值减小,串行算法的性能严重降低。基于MapReduce或OpenMP的并行相似对搜索算法大多也采用过滤策略,因此也没有完全地解决这个问题。本文针对余弦相似度的相似对搜索问题进行了研究,提出了两种基于CUDA并行相似对搜索算法,主要工作如下:(1)基于CUDA架构设计了几种高维稀疏向量数据结构。本文提出了基于分段的前向表结构SFL(Segment-based Forward List),可以有效地实现内存合并访问;提出了倒排表结构CU-IL(CUDA-based Inverted List),避免了不必要的点积计算;结合上述两种数据结构,提出了一种混合型结构HSV(Hybrid Sparse Vector),可以在内存访问和点积运算之间取得一个折中。(2)提出并实现了一种新的基于CUDA架构的并行相似对搜索算法FCuAPSS。该算法基于前向表结构计算相似度,并使用共享内存优化算法性能。实验结果表明FCuAPSS取得了不错的加速效果,验证了共享内存优化方法的有效性。(3)为了克服FCuAPSS的缺点,提出并实现了一种混合结构的相似对搜索算法CuAPSS。CuAPSS结合向量对并行扫描和特征对并行扫描两种不同的方法,在向量的不同部分分别执行这两种方法。然后,本文提出针对参数p的调整方法,通过调整p,CuAPSS达到最优性能。实验结果表明CuAPSS取得了显著的加速效果,与CUDA库cuSPARSE相比CuAPSS取得14-85倍的加速比,与当前最优的并行算法相比CuAPSS能够达到1.5-23倍的加速比,而且在不同阈值下保持稳定的执行时间。