Efficient sequential and parallel algorithms for record linkage.
Background and 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...
| Publicado en: | Journal of the American Medical Informatics Association Vol. 21; no. 2; pp. 252 - 263 |
|---|---|
| Autores principales: | , , , |
| Formato: | research Journal Article |
| Publicado: |
Oxford University Press / USA
Mar2014
|
| Acceso en línea: | Ver este registro en EBSCOhost |
| fields | @attributes: recordID: 1 pdfLink: plink: https://search.ebscohost.com/login.aspx?direct=true&db=ccm&AN=104021491&site=ehost-live header: @attributes: shortDbName: ccm uiTerm: 104021491 longDbName: CINAHL Complete uiTag: AN controlInfo: bkinfo: dissinfo: jinfo: jid: 10675027 FZ9 jtl: Journal of the American Medical Informatics Association issn: 10675027 maglogo: N pubinfo: dt: Mar2014 vid: 21 iid: 2 pid: 622 pub: Oxford University Press / USA artinfo: ui: 104021491 NLM24154837 2012470480 10.1136/amiajnl-2013-002034 NLM24154837 PMC3932463 104021491 ppf: 252 ppct: 11 formats: tig: atl: Efficient sequential and parallel algorithms for record linkage. aug: au: Mamun, Abdullah-Al Mi, Tian Aseltine, Robert Rajasekaran, Sanguthevar affil: Department of Computer Science and Engineering, University of Connecticut, Storrs, Connecticut, USA. sug: subj: Algorithms Medical Record Linkage Methods Patient Record Systems Cluster Analysis ab: Background and 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. pubtype: Academic Journal doctype: research Journal Article ougenre: Article language: English refInfo: holdings: @attributes: islocal: N |
|---|