Text joins for data cleansing and integration in a relational database management system

• US 20050027717A1
• Filed: 04/21/2004
• Published: 02/03/2005
• Est. Priority Date: 04/21/2003
• Status: Abandoned Application

• Current Assignee: AT&T Corporation (AT&T, Inc.), AT&T, Inc., Trustees Of Columbia University In The City Of New York (Columbia University)
• Original Assignee: AT&T Corporation (AT&T, Inc.), Trustees Of Columbia University In The City Of New York (Columbia University)
• Inventors: Srivastava, Divesh, Koudas, Nikolaos, Gravano, Luis, Ipeirotis, Panagiotis G.
• Application Number:
  US10/828,819
• Publication Number:
  US 20050027717A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 16/3347 using vector based model

Abstract

An organization'"'"'s data records are often noisy: because of transcription errors, incomplete information, and lack of standard formats for textual data. A fundamental task during data cleansing and integration is matching strings—perhaps across multiple relations—that refer to the same entity (e.g., organization name or address). Furthermore, it is desirable to perform this matching within an RDBMS, which is where the data is likely to reside. In this paper, We adapt the widely used and established cosine similarity metric from the information retrieval field to the relational database context in order to identify potential string matches across relations. We then use this similarity metric to characterize this key aspect of data cleansing and integration as a join between relations on textual attributes, where the similarity of matches exceeds a specified threshold. Computing an exact answer to the text join can be expensive. For query processing efficiency, we propose an approximate, sampling-based approach to the join problem that can be easily and efficiently executed in a standard, unmodified RDBMS. Therefore the present invention includes a system for string matching across multiple relations in a relational database management system comprising generating a set of strings from a set of characters, decomposing each string into a subset of tokens, establishing at least two relations within the strings, establishing a similarity threshold for the relations, sampling the at least two relations, correlating the relations for the similarity threshold and returning all of the tokens which meet the criteria of the similarity threshold.

Claims

1. ) A system for string matching across multiple relations in a relational database management system comprising:

generating a set of strings from a set of characters,

decomposing each string into a subset of tokens,

establishing at least two relations within said strings,

establishing a similarity threshold for said relations,

sampling said at least two relations,

correlating said relations for said similarity threshold and

returning all of said tokens which meet the criteria of said similarity threshold.