Entity resolution with iterative blocking

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Entity resolution with iterative blocking

Full text

Pdf (487 KB)

Source

International Conference on Management of Data archive
Proceedings of the 35th SIGMOD international conference on Management of data table of contents

Providence, Rhode Island, USA

SESSION: Research session 6: entity resolution table of contents

Pages 219-232

Year of Publication: 2009

ISBN:978-1-60558-551-2

Authors

Steven Euijong Whang	Stanford University, Stanford, CA, USA
David Menestrina	Stanford University, Stanford, CA, USA
Georgia Koutrika	Stanford University, Stanford, CA, USA
Martin Theobald	Stanford University, Stanford, CA, USA
Hector Garcia-Molina	Stanford University, Stanford, CA, USA

Sponsors

ACM: Association for Computing Machinery
SIGMOD: ACM Special Interest Group on Management of Data

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 50, Downloads (12 Months): 173, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1559845.1559870 What is a DOI?

ABSTRACT

Entity Resolution (ER) is the problem of identifying which records in a database refer to the same real-world entity. An exhaustive ER process involves computing the similarities between pairs of records, which can be very expensive for large datasets. Various blocking techniques can be used to enhance the performance of ER by dividing the records into blocks in multiple ways and only comparing records within the same block. However, most blocking techniques process blocks separately and do not exploit the results of other blocks. In this paper, we propose an iterative blocking framework where the ER results of blocks are reflected to subsequently processed blocks. Blocks are now iteratively processed until no block contains any more matching records. Compared to simple blocking, iterative blocking may achieve higher accuracy because reflecting the ER results of blocks to other blocks may generate additional record matches. Iterative blocking may also be more efficient because processing a block now saves the processing time for other blocks. We implement a scalable iterative blocking system and demonstrate that iterative blocking can be more accurate and efficient than blocking for large datasets.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Nikhil Bansal , Avrim Blum , Shuchi Chawla, Correlation Clustering, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.238, November 16-19, 2002
	2	R. Baxter, P. Christen, and T. Churches. A comparison of fast blocking methods for record linkage. In ACM SIGKDD Workshop on Data Cleaning, Record Linkage, and Object Identification, 2003.
	3	Omar Benjelloun , Hector Garcia-Molina , David Menestrina , Qi Su , Steven Euijong Whang , Jennifer Widom, Swoosh: a generic approach to entity resolution, The VLDB Journal — The International Journal on Very Large Data Bases, v.18 n.1, p.255-276, January 2009 [doi>10.1007/s00778-008-0098-x]
	4	Indrajit Bhattacharya , Lise Getoor, Iterative record linkage for cleaning and integration, Proceedings of the 9th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery, June 13, 2004, Paris, France [doi>10.1145/1008694.1008697]
	5	Mikhail Bilenko , Beena Kamath , Raymond J. Mooney, Adaptive Blocking: Learning to Scale Up Record Linkage, Proceedings of the Sixth International Conference on Data Mining, p.87-96, December 18-22, 2006 [doi>10.1109/ICDM.2006.13]
	6	Surajit Chaudhuri , Venkatesh Ganti , Rajeev Motwani, Robust Identification of Fuzzy Duplicates, Proceedings of the 21st International Conference on Data Engineering, p.865-876, April 05-08, 2005 [doi>10.1109/ICDE.2005.125]
	7	Xin Dong , Alon Halevy , Jayant Madhavan, Reference reconciliation in complex information spaces, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066168]
	8	Ahmed K. Elmagarmid , Panagiotis G. Ipeirotis , Vassilios S. Verykios, Duplicate Record Detection: A Survey, IEEE Transactions on Knowledge and Data Engineering, v.19 n.1, p.1-16, January 2007 [doi>10.1109/TKDE.2007.9]
	9	L. Gu, R. Baxter, D. Vickers, and C. Rainsford. Record linkage: Current practice and future directions. Technical Report 03/83, CSIRO Mathematical and Information Sciences, 2003.
	10	L. Gu and R. A. Baxter. Adaptive filtering for efficient record linkage. In SDM, 2004.
	11	Mauricio A. Hernández , Salvatore J. Stolfo, Real-world Data is Dirty: Data Cleansing and The Merge/Purge Problem, Data Mining and Knowledge Discovery, v.2 n.1, p.9-37, January 1998 [doi>10.1023/A:1009761603038]
	12	Mauricio A. Hernández , Salvatore J. Stolfo, The merge/purge problem for large databases, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.127-138, May 22-25, 1995, San Jose, California, United States
	13	Thomas N. Herzog , Fritz J. Scheuren , William E. Winkler, Data Quality and Record Linkage Techniques, Springer Publishing Company, Incorporated, 2007
	14	Piotr Indyk, A small approximately min-wise independent family of hash functions, Journal of Algorithms, v.38 n.1, p.84-90, Jan. 2001 [doi>10.1006/jagm.2000.1131]
	15	Andrew McCallum , Kamal Nigam , Lyle H. Ungar, Efficient clustering of high-dimensional data sets with application to reference matching, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.169-178, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347123]
	16	Matthew Michelson , Craig A. Knoblock, Learning blocking schemes for record linkage, Proceedings of the 21st national conference on Artificial intelligence, p.440-445, July 16-20, 2006, Boston, Massachusetts
	17	A. E. Monge and C. P. Elkan. An efficient domain independent algorithm for detecting approximately duplicate database records. In SIGMOD DMKD, 1997.
	18	H. B. Newcombe, Handbook of record linkage: methods for health and statistical studies, administration, and business, Oxford University Press, Inc., New York, NY, 1988
	19	Howard B. Newcombe , James M. Kennedy, Record linkage: making maximum use of the discriminating power of identifying information, Communications of the ACM, v.5 n.11, p.563-566, Nov. 1962 [doi>10.1145/368996.369026]
	20	Sunita Sarawagi , Anuradha Bhamidipaty, Interactive deduplication using active learning, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775087]
	21	Sheila Tejada , Craig A. Knoblock , Steven Minton, Learning object identification rules for information integration, Information Systems, v.26 n.8, p.607-633, December 2001 [doi>10.1016/S0306-4379(01)00042-4]
	22	Steven Euijong Whang , David Menestrina , Georgia Koutrika , Martin Theobald , Hector Garcia-Molina, Entity resolution with iterative blocking, Proceedings of the 35th SIGMOD international conference on Management of data, June 29-July 02, 2009, Providence, Rhode Island, USA [doi>10.1145/1559845.1559870]
	23	W. Winkler. Overview of record linkage and current research directions. Technical report, Statistical Research Division, U.S. Bureau of the Census, Washington, DC, 2006.
	24	W. E. Winkler. Approximate string comparator search strategies for very large administrative lists. Technical report, US Bureau of the Census, 2005.
	25	W. Yancey. Bigmatch: A program for extracting probable matches from a large file for record linkage. Technical report, US Bureau of the Census, 2002.