The problem of record linkage is to cluster the records from several data sources such that each cluster has all the records belonging to one and only one entity. Record linkage has applications in a wide variety of domains including public health, law enforcement, fraud detection, biology, and transportation. Given the typically vast sizes of datasets, existing algorithms suffer from very long runtimes. Hence, it is essential to develop novel algorithms tailored to address this issue. Blocking is a popular technique employed to speed up record linkage algorithms. In this paper, we employ a blocking technique that is based on Soundex encoding. Soundex index is a method of coding names based on their pronunciation rather than their spelling. Soundex has been traditionally used only as a distance metric. In this paper, we show how to use Soundex as a blocking technique. To the best of our knowledge, no one else has done it in the past. In fact, we introduce two novel blocking approaches that utilize Soundex encoding: One stage Soundex blocking and Two stage Soundex blocking.Our approaches exhibit superior linkage performance compared to the state-of-the-art record linkage algorithms, as evidenced by higher F-1 scores and reduced linkage times. The proposed blocking approaches prove to be highly effective.

Given multiple data sets, the problem of record linkage is to cluster them such that each cluster has all the information pertaining to a single entity and does not contain any other information. This problem has numerous applications in domains such as healthcare, law enforcement, medicine, census data analysis, etc. The performance of record linkage algorithms is measured with two metrics, namely, run times and accuracy. Record linkage has been studied extensively and numerous algorithms have been proposed. These algorithms take a very long time especially when the input data sets are large. Many applications of interest call for real-time or very nearly real-time performance. Thus there is a crucial need for the creation of novel record linkage algorithms that are very fast while maintaining a very good accuracy.Blocking is a technique that is typically used to speed up record linkage algorithms. In this paper, we introduce a novel algorithm for blocking called SuperBlocking. We have created novel record linkage algorithms that employ SuperBlocking. Experimental comparisons reveal that our algorithms outperform state-of-the-art algorithms for record linkage. We have also developed parallel versions of our record linkage algorithms and they obtain close to linear speedups.

We present a computational geometry method for the problem of triangulation in the plane using measurements of distance-differences. Compared to existing solutions to this well-studied problem, this method is: (a) computationally more efficient and adaptive in that its precision can be controlled as a function of the number of computational operations, making it suitable to low power devices, and (b) robust with respect to measurement and computational errors, and is not susceptible to numerical instabilities typical of existing linear algebraic or quadratic methods. This method employs a binary search on a distance-difference curve in the plane using a second distance- difference as the objective function. We establish the unimodality of the directional derivative of the objective function within each of a small number of suitably decomposed regions of the plane to support the binary search. The computational complexity of this method is O(log21/gamma), where the computed solution is guaranteed to be within a gamma-precision region centered at the actual solution. We present simulation results to compare this method with existing DTOA triangulation methods.