Efficient and scalable graph similarity joins in MapReduce.

Area of Science:

• Computer Science
• Data Mining
• Graph Databases

Background:

• Massive graph-modeled data necessitates efficient similarity analysis.
• Applications include data cleaning and near-duplicate detection.
• Existing methods struggle with scalability for large graph datasets.

Purpose of the Study:

• To propose a scalable algorithm for graph similarity joins with edit distance constraints.
• To enhance efficiency by optimizing the filtering and verification phases.
• To address the challenge of managing large numbers of key-value pairs in MapReduce.

Main Methods:

• Developed MGSJoin, a MapReduce-based algorithm employing a filtering-verification framework.
• Utilized overlapping graph signatures for initial candidate filtering.
• Introduced spectral Bloom filters to reduce key-value pairs during filtering.
• Integrated a multiway join strategy and MapReduce for efficient Graph Edit Distance (GED) calculation during verification.

Main Results:

• MGSJoin demonstrates superior efficiency and scalability compared to existing methods.
• The use of spectral Bloom filters effectively reduces the number of key-value pairs.
• The integrated multiway join strategy and GED calculation enhance verification performance.

Conclusions:

• MGSJoin provides an efficient and scalable solution for graph similarity joins with edit distance constraints.
• The proposed techniques, including spectral Bloom filters and multiway joins, significantly improve performance.
• This algorithm is well-suited for handling large-scale graph data analysis.