Don't match twice: redundancy-free similarity computation with MapReduce

ABSTRACT

To improve the effectiveness of pair-wise similarity computation, state-of-the-art approaches assign objects to multiple overlapping clusters. This introduces redundant pair comparisons when similar objects share more than one cluster. We propose an approach that eliminates such redundant comparisons and that can be easily integrated into existing MapReduce implementations. We evaluate the approach on a real cloud infrastructure and show its effectiveness for all degrees of redundancy.

References

1. R. Baraglia, G. D. F. Morales, and C. Lucchese. Document Similarity Self-Join with MapReduce. In ICDM, 2010.
2. P. Christen. A Survey of Indexing Techniques for Scalable Record Linkage and Deduplication. IEEE Trans. Knowl. Data Eng., 24(9), 2012.
3. J. Ekanayake, T. Gunarathne, and J. Qiu. Cloud Technologies for Bioinformatics Applications. IEEE Trans. Parallel Distrib. Syst., 22(6), 2011.
4. T. Elsayed, J. J. Lin, and D. W. Oard. Pairwise Document Similarity in Large Collections with MapReduce. In ACL (Short Papers), 2008.
5. L. Kolb, A. Thor, and E. Rahm. Dedoop: Efficient Deduplication with Hadoop. PVLDB, 5(12), 2012.
6. L. Kolb, A. Thor, and E. Rahm. Load Balancing for MapReduce-based Entity Resolution. In ICDE, 2012.
7. L. Kolb, A. Thor, and E. Rahm. Multi-pass Sorted Neighborhood Blocking with MapReduce. Computer Science - R&D, 27(1), 2012.
8. H. Köpcke and E. Rahm. Frameworks for entity matching: A comparison. Data Knowl. Eng., 69(2), 2010.
9. N. McNeill, H. Kardes, and A. Borthwick. Dynamic Record Blocking: Efficient Linking of Massive Databases in MapReduce. In QDB, 2012.
10. M. Mendes and L. Sacks. Evaluating fuzzy clustering for relevance-based information access. In IEEE FUZZ, volume 1, 2003.
11. C. Moretti, H. Bui, K. Hollingsworth, et al. All-Pairs: An Abstraction for Data-Intensive Computing on Campus Grids. IEEE Trans. Parallel Distrib. Syst., 21(1), 2010.
12. G. Papadakis, E. Ioannou, C. Niederée, et al. Eliminating the Redundancy in Blocking-based Entity Resolution Methods. In JCDL, 2011.
13. G. Papadakis and W. Nejdl. Efficient Entity Resolution for Large Heterogeneous Information Spaces. In ICDE Workshops, 2011.
14. M. C. Schatz. CloudBurst: highly sensitive read mapping with MapReduce. Bioinformatics, 25(11), 2009.
15. R. Vernica, M. J. Carey, and C. Li. Efficient parallel set-similarity joins using MapReduce. In Sigmod, 2010.
16. C. Xiao, W. Wang, X. Lin, et al. Efficient Similarity Joins for Near-Duplicate Detection. In WWW, 2008.

Index Terms

• Information systems

  • Information retrieval

    • Search engine architectures and scalability

      • Distributed retrieval

      • Peer-to-peer retrieval

  • Information storage systems

    • Storage architectures

      • Distributed storage