Context-Aware Approximate String Matching for Large-Scale Real-Time Entity Resolution

Peter Christen; Ross W. Gayler

doi:10.1109/ICDMW.2015.152

Context-Aware Approximate String Matching for Large-Scale Real-Time Entity Resolution

Peter Christen, Ross W. Gayler

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

1 Citation (Scopus)

Abstract

Techniques for approximate string matching have been widely studied over several decades. They are required in many applications, including entity resolution, spell checking, similarity joins, and biological sequence comparison. Most existing techniques for approximate string matching used in entity resolution only consider the two strings that are compared. They neglect contextual information such as the frequency of how often strings occur in a database, the likelihood of the character edits between strings, or how many other similar strings there are in a database. In this paper we investigate if incorporating such contextual information into edit distance based approximate string matching can improve matching quality for real-time entity resolution. In this application, query records have to be matched in sub-second time to records in a large database that refer to the same entity. We evaluate our approach on two large real data sets and compare it to several baseline approaches. Our results show that considering edit frequency and the neighborhood size of a string can improve matching results, while taking string frequencies into account can actually make results worse.

Original language	English
Title of host publication	Proceedings - 15th IEEE International Conference on Data Mining Workshop, ICDMW 2015
Editors	Xindong Wu, Alexander Tuzhilin, Hui Xiong, Jennifer G. Dy, Charu Aggarwal, Zhi-Hua Zhou, Peng Cui
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	211-217
Number of pages	7
ISBN (Electronic)	9781467384926
DOIs	https://doi.org/10.1109/ICDMW.2015.152
Publication status	Published - 29 Jan 2016
Event	15th IEEE International Conference on Data Mining Workshop, ICDMW 2015 - Atlantic City, United States Duration: 14 Nov 2015 → 17 Nov 2015

Publication series

Name	Proceedings - 15th IEEE International Conference on Data Mining Workshop, ICDMW 2015

Conference

Conference	15th IEEE International Conference on Data Mining Workshop, ICDMW 2015
Country/Territory	United States
City	Atlantic City
Period	14/11/15 → 17/11/15

Access to Document

10.1109/ICDMW.2015.152

Cite this

Christen, P., & Gayler, R. W. (2016). Context-Aware Approximate String Matching for Large-Scale Real-Time Entity Resolution. In X. Wu, A. Tuzhilin, H. Xiong, J. G. Dy, C. Aggarwal, Z.-H. Zhou, & P. Cui (Eds.), Proceedings - 15th IEEE International Conference on Data Mining Workshop, ICDMW 2015 (pp. 211-217). Article 7395673 (Proceedings - 15th IEEE International Conference on Data Mining Workshop, ICDMW 2015). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICDMW.2015.152

Christen, Peter ; Gayler, Ross W. / Context-Aware Approximate String Matching for Large-Scale Real-Time Entity Resolution. Proceedings - 15th IEEE International Conference on Data Mining Workshop, ICDMW 2015. editor / Xindong Wu ; Alexander Tuzhilin ; Hui Xiong ; Jennifer G. Dy ; Charu Aggarwal ; Zhi-Hua Zhou ; Peng Cui. Institute of Electrical and Electronics Engineers Inc., 2016. pp. 211-217 (Proceedings - 15th IEEE International Conference on Data Mining Workshop, ICDMW 2015).

@inproceedings{d704e7ed71294b39af07133171141aff,

title = "Context-Aware Approximate String Matching for Large-Scale Real-Time Entity Resolution",

abstract = "Techniques for approximate string matching have been widely studied over several decades. They are required in many applications, including entity resolution, spell checking, similarity joins, and biological sequence comparison. Most existing techniques for approximate string matching used in entity resolution only consider the two strings that are compared. They neglect contextual information such as the frequency of how often strings occur in a database, the likelihood of the character edits between strings, or how many other similar strings there are in a database. In this paper we investigate if incorporating such contextual information into edit distance based approximate string matching can improve matching quality for real-time entity resolution. In this application, query records have to be matched in sub-second time to records in a large database that refer to the same entity. We evaluate our approach on two large real data sets and compare it to several baseline approaches. Our results show that considering edit frequency and the neighborhood size of a string can improve matching results, while taking string frequencies into account can actually make results worse.",

keywords = "Edit distance, data matching, real-time matching, similarity calculation, string databases",

author = "Peter Christen and Gayler, {Ross W.}",

note = "Publisher Copyright: {\textcopyright} 2015 IEEE.; 15th IEEE International Conference on Data Mining Workshop, ICDMW 2015 ; Conference date: 14-11-2015 Through 17-11-2015",

year = "2016",

month = jan,

day = "29",

doi = "10.1109/ICDMW.2015.152",

language = "English",

series = "Proceedings - 15th IEEE International Conference on Data Mining Workshop, ICDMW 2015",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "211--217",

editor = "Xindong Wu and Alexander Tuzhilin and Hui Xiong and Dy, {Jennifer G.} and Charu Aggarwal and Zhi-Hua Zhou and Peng Cui",

booktitle = "Proceedings - 15th IEEE International Conference on Data Mining Workshop, ICDMW 2015",

address = "United States",

}

Christen, P & Gayler, RW 2016, Context-Aware Approximate String Matching for Large-Scale Real-Time Entity Resolution. in X Wu, A Tuzhilin, H Xiong, JG Dy, C Aggarwal, Z-H Zhou & P Cui (eds), Proceedings - 15th IEEE International Conference on Data Mining Workshop, ICDMW 2015., 7395673, Proceedings - 15th IEEE International Conference on Data Mining Workshop, ICDMW 2015, Institute of Electrical and Electronics Engineers Inc., pp. 211-217, 15th IEEE International Conference on Data Mining Workshop, ICDMW 2015, Atlantic City, United States, 14/11/15. https://doi.org/10.1109/ICDMW.2015.152

Context-Aware Approximate String Matching for Large-Scale Real-Time Entity Resolution. / Christen, Peter; Gayler, Ross W.
Proceedings - 15th IEEE International Conference on Data Mining Workshop, ICDMW 2015. ed. / Xindong Wu; Alexander Tuzhilin; Hui Xiong; Jennifer G. Dy; Charu Aggarwal; Zhi-Hua Zhou; Peng Cui. Institute of Electrical and Electronics Engineers Inc., 2016. p. 211-217 7395673 (Proceedings - 15th IEEE International Conference on Data Mining Workshop, ICDMW 2015).

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

TY - GEN

T1 - Context-Aware Approximate String Matching for Large-Scale Real-Time Entity Resolution

AU - Christen, Peter

AU - Gayler, Ross W.

PY - 2016/1/29

Y1 - 2016/1/29

N2 - Techniques for approximate string matching have been widely studied over several decades. They are required in many applications, including entity resolution, spell checking, similarity joins, and biological sequence comparison. Most existing techniques for approximate string matching used in entity resolution only consider the two strings that are compared. They neglect contextual information such as the frequency of how often strings occur in a database, the likelihood of the character edits between strings, or how many other similar strings there are in a database. In this paper we investigate if incorporating such contextual information into edit distance based approximate string matching can improve matching quality for real-time entity resolution. In this application, query records have to be matched in sub-second time to records in a large database that refer to the same entity. We evaluate our approach on two large real data sets and compare it to several baseline approaches. Our results show that considering edit frequency and the neighborhood size of a string can improve matching results, while taking string frequencies into account can actually make results worse.

AB - Techniques for approximate string matching have been widely studied over several decades. They are required in many applications, including entity resolution, spell checking, similarity joins, and biological sequence comparison. Most existing techniques for approximate string matching used in entity resolution only consider the two strings that are compared. They neglect contextual information such as the frequency of how often strings occur in a database, the likelihood of the character edits between strings, or how many other similar strings there are in a database. In this paper we investigate if incorporating such contextual information into edit distance based approximate string matching can improve matching quality for real-time entity resolution. In this application, query records have to be matched in sub-second time to records in a large database that refer to the same entity. We evaluate our approach on two large real data sets and compare it to several baseline approaches. Our results show that considering edit frequency and the neighborhood size of a string can improve matching results, while taking string frequencies into account can actually make results worse.

KW - Edit distance

KW - data matching

KW - real-time matching

KW - similarity calculation

KW - string databases

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

U2 - 10.1109/ICDMW.2015.152

DO - 10.1109/ICDMW.2015.152

M3 - Conference contribution

T3 - Proceedings - 15th IEEE International Conference on Data Mining Workshop, ICDMW 2015

SP - 211

EP - 217

BT - Proceedings - 15th IEEE International Conference on Data Mining Workshop, ICDMW 2015

A2 - Wu, Xindong

A2 - Tuzhilin, Alexander

A2 - Xiong, Hui

A2 - Dy, Jennifer G.

A2 - Aggarwal, Charu

A2 - Zhou, Zhi-Hua

A2 - Cui, Peng

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 15th IEEE International Conference on Data Mining Workshop, ICDMW 2015

Y2 - 14 November 2015 through 17 November 2015

ER -

Christen P, Gayler RW. Context-Aware Approximate String Matching for Large-Scale Real-Time Entity Resolution. In Wu X, Tuzhilin A, Xiong H, Dy JG, Aggarwal C, Zhou ZH, Cui P, editors, Proceedings - 15th IEEE International Conference on Data Mining Workshop, ICDMW 2015. Institute of Electrical and Electronics Engineers Inc. 2016. p. 211-217. 7395673. (Proceedings - 15th IEEE International Conference on Data Mining Workshop, ICDMW 2015). doi: 10.1109/ICDMW.2015.152

Context-Aware Approximate String Matching for Large-Scale Real-Time Entity Resolution

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this