Approximate Record Matching Using Hash Grams

Accurately identifying duplicate records between multiple data sources is a persistent problem that continues to plague organizations and researchers alike. Small inconsistencies between records can prevent detection between two otherwise identical records. In this paper, we present a new probabilistic h-gram (hash gram) record matching technique by extending traditional n-grams and utilizing scale based hashing for equality testing. h-gram matching highly reduces the number of comparisons to be performed for duplicate record detection applicable to a variety of data types and data sizes by transforming data into its equivalent numerical realities. One of the key features of h-gram matching is that it is highly extensible providing more intuitive and flexible results. With the sampling technique in place, our method can be applied on variable size databases to perform data linkage and probabilistic results can be quickly obtained. We have extensively evaluated h-gram matching on large samples of real-world data and the results show higher level of accuracy as well as reduction in required time when compared with existing techniques.