Research Of Parallel All Pairs Similarity Search On CUDA

All-Pairs Similarity Search(APSS)has been widely used in many fields of computer science,such as information retrieval,data mining and database.It is a crucial process in many applications,such as near-duplicate document detection,collaborative filtering and clustering.Thus,many research have been done into this problem.Many serial algorithms have been proposed by using pruning policy to decrease the possible similarity candidates for each query object.However,the efficiency of those serial algorithms degrade badly as the threshold decreases.The parallel implementations based on OpenMP or MapReduce also adopt the pruning policy and do not solve the problem thoroughly.In this context,this paper does research into the All-Pairs cosine similarity search problem,and introduces two parallel APSS algorithms on CUDA.The main work of this paper is as follows:(1)Designing data structures for high dimensional sparse vectors on CUDA.This paper proposed SFL(Segmented-based Forward List)for coalesced memory access;It proposes CU-IL(CUDA-based Inverted List)to avoid unnecessary computations;Combining SFL and CU-IL,a hybrid structure HSV(Hybrid Sparse Vector)is introduced to compromise between the memory visiting and dot-product computing.(2)Introducing and implementing a parallel APSS algorithm FCuAPSS.It computes similarities on the forward list and uses shared memory to optimize the performance.Experimental results show that FCuAPSS has good acceleration results and verify the effectiveness of the optimization method of shared memory.(3)Developing and implementing CuAPSS on the hybrid structure to overcome theshortcomings of FCuAPSS.CuAPSS combines a pair-parallel scan and a feature-parallel scan executed on different parts of vectors.Then,a parameter tuning method is proposed to achieve the best performance.Experimental results show that CuAPSS achieves speedups of 14x-85x against cuSPARSE and 1.5x-23x against the state-of-the-art algorithm,while keeps a stable running time with different thresholds.