An efficient similarity join approach on large-scale high-dimensional data using random projection

摘要

Similarity join on large-scale high-dimensional data faces major challenges because of the datascale and the cure of dimensionality. Random projection with p-stable distribution can reducethe high-dimensional data form d-dimension to k-dimension (k ≪ d), the distance of the datain k-dimensional space can be used to filter out as many data pairs as possible at relative lowcost. Based on the above idea, we proposed two novel approaches to deal with large-scalehigh-dimensional data similarity join: projection-based similarity join (PromSimJ) algorithm andprojection space partitioning–based similarity join (ProSPSimJ) algorithm. The comprehensiveexperiments were performed to test the performance of the above methods.We also comparedthe performance of the above methods with that of the naive method block nested loop join.The final experimental results prove that our approaches have much better performance andgood scalability.