Understanding Cloud Data Using Approximate String Matching and Edit Distance
Authors:
- 1 November 2012
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1234-1243
Abstract
For health and human services, fraud detection and other security services, identity resolution is a core requirement for understanding big data in the cloud. Due to the lack of a globally unique identifier and captured typographic differences for the same identity, identity resolution has high spatial and temporal complexities. We propose a filter and verify method to substantially increase the speed of approximate string matching using edit distance. This method has been found to be almost 80 times faster (130 times when combined with other optimizations) than Damerau-Levenshtein edit distance and preserves all approximate matches. Our method creates compressed signatures for data fields and uses Boolean operations and an enhanced bit counter to quickly compare the distance between the fields. This method is intended to be applied to data records whose fields contain relatively short-length strings, such as those found in most demographic data. Without loss of accuracy, the proposed Fast Bitwise Filter will provide substantial performance gain to approximate string comparison in database, record linkage and deduplication data processing systems.Keywords
This publication has 20 references indexed in Scilit:
- Trie-joinProceedings of the VLDB Endowment, 2010
- Ed-JoinProceedings of the VLDB Endowment, 2008
- Record linkage software in the public domain: a comparison of Link Plus, The Link King, and a `basic' deterministic algorithmHealth Informatics Journal, 2008
- Adaptive Filtering for Efficient Record Linkage2004
- Learning to match and cluster large high-dimensional data sets for data integration2002
- Algorithms on Strings, Trees and Sequences1997
- Dynamic programming algorithm optimization for spoken word recognitionIEEE Transactions on Acoustics, Speech, and Signal Processing, 1978
- A technique for computer detection and correction of spelling errorsCommunications of the ACM, 1964
- A technique for counting ones in a binary computerCommunications of the ACM, 1960
- Error Detecting and Error Correcting CodesBell System Technical Journal, 1950