A scalable and efficient subgroup blocking scheme for multidatabase record linkage

Thilina Ranbaduge; Dinusha Vatsalan; Peter Christen

doi:10.1007/978-3-319-93040-4_2

A scalable and efficient subgroup blocking scheme for multidatabase record linkage

Thilina Ranbaduge^*, Dinusha Vatsalan, Peter Christen

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

5 Citations (Scopus)

Abstract

Record linkage is a commonly used task in data integration to facilitate the identification of matching records that refer to the same entity from different databases. The scalability of multidatabase record linkage (MDRL) is significantly challenged with the increase of both the sizes and the number of databases that are to be linked. Identifying matching records across subgroups of databases is an important aspect in MDRL that has not been addressed so far. We propose a scalable subgroup blocking approach for MDRL that uses an efficient search over a graph structure to identify similar blocks of records that need to be compared across subgroups of multiple databases. We provide an analysis of our technique in terms of complexity and blocking quality. We conduct an empirical study on large real-world datasets that shows our approach is scalable with the size of subgroups and the number of databases, and outperforms an existing state-of-the-art blocking technique for MDRL.

Original language	English
Title of host publication	Advances in Knowledge Discovery and Data Mining - 22nd Pacific-Asia Conference, PAKDD 2018, Proceedings
Editors	Geoffrey I. Webb, Dinh Phung, Mohadeseh Ganji, Lida Rashidi, Vincent S. Tseng, Bao Ho
Publisher	Springer Verlag
Pages	15-27
Number of pages	13
ISBN (Print)	9783319930398
DOIs	https://doi.org/10.1007/978-3-319-93040-4_2
Publication status	Published - 2018
Event	22nd Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, PAKDD 2018 - Melbourne, Australia Duration: 3 Jun 2018 → 6 Jun 2018

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10939 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	22nd Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, PAKDD 2018
Country/Territory	Australia
City	Melbourne
Period	3/06/18 → 6/06/18

Access to Document

10.1007/978-3-319-93040-4_2

Cite this

Ranbaduge, T., Vatsalan, D., & Christen, P. (2018). A scalable and efficient subgroup blocking scheme for multidatabase record linkage. In G. I. Webb, D. Phung, M. Ganji, L. Rashidi, V. S. Tseng, & B. Ho (Eds.), Advances in Knowledge Discovery and Data Mining - 22nd Pacific-Asia Conference, PAKDD 2018, Proceedings (pp. 15-27). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10939 LNAI). Springer Verlag. https://doi.org/10.1007/978-3-319-93040-4_2

Ranbaduge, Thilina ; Vatsalan, Dinusha ; Christen, Peter. / A scalable and efficient subgroup blocking scheme for multidatabase record linkage. Advances in Knowledge Discovery and Data Mining - 22nd Pacific-Asia Conference, PAKDD 2018, Proceedings. editor / Geoffrey I. Webb ; Dinh Phung ; Mohadeseh Ganji ; Lida Rashidi ; Vincent S. Tseng ; Bao Ho. Springer Verlag, 2018. pp. 15-27 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{1ec5ac97b1ad495db55b2ad40198a4da,

title = "A scalable and efficient subgroup blocking scheme for multidatabase record linkage",

abstract = "Record linkage is a commonly used task in data integration to facilitate the identification of matching records that refer to the same entity from different databases. The scalability of multidatabase record linkage (MDRL) is significantly challenged with the increase of both the sizes and the number of databases that are to be linked. Identifying matching records across subgroups of databases is an important aspect in MDRL that has not been addressed so far. We propose a scalable subgroup blocking approach for MDRL that uses an efficient search over a graph structure to identify similar blocks of records that need to be compared across subgroups of multiple databases. We provide an analysis of our technique in terms of complexity and blocking quality. We conduct an empirical study on large real-world datasets that shows our approach is scalable with the size of subgroups and the number of databases, and outperforms an existing state-of-the-art blocking technique for MDRL.",

keywords = "Apriori, Cliques, Depth-first, Entity resolution, P-partite graph",

author = "Thilina Ranbaduge and Dinusha Vatsalan and Peter Christen",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG, part of Springer Nature 2018.; 22nd Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, PAKDD 2018 ; Conference date: 03-06-2018 Through 06-06-2018",

year = "2018",

doi = "10.1007/978-3-319-93040-4_2",

language = "English",

isbn = "9783319930398",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "15--27",

editor = "Webb, {Geoffrey I.} and Dinh Phung and Mohadeseh Ganji and Lida Rashidi and Tseng, {Vincent S.} and Bao Ho",

booktitle = "Advances in Knowledge Discovery and Data Mining - 22nd Pacific-Asia Conference, PAKDD 2018, Proceedings",

address = "Germany",

}

Ranbaduge, T, Vatsalan, D & Christen, P 2018, A scalable and efficient subgroup blocking scheme for multidatabase record linkage. in GI Webb, D Phung, M Ganji, L Rashidi, VS Tseng & B Ho (eds), Advances in Knowledge Discovery and Data Mining - 22nd Pacific-Asia Conference, PAKDD 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10939 LNAI, Springer Verlag, pp. 15-27, 22nd Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, PAKDD 2018, Melbourne, Australia, 3/06/18. https://doi.org/10.1007/978-3-319-93040-4_2

A scalable and efficient subgroup blocking scheme for multidatabase record linkage. / Ranbaduge, Thilina; Vatsalan, Dinusha; Christen, Peter.
Advances in Knowledge Discovery and Data Mining - 22nd Pacific-Asia Conference, PAKDD 2018, Proceedings. ed. / Geoffrey I. Webb; Dinh Phung; Mohadeseh Ganji; Lida Rashidi; Vincent S. Tseng; Bao Ho. Springer Verlag, 2018. p. 15-27 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10939 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A scalable and efficient subgroup blocking scheme for multidatabase record linkage

AU - Ranbaduge, Thilina

AU - Vatsalan, Dinusha

AU - Christen, Peter

N1 - Publisher Copyright: © Springer International Publishing AG, part of Springer Nature 2018.

PY - 2018

Y1 - 2018

N2 - Record linkage is a commonly used task in data integration to facilitate the identification of matching records that refer to the same entity from different databases. The scalability of multidatabase record linkage (MDRL) is significantly challenged with the increase of both the sizes and the number of databases that are to be linked. Identifying matching records across subgroups of databases is an important aspect in MDRL that has not been addressed so far. We propose a scalable subgroup blocking approach for MDRL that uses an efficient search over a graph structure to identify similar blocks of records that need to be compared across subgroups of multiple databases. We provide an analysis of our technique in terms of complexity and blocking quality. We conduct an empirical study on large real-world datasets that shows our approach is scalable with the size of subgroups and the number of databases, and outperforms an existing state-of-the-art blocking technique for MDRL.

AB - Record linkage is a commonly used task in data integration to facilitate the identification of matching records that refer to the same entity from different databases. The scalability of multidatabase record linkage (MDRL) is significantly challenged with the increase of both the sizes and the number of databases that are to be linked. Identifying matching records across subgroups of databases is an important aspect in MDRL that has not been addressed so far. We propose a scalable subgroup blocking approach for MDRL that uses an efficient search over a graph structure to identify similar blocks of records that need to be compared across subgroups of multiple databases. We provide an analysis of our technique in terms of complexity and blocking quality. We conduct an empirical study on large real-world datasets that shows our approach is scalable with the size of subgroups and the number of databases, and outperforms an existing state-of-the-art blocking technique for MDRL.

KW - Apriori

KW - Cliques

KW - Depth-first

KW - Entity resolution

KW - P-partite graph

UR - http://www.scopus.com/inward/record.url?scp=85049362020&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-93040-4_2

DO - 10.1007/978-3-319-93040-4_2

M3 - Conference contribution

SN - 9783319930398

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 15

EP - 27

BT - Advances in Knowledge Discovery and Data Mining - 22nd Pacific-Asia Conference, PAKDD 2018, Proceedings

A2 - Webb, Geoffrey I.

A2 - Phung, Dinh

A2 - Ganji, Mohadeseh

A2 - Rashidi, Lida

A2 - Tseng, Vincent S.

A2 - Ho, Bao

PB - Springer Verlag

T2 - 22nd Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, PAKDD 2018

Y2 - 3 June 2018 through 6 June 2018

ER -

Ranbaduge T, Vatsalan D, Christen P. A scalable and efficient subgroup blocking scheme for multidatabase record linkage. In Webb GI, Phung D, Ganji M, Rashidi L, Tseng VS, Ho B, editors, Advances in Knowledge Discovery and Data Mining - 22nd Pacific-Asia Conference, PAKDD 2018, Proceedings. Springer Verlag. 2018. p. 15-27. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-93040-4_2

A scalable and efficient subgroup blocking scheme for multidatabase record linkage

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this