title: Efficient sequential and parallel algorithms for record linkage.
abstract: OBJECTIVE
  Integrating data from multiple sources is a crucial and challenging problem. Even though there exist numerous algorithms for record linkage or deduplication, they suffer from either large time needs or restrictions on the number of datasets that they can integrate. In this paper we report efficient sequential and parallel algorithms for record linkage which handle any number of datasets and outperform previous algorithms.
  
  
  METHODS
  Our algorithms employ hierarchical clustering algorithms as the basis. A key idea that we use is radix sorting on certain attributes to eliminate identical records before any further processing. Another novel idea is to form a graph that links similar records and find the connected components.
  
  
  RESULTS
  Our sequential and parallel algorithms have been tested on a real dataset of 1,083,878 records and synthetic datasets ranging in size from 50,000 to 9,000,000 records. Our sequential algorithm runs at least two times faster, for any dataset, than the previous best-known algorithm, the two-phase algorithm using faster computation of the edit distance (TPA (FCED)). The speedups obtained by our parallel algorithm are almost linear. For example, we get a speedup of 7.5 with 8 cores (residing in a single node), 14.1 with 16 cores (residing in two nodes), and 26.4 with 32 cores (residing in four nodes).
  
  
  CONCLUSIONS
  We have compared the performance of our sequential algorithm with TPA (FCED) and found that our algorithm outperforms the previous one. The accuracy is the same as that of this previous best-known algorithm.
authors.affiliation: Department of Computer Science and Engineering, University of Connecticut, Storrs, Connecticut, USA.
authors.forename: Abdullah-Al
authors.initials: AA
authors.lastname: Mamun
authors.forename: Tian
authors.initials: T
authors.lastname: Mi
authors.forename: Robert
authors.initials: R
authors.lastname: Aseltine
authors.forename: Sanguthevar
authors.initials: S
authors.lastname: Rajasekaran
mesh_terms: D000465:Algorithms; D016000:Cluster Analysis; D008498:Medical Record Linkage / Q000379:methods*; D016347:Medical Records Systems, Computerized
keywords: Algorithms; Data Integration; Healthcare Records; Parallel Algorithms; Speedups