MapReduce Based Personalized Locality Sensitive Hashing for Similarity Joins on Large Scale Data

摘要

Locality Sensitive Hashing (LSH) has been proposed as an efficient techniquefor similarity joins for high dimensional data. The efficiency and approximationrate of LSH depend on the number of generated false positive instances and falsenegative instances. In many domains, reducing the number of false positives iscrucial. Furthermore, in some application scenarios, balancing false positives andfalse negatives is favored. To address these problems, in this paper we proposePersonalized Locality Sensitive Hashing (PLSH), where a new banding scheme isembedded to tailor the number of false positives, false negatives, and the sum ofboth. PLSH is implemented in parallel using MapReduce framework to deal withsimilarity joins on large scale data. Experimental studies on real and simulated dataverify the efficiency and effectiveness of our proposed PLSH technique, comparedwith state-of-the-art methods.