An analysis of one-to-one matching algorithms for entity resolution

• DOI: 10.1007/s00778-023-00791-3
• Publication Date: 2023-04-18T05:31:57Z
• Authors: George Papadakis; Vasilis Efthymiou; Emmanouil Thanos; Oktie Hassanzadeh; Peter Christen
• Keywords: Technology; Science & Technology; Computer Science, Information Systems; Experimental evaluation; 02 engineering and technology; Clustering; Record linkage; Computer Science; 0202 electrical engineering, electronic engineering, information engineering; Graph matching; Computer Science, Hardware & Architecture; Bipartite graphs

AbstractEntity resolution (ER) is the task of finding records that refer to the same real-world entities. A common scenario, which we refer to as Clean-Clean ER, is to resolve records across two clean sources (i.e., they are duplicate-free and contain one record per entity). Matching algorithms for Clean-Clean ER yield bipartite graphs, which are further processed by clustering algorithms to produce the end result. In this paper, we perform an extensive empirical evaluation of eight bipartite graph matching algorithms that take as input a bipartite similarity graph and provide as output a set of matched records. We consider a wide range of matching algorithms, including algorithms that have not previously been applied to ER, or have been evaluated only in other ER settings. We assess the relative performance of these algorithms with respect to accuracy and time efficiency over ten established real-world data sets, from which we generated over 700 different similarity graphs. Our results provide insights into the relative performance of these algorithms and guidelines for choosing the best one, depending on the data at hand.