Approximate String Joins in a Database (Almost) for Free

TLDR

String data is ubiquitous and managing it has become increasingly important, yet commercial databases lack efficient support for approximate string joins, a need amplified by typographical errors and varied attribute conventions. The paper proposes a technique to enable approximate string joins on commercial databases by leveraging existing database features. The method matches short k‑grams, accounting for match positions and counts, and translates the edit‑distance predicate into a standard relational expression that can be optimized by existing query planners. Experiments show that the technique outperforms direct UDFs in both I/O and CPU efficiency on real data.

Abstract

String data is ubiquitous, and its management has taken on particular importance in the past few years. Approximate queries are very important on string data especially for more complex queries involving joins. This is due, for example, to the prevalence of typographical errors in data, and multiple conventions for recording attributes such as name and address. Commercial databases do not support approximate string joins directly, and it is a challenge to implement this functionality efficiently with user-defined functions (UDFs). In this paper, we develop a technique for building approximate string join capabilities on top of commercial databases by exploiting facilities already available in them. At the core, our technique relies on matching short substrings of length , called -grams, and taking into account both positions of individual matches and the total number of such matches. Our approach applies to both approximate full string matching and approximate substring matching, with a variety of possible edit distance functions. The approximate string match predicate, with a suitable edit distance threshold, can be mapped into a vanilla relational expression and optimized by conventional relational optimizers. We demonstrate experimentally the benefits of our technique over the direct use of UDFs, using commercial database systems and real data. To study the I/O and CPU behavior of approximate string join algorithms with variations in edit distance and -gram length, we also describe detailed experiments based on a prototype implementation.