System and methods for searching and matching databases

• US 6,026,398 A
• Filed: 10/16/1997
• Issued: 02/15/2000
• Est. Priority Date: 10/16/1997
• Status: Expired due to Term

• Current Assignee: iMarket, Inc. (Dun & Bradstreet Corp.)
• Original Assignee: iMarket, Inc. (Dun & Bradstreet Corp.)
• Inventors: Brown, David, Beckingham, Paul
• Primary Examiner(s): Lintz, Paul R.
• Assistant Examiner(s): Corrielus, Jean M.
• Application Number:
  US08/951,688
• Time in Patent Office: 852 Days
• Field of Search: 707/7, 707/536, 707/4, 707/3, 707/6, 704/8, 704/1, 704/200, 395/898
• US Class Current: 707/745
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: Y10S 707/917 Text
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

In a database data processing system, input search data is matched against an index of a database to determine database records which either closely or exactly match the input search data. The input search data is broken down into elements, and elements are converted to terms having a finite set of possible values. The Soundex function may be used to convert elements to terms. The terms are compared against an index of terms to determine which database records relate to the input search data. Through statistical analysis, match records are given a record weight which may be used to calculate how closely the input data actually is to each match record. The invention provides a fast and efficient way of accurately searching for data in extremely large databases, while not requiring precise input search data entry. The invention may also be used to compare or supplement one database against another.

Claims

1. A method of correlating input data to stored data, comprising the steps of:

receiving input data as a plurality of elements;

converting selected elements to a finite family of terms by a first function, such that multiple elements may convert to each term;

matching each term against at least one index of the stored data to obtain a matching term set for each term, wherein each term set is a set of stored match records matching a respective term;

computing record weights for match records existing in the matching term sets; and

applying a second function to match records based on record weights of match records, to determine a match condition of the match records.

2. The method of claim 1, wherein the first function of the converting step is an approximate string matching function which encodes word elements into terms.

3. The method of claim 2, wherein the first function is a Soundex function and the phonetically encoded elements are Soundex terms.

4. The method of claim 1, wherein term set references to records in the stored data are maintained as a bit-map.

5. The method of claim 1, wherein term set references to records in the stored data are maintained as a range index.

6. The method of claim 1, wherein term set references to records in the stored data are maintained as a list of record numbers.

7. The method of claim 1, wherein term set references to records stored in the stored data are maintained as a list of record numbers, as a range index, and as a bit-map.

8. The method of claim 1, wherein the stored data is ordered such that related records of data occur in sequence with each other;

and

wherein a limiting field of the input search data designates a limited range of records of the stored data from which to select match records in said matching step.

9. The method of claim 8, wherein the stored data is ordered based on a geographical location field of each record, and the limiting field is a ZIP code field of the input search data, used to select a limited range of records each having a common ZIP code field.

10. The method of claim 1, wherein the second function comprises a plurality of record match tests applied to certain match records, based on record weights of the certain match records, to determine a match condition of the certain match records.

11. The method of claim 10, further comprising the step of:

applying a third function to certain match records if the second function failed to determine that a match record closely matched the input data.

12. The method of claim 11, wherein the third function is an approximate string matching function applied to highest weighted match records to determine a match condition of the highest weighted match records.

13. The method of claim 11, wherein the third function is a Q-gram function which matches portions of text data from the input data to portions of text data from certain of the top weighted match records to determine a percentage likelihood of a match between the input data and the match records.

14. The method of claim 1, wherein the second function includes a miss record match test which determines a miss match condition indicating that some of the certain match records do not match the input data.

15. The method of claim 1, wherein the second function includes a hit record match test which determines a hit match condition indicating that at least one of the certain match records matches the input data.

16. The method of claim 1, wherein the second function includes a multiple record match test which determines a multiple match condition indicating that a plurality of the certain match records closely match the input data.

17. The method of claim 1, wherein the second function includes hit, multiple and miss record match tests, which, when used together, can determine if there are any match records which closely match the input data.

18. The method of claim 1, wherein the second function comprises a plurality of record match tests, and certain outputs of certain of said plurality of record match tests are used as inputs to other of said plurality of record match tests.

19. The method of claim 1, wherein match records are sorted according to record weights before applying the second function.

20. The method of claim 19, wherein the certain match records comprise match records having weights above a predetermined threshold.

21. The method of claim 19, wherein the second function is only applied to a certain number of records of the records sorted according to weight.

22. The method of claim 1, wherein the matching step includes a pre-limiting step that uses a limiting field of the input data to select a limited index range, wherein the limited index range designates a portion of records within the stored data used to obtain the matching term set for each term.

23. The method of claim 22, wherein the at least one limiting field is a geographical location field.

24. The method of claim 23, wherein the geographical location field is a form of ZIP code.

25. The method of claim 22, wherein the at least one limiting field is a numerical element of the input data.

26. The method of claim 22 wherein record weights for match records are computed from term set weights, the term set weights being computed specific to the term sets obtained from the portion of records.

27. The method of claim 26 wherein the term set weight is based on the number of record identifiers in the term set, the term set weight being heavier if the term set contains a smaller number of record identifiers.

28. The method of claim 1, wherein the matching step includes the step of:

matching a phone number element against an index of phone numbers of records of the stored data, to obtain a set of phone number match records; and

wherein the computing record weights step includes the step of computing record weights of the phone number match records and combining the phone number match records into the set of match records existing in the matching term sets.

29. The method of claim 28, further comprising the step of:

applying a second function comprising a plurality of record match tests to certain match records, based on record weights of the certain match records, to determine a match condition of the certain match records.

30. The method of claim 1, wherein the computing a record weight for each unique match record step further comprises the step of:

for each match record, summing term set weights for term sets which reference the match records, to produce a record weight for that match record.

31. The method of claim 30, wherein the computing a record weight for each unique match record step further comprises the step of:

obtaining a term set weight for each term set matching each term.

32. A system correlating input data to stored data, comprising:

means for receiving input data as a plurality of elements;

means for converting selected elements to a finite family of terms by a first function, such that multiple elements may convert to each term, wherein the first function is an approximate string matching function which encodes word elements into terms;

means for matching each term against at least one index of the stored data to obtain a matching term set for each term, wherein each term set is a set of stored match records matching a respective term;

means for computing record weights for match records existing in the matching term sets; and

means for applying a second function comprising a plurality of record match tests to certain match records, based on record weights of the certain match records, to determine a match condition of the certain match records.

33. The data processing system of claim 32, wherein:

the first function is a Soundex function which phonetically encodes portions of the input search data to Soundex terms and wherein the terms of each index entry are Soundex terms.

34. The database data processing system of claim 33, further comprising:

a means for applying a third function comprising an approximate string matching algorithm test to certain match records, based on record weights of the certain match records, to determine a match condition of the certain match records, in the event that the means for applying a second function fails to determine a match condition.

35. The database data processing system of claim 32, wherein the stored data is ordered such that related records of data occur in sequence with each other;

and

wherein the system includes a means for obtaining a limiting field of the input search data which designates a limited index range of records of the stored data from which to select match records by said means for matching.

36. The database data processing system of claim 35, wherein the means for applying a second function implements a plurality of statistical record match tests, certain of which produce output that is used as input to other of said record match tests, wherein said record match tests determine how closely match records correspond to the input data.

37. The database data processing system of claim 32, wherein:

each index entry includes a term set identifying records in the database that contain elements that convert to the term of that index entry via the first function; and

wherein each index entry has a term set weight indicating the relative number of records in the database referenced in the term set for that index entry, wherein the term set weight is heavier if a term set contains a smaller number of record references.

38. The database data processing system of claim 37, wherein term set record references are represented by a bit-map index.

39. The database data processing system of claim 37, wherein term set record references are represented by a range index.

40. The database data processing system of claim 37, wherein term set record references are represented by a list of record identifiers.

41. A database data processing and searching system comprising:

a computer system including an input device, a processor, an output device and a storage device;

a database of records stored on the storage device and indexed by at least one index having index entries, wherein each index entry contains a Soundex term and a term set referencing records in the database which contain an element of data which converts to the Soundex term of that index entry via a Soundex function;

a field mapper executing on the processor for accepting input search data from the input device, and mapping the input search data to one or more record fields compatible with a record format of records in the database;

a match engine executing on the processor for converting the input search data in the record fields to Soundex input terms via the Soundex function and for matching each Soundex input term with one of the Soundex terms of an index entry, thus indicating a term set of match records for that Soundex input term;

a record weigher executing on the processor for computing record weights for each different match record in the term sets matching the Soundex input terms;

a record tester for applying a plurality of record match functions to determine match conditions of certain match records based upon record weights;

a second tester for applying an approximate string matching function to the input search data and the data of certain match records from the database in an event that the plurality of record match functions are unable to determine a match condition by a threshold amount.

42. A method of matching an input database against a reference database comprising:

providing a geographically sorted reference database of records comprised of elements;

providing a plurality of inverted indexes, each comprising index entries including a phonetically encoded term and a term set indexed by the phonetically encoded term, the term sets containing references to reference database records that contain elements which phonetically encode to the phonetically encoded term of that index entry, and each term set having a term set weight, wherein the term set weight is higher for term sets with a lesser number of references to reference database records;

phonetically encoding elements of records of the input database into input terms;

selecting a portion of records of the input database, based upon a limiting field of the input data, wherein index entries of an inverted index have term sets referencing a limited number of reference database records, based upon the limiting field;

matching the input terms to the phonetically encoded terms of the inverted index entries to determine matching term sets of reference database match records;

computing record weights for each unique match record by summing the term set weights of matching term sets having a reference to the match record;

applying a plurality of second function record match tests, utilizing the record weights of certain match records, to determine a match condition of certain of the match records, said match condition indicating how closely records of the input data base match to records of the reference database.

43. A method of correlating input data to stored data, comprising the steps of:

receiving input data as a plurality of elements;

converting selected elements to a finite family of terms by a first function, such that multiple elements may convert to each term, wherein the first function is an approximate string matching function which encodes word elements into terms;

matching each term against at least one index of the stored data to obtain a matching term set for each term, wherein each term set is a set of stored match records matching a respective term;

applying a second function to match records based on record weights of the match records, to determine a match condition of the match records.

44. The method of claim 43, further comprising the step of:

computing record weights for match records existing in the matching term sets, prior to applying the second function.

45. A computer readable medium encoded with processing logic comprising:

means for receiving input data as a plurality of elements;

means for converting selected elements to a finite family of terms by a first function, such that multiple elements may convert to each term, wherein the first function is an approximate string matching function which encodes word elements into terms;

means for matching each term against at least one index of the stored data to obtain a matching term set for each term, wherein each term set is a set of stored match records matching a respective term;

means for computing record weights for match records existing in the matching term sets; and

means for applying a second function to match records based on record weights of the match records, to determine a match condition of the match records.

46. A method of correlating input data to stored data, comprising the steps of:

receiving input data as a plurality of elements;

converting selected elements to a finite family of terms by a first function, such that multiple elements may convert to each term;

matching each term against at least one index of the stored data to obtain a matching term set for each term, wherein each term set is a set of stored match records matching a respective term, the matching step including a limiting step that selects a limited index range, wherein the limited index range designates a portion of records within the stored data used to obtain the matching term set for each term;

assigning a term set weight to each matching term set based on records in the matching term set; and

computing record weights for match records existing in the matching term sets from the assigned term set weights.

47. The method of claim 46 wherein record weights are computed for each match record by summing term set weights for term sets which reference the match record.

48. A method as claimed in claim 46 wherein the term set weight is based on the number of record identifiers in the matching term set, the term set weight being heavier if the term set contains a smaller number of record identifiers.