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

Area of Science:

• Computer Science
• Data Mining
• Machine Learning

Background:

• Locality Sensitive Hashing (LSH) is vital for efficient similarity joins in high-dimensional datasets.
• LSH performance hinges on managing false positives and false negatives.
• Reducing false positives is critical, while some applications require balancing both error types.

Purpose of the Study:

• To introduce Personalized Locality Sensitive Hashing (PLSH) for fine-grained control over LSH error rates.
• To develop a novel banding scheme within PLSH to tailor false positives, false negatives, and their sum.
• To enable efficient, large-scale similarity joins using a parallel MapReduce implementation of PLSH.

Main Methods:

• Developed a novel banding scheme for Personalized Locality Sensitive Hashing (PLSH).
• Implemented PLSH in parallel using the MapReduce framework for scalability.
• Conducted experiments on both real and simulated high-dimensional datasets.

Main Results:

• PLSH effectively allows users to adjust the trade-off between false positives and false negatives.
• The parallel MapReduce implementation demonstrates significant efficiency for large-scale data.
• Experimental results confirm PLSH's superiority over existing state-of-the-art methods.

Conclusions:

• PLSH provides a flexible and effective approach to similarity joins for high-dimensional data.
• The technique offers improved control over approximation errors compared to standard LSH.
• PLSH is a scalable solution for handling massive datasets in similarity search applications.