Record linkage as dna sequence alignment problem

Since modern database applications increasingly need to deal with dirty data due to a variety of reasons (e.g., data entry errors, heterogeneous formats, and ambiguous terms), (record) linkage problem to determine if two entities represented as relational records are approximately the same or not. In this paper, we propose a novel idea of using the popular gene sequence alignment algorithm in Biology BLAST. Our proposal, termed as the BLASTed linkage, is based on the observations that: (1) both problems are variants of approximate pattern matching, (2) BLAST provides the statistical guarantee of search results in a scalable manner a greatly lacking feature in many linkage solutions, and (3) by transforming the record linkage problem into the gene sequence alignment problem, one can leverage on a wealth of advanced algorithms, implementations, and tools that have been actively developed for BLAST during the last decade. In translating English alphabets to DNA sequences of A. C, G. and T. we study four variations: (1) default each alphabet is mapped to nucleotides under 1, 2, and 1-bit coding schemes, (2) weighted tokens are elongated or shortened proportional to their importance, making important tokens longer in the resultant DNA sequences, (3) hybrid each token's lexical meaning as well as its importance are considered at the same time during translation, and (4) multi-bit tokens are selected for any of 1. 2, and 1-bit coding schemes based on the cumulative distribution functions of their schemes are experimentally validated using both real and synthetic data sets.