Efficient entity matching using materialized lists

Abstract

Entity matching (EM) is the task of identifying records that refer to the same entity from different sources. EM is widely used in real-world applications such as data integration and data cleaning, but the naive method of EM leads to exhaustive pair-wise comparisons. To enhance the efficiency of EM, we transform EM into the top-k query problem of identifying the best k results for a given match function, and propose a new EM algorithm using pre-materialized lists, which refer to the sorted lists of record pairs. Our proposed algorithm identifies the EM results with sub-linear cost using the materialized lists. Because it requires us to materialize the sorted lists with all record pairs, however, this approach can be impractical. To address this problem, we reduce the size of the materialized lists, which stores only 1% of all pairs without sacrificing EM accuracy. This method is inspired by the notion of skyline queries. In addition, we extend our proposed framework to collective entity matching that exploits both attributes and the reference relationships across records. Experimental results show that the proposed algorithms are an order of magnitude faster than the state-of-the-art algorithms without compromising accuracy. (C) 2013 Elsevier Inc. All rights reserved.