Summary original text

RWSL Assignment Part two of the Continuous Assessment –Summary original text ISBN 978-1-4503-2202-7 Lars Kolb, Andreas Thor, and Erhard Rahm. 2013. Don't match twice: redundancy-free similarity computation with MapReduce. In Proceedings of the Second Workshop on Data Analytics in the Cloud (DanaC '13). ACM, New York, NY, USA, 1-5. DOI=10.1145/2486767.2486768 http://doi.acm.org/10.1145/2486767.2486768 ISBN: 978-1-4503-2202-7 Original text 1. INTRODUCTION Pair-wise similarity computation (PSC) is an important aspect of many data-intensive applications, e.g., identifying similar documents for clustering [10], efficient set-similarity joins in databases [16], or identifying duplicates (entity resolution) [8]. PSC usually is an expensive operation because it is inherently of O(n2) complexity and typically involves complex (string) similarity functions. Therefore, it particularly benefits from the parallel MapReduce (MR) model and we observe an increasing number of MapReduce-based PSC implementations [4, 15, 3, 6, 14, 11]. The na¨ıve approach for PSC examines the complete Cartesian product of object pairs. The resulting quadratic complexity is intolerable for large datasets even when using MR. A common approach is pruning the search space to avoid processing pairs with presumably low similarity. This is achieved by grouping objects into (possibly overlapping) clusters and restricting similarity computation to objects of the same data cluster. To this end, many MR implementations follow a similar strategy: For each object (e.g., document, string, or entity) one or more signatures (e.g., terms, tokens, or blocking keys) are generated. A signature identifies a particular cluster and objects are assigned to all clusters of their signatures. The map phase emits a (key=signature, value=object) pair for each signature. The MR framework then groups all pairs based on their key (signature) and thus groups together objects of the same cluster. The actual similarity (match) computation is performed within the reduce phase, i.e., all objects of the same clusters are compared with each other. The creation of appropriate signatures for objects is difficult because it has to balance between efficiency and data quality. On the one hand, cluster sizes should be as small as possible to reduce the number of pairs and thus increase efficiency. On the other hand, small cluster sizes tend to miss similar object pairs especially for dirty (web) data. For example, if customer objects are clustered by their location, wrong or missing zip codes may place very similar objects into different clusters. Many approaches such as document clustering [10], entity resolution [8], or sequence alignment [14] therefore make use of multiple signatures per object to ensure that similar objects are still grouped together for comparison even in the presence of data quality issues. For example, entity resolution approaches frequently apply standard blocking [2] for generating blocking keys (signatures) based on the values of one or several entity attributes. Blocking keys for finding duplicates customers in enterprise databases can be the first three letters of the customer’s name or zip code. Due to common data quality issues, e.g., missing or false zip code, it is of crucial importance to utilize several blocking keys (multi-pass blocking) to achieve sufficient match pair completeness and thus match quality compared to single-pass blocking. The sketched na¨ıve MR-based implementation for PSC is unaware of redundancy introduced by multiple signatures per object. If an object pair shares more than one signature, it will be redundantly compared by several reduce tasks that are likely to be executed on different nodes. This unnecessary computation obviously deteriorates the run-time efficiency. Consequently, eliminating redundant pair comparison is a promising optimization approach. Lars Kolb, Andreas Thor, and Erhard Rahm, (2013) ‘Don’t match twice: redundancy-free similarity computation with MapReduce’ In Proceedings of the Second Workshop on Data Analytics in the Cloud (DanaC '13), ACM, New York, NY, USA, 1-5. DOI=10.1145/2486767.2486768 URL: http://doi.acm.org/10.1145/2486767.2486768 [Accessed 25 November 2013]