Approximate String Joins In A Database (Almost) For Free

Approximate String Joins in a Database (Almost) for FreeLuis GravanoColumbia UniversityPanagiotis G. IpeirotisColumbia UniversityH. V. JagadishUniversity of dujag@eecs.umich.eduNick KoudasAT&T Labs–ResearchS. MuthukrishnanAT&T Labs–ResearchDivesh SrivastavaAT&T ch.att.comdivesh@research.att.comAbstractString data is ubiquitous, and its management hastaken on particular importance in the past fewyears. Approximate queries are very important onstring data especially for more complex queriesinvolving joins. This is due, for example, to theprevalence of typographical errors in data, andmultiple conventions for recording attributes suchas name and address. Commercial databases donot support approximate string joins directly, andit 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 ofcommercial 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 bothpositions of individual matches and the total number of such matches. Our approach applies to bothapproximate full string matching and approximatesubstring matching, with a variety of possible editdistance functions. The approximate string matchpredicate, with a suitable edit distance threshold,can be mapped into a vanilla relational expressionand optimized by conventional relational optimizers. We demonstrate experimentally the benefitsof 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 editdistance and -gram length, we also describe detailed experiments based on a prototype implementation.1IntroductionString data is ubiquitous. To name only a few commonplace applications, consider product catalogs (for books,music, software, etc.), electronic white and yellow pagedirectories, specialized information sources such as patentdatabases, and customer relationship management data.As a consequence, management of string data indatabases has taken on particular importance in the pastfew years. Applications that collect and correlate data fromindependent data sources for warehousing, mining, and statistical analysis rely on efficient string matching to performtheir tasks. Here, correlation between the data is typicallybased on joins between descriptive string attributes in thevarious sources. However, the quality of the string information residing in various databases can be degraded dueto a variety of reasons, including human typing errors andflexibility in specifying string attributes. Hence the resultsof the joins based on exact matching of string attributes areoften of lower quality than expected. The following example illustrates these problems:Example 1.1 [String Joins] Consider a corporation maintaining various customer databases. Requests for correlating data sources are very common in this context. A specific customer might be present in more than one databasebecause the customer subscribes to multiple services thatthe corporation offers, and each service may have developed its database independently. In one database, acustomer’s name may be recorded as John A. Smith,while in another database the name may be recorded asSmith, John. In a different database, due to a typingerror, this name may be recorded as Jonh Smith. A request to correlate these databases and create a unified viewof customers will fail to produce the desired output if exactstring matching is used in the join. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercialadvantage, the VLDB copyright notice and the title of the publication andits date appear, and notice is given that copying is by permission of theVery Large Data Base Endowment. To copy otherwise, or to republish,requires a fee and/or special permission from the Endowment.Proceedings of the 27th VLDB Conference,Roma, Italy, 2001Unfortunately, commercial databases do not directlysupport approximate string processing functionality. Specialized tools, such as those available from Trillium Software1 , are useful for matching specific types of valuessuch as addresses, but these tools are not integrated with1 www.trillium.com

databases. To use such tools for information stored indatabases, one would either have to process data outsidethe database, or be able to use them as user-defined functions (UDFs) in an object-relational database. The formerapproach is undesirable in general. The latter approach isquite inefficient, especially for joins, because relational engines evaluate joins involving UDFs whose arguments include attributes belonging to multiple tables by essentiallycomputing the cross-products and applying the UDFs in apost-processing fashion.To address such difficulties, we need techniques for efficiently identifying all pairs of approximately matchingstrings in a database of strings. Whenever one deals withmatching in an approximate fashion, one has to specify theapproximation metric. Several proposals exist for stringsto capture the notion of “approximate equality.” Amongthose, the notion of edit distance between two strings isvery popular. According to this notion, deletion, insertion,and substitution of a character are considered as unit costoperations and the edit distance between two strings is defined as the lowest cost sequence of operations that cantransform one string to the other.Although there is a fair amount of work on the problemof approximately matching strings (see Section 6), we arenot aware of work related to approximately matching allstring pairs based on edit distance (or variants of it), as isneeded in approximate string joins. Moreover, we are notaware of any work related to this problem in the context ofa relational DBMS.In this paper, we present a technique for computing approximate string joins efficiently. At the core, our technique relies on matching short substrings of length of thedatabase strings (also known as -grams). We show howa relational schema can be augmented to directly represent-grams of database strings in auxiliary tables within thedatabase in a way that will enable use of traditional relational techniques and access methods for the calculation ofapproximate string joins. By taking into account the total number of such matches and the positions of individual -gram matches we guarantee no false dismissals underthe edit distance metric, as well as variations of it, and theidentification of a set of candidate pairs with a few falsepositives that can be later verified for correctness.Instead of trying to invent completely new join algorithms from scratch (which would be unlikely to be incorporated into existing commercial DBMSs), we opted fora design that would require minimal changes to existingdatabase systems. We show how the approximate stringmatch predicate, with a suitable edit distance threshold, canbe mapped into a vanilla SQL expression and optimizedby conventional optimizers. The immediate practical benefit of our technique is that approximate string processingcan be widely and effectively deployed in commercial relational databases without extensive changes to the underlying database system. Furthermore, by not requiring anychanges in the DBMS internals, we can re-use existing facilities, like the query optimizer, join ordering algorithmsand selectivity estimation.The rest of the paper is organized as follows: In Section 2 we give the notation and the definitions that we willuse. Then, in Section 3 we introduce formally the prob-lem of approximate string joins and we present our proposal. In Section 4 we present the results of an experimental study comparing the proposed approach to other applicable methods, demonstrating performance benefits andpresenting performance trends for several parameters of interest. Finally, in Section 5 we describe how we can adaptour techniques to address further problems of interest. Inparticular we show how to incorporate an alternate stringdistance function, namely the block edit distance (whereedit operations on contiguous substrings are inexpensive),and we address the problem of approximate substring joins.2Preliminaries2.1 Notation We use , possibly with subscripts, to denote tables, ,possibly with subscripts, to denote attributes, and , possibly with subscripts, to denote records in tables. We usethe notationto refer to attributeof table , andto refer to the value in attributeof record.Let be a finite alphabet of size. We use lowercase Greek symbols, such as , possibly with subscripts, todenote strings in . Letbe a string of length .We use,, to denote a substring ofof lengthstarting at position . # ! " ! &%' Definition 2.1 [Edit Distance] The edit distance betweentwo strings is the minimum number of edit operations (i.e.,insertions, deletions, and substitutions) of single charactersneeded to transform the first string into the second. 2.2(-grams: A Foundation for Approximate StringProcessingBelow, we briefly review the notion of positional -gramsfrom the literature, and we give the intuition behind theiruse for approximate string matching [16, 15, 13].Given a string , its positional -grams are obtained by“sliding” a window of length over the characters of .Since -grams at the beginning and the end of the stringcan have fewer than characters from , we introduce newcharacters “#” and “ ” not in , and conceptually extendthe string by prefixing it withoccurrences of “#”and suffixing it withoccurrences of “ ”. Thus, each-gram contains exactly characters, though some of thesemay not be from the alphabet . ## *) % # ,. / 0% # %Definition 2.2 [Positional -gram] A positional -gram, whereof a string is a pairis the -gram of that starts at position , counting onthe extended string. The setof all positional -grams ofpairs constructeda string is the set of all thefrom all -grams of .# The intuition behind the use of -grams as a foundationfor approximate string processing is that when two stringsandare within a small edit distance of each other,they share a large number of -grams in common [15, 13].The following example illustrates this observation. 21 43