  Record linkage has been extensively used in various data mining applications
involving sharing data. While the amount of available data is growing, the
concern of disclosing sensitive information poses the problem of utility vs
privacy. In this paper, we study the problem of private record linkage via
secure data transformations. In contrast to the existing techniques in this
area, we propose a novel approach that provides strong privacy guarantees under
the formal framework of differential privacy. We develop an embedding strategy
based on frequent variable length grams mined in a private way from the
original data. We also introduce personalized threshold for matching individual
records in the embedded space which achieves better linkage accuracy than the
existing global threshold approach. Compared with the state-of-the-art secure
matching schema, our approach provides formal, provable privacy guarantees and
achieves better scalability while providing comparable utility.
