System and method for searching and matching databases

• US 7,392,240 B2
• Filed: 11/05/2003
• Issued: 06/24/2008
• Est. Priority Date: 11/08/2002
• Status: Active Grant

• Current Assignee: Dun & Bradstreet Corp., DUN & Bradstreet Incorporated (Dun & Bradstreet Corp.), Hoover's Incorporated (Dun & Bradstreet Holdings, Inc.)
• Original Assignee: DUN & Bradstreet Incorporated (Dun & Bradstreet Corp.)
• Inventors: Gustafson, Eric, Skahill, Larry, Scriffignano, Anthony J., Hayenhjelm, Amy, Shipman, Courtney, Allaway, David, Pillai, Ajay, Ohlson, Edward, Chakraborty, Sudip
• Primary Examiner(s): Rimell; Sam
• Assistant Examiner(s): Lewis; Alicia M
• Application Number:
  US10/702,114
• Publication Number:
  US 20040220918A1
• Time in Patent Office: 1,693 Days
• Field of Search: 707/3, 707/4, 707/5
• US Class Current: 1/1
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/2468 Fuzzy queries
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

A system and method for finding a business entity in a database that matches input data. A web services interface accepts a match request and provides a best match. A pre-processing layer cleans, parses, and standardizes input data into terms. An application layer includes a match engine for processing the match request using the terms. The match engine evaluates and scores match candidates from the database to provide the best match and, optionally, an ordered list of match candidates.

Claims

1. A method comprising:

receiving input data having a plurality of elements;

converting selected elements in said plurality of elements to a set of terms;

generating a plurality of keys from said set of terms;

determining from stored data (a) optimization of said plurality of keys, thus yielding optimized keys, and (b) candidates that share a commonality with said optimized keys, thus yielding key intersections and a quantity for said key intersections;

generating a cost function for said key intersections;

prioritizing said key intersections according to said cost function, thus yielding cost-prioritized key intersections;

retrieving match candidates in order of said cost-prioritized key intersections, and bounded by a pre-determined threshold and said quantity; and

selecting a best match from said match candidates.

2. The method according to claim 1, wherein said converting step comprises:

parsing said plurality of elements to identify said set of terms, including a company name and an address;

cleaning said set of terms, including removing extraneous words; and

standardizing said set of terms.

3. The method according to claim 2, wherein said converting step further comprises:

validating said address having a street name and city name;

correcting said street name and said city name, if necessary; and

assigning a zip code, a latitude, and a longitude.

4. The method according to claim 3, wherein said converting step further comprises:

maintaining at least one reference table.

5. The method according to claim 2, wherein said converting step further comprises:

removing special characters in said set of terms;

removing a last word in said company name if said last word is a standard company form;

converting text in said set of terms to uppercase;

depluralizing select text in said set of terms;

standardizing select words in said set of terms;

normalizing select phrases in said set of terms; and

extracting a street number and a street name from said address.

6. The method according to claim 1, further comprising:

generating a confidence score for each of said match candidates based on a degree of match.

7. The method according to claim 6, further comprising:

providing an ordered list of selected match candidates based on said confidence score.

8. The method according to claim 6, wherein said confidence score is based on comparison scoring.

9. The method according to claim 8, wherein said comparison scoring step comprises:

determining a score for a business name, a street name, and a city name in a pair, said pair being said set of terms and one of said match candidates;

classifying said pair into data segments using a decision tree;

performing logistic modeling using said data segments;

determining a match probability for said pair; and

assigning a grade to said pair.

10. The method according to claim 9, wherein said comparison scoring step further comprises:

determining a uniqueness score based on a number of matching business names in said city name.

11. The method according to claim 9, wherein said comparison scoring step further comprises:

calculating a business density score for said pair.

12. The method according to claim 9, wherein said comparison scoring step further comprises:

calculating a zip score.

13. The method according to claim 9, wherein said comparison scoring step further comprises:

calculating an industry score by matching words in said business name to standard industrial classification (SIC) key words.

14. A system comprising:

(A) web services interface for accepting a match request and providing a best match;

(B) pre-processing layer having a cleaning, parsing, and standardizing component for converting input data into a set of terms;

(C) an application layer for;

generating a plurality of keys from said set of terms,

determining from stored data (a) optimization of said plurality of keys, thus yielding optimized keys, and (b) candidates that share a commonality with said optimized keys, thus yielding key intersections and a quantity for said key intersections;

generating a cost function for said key intersections;

prioritizing said key intersections according to said cost function, thus yielding cost-prioritized key intersections;

obtaining match candidates in order of said cost-prioritized key intersections, and bounded by a pre-determined threshold and said quantity; and

selecting said best match from said match candidates; and

(D) a database layer for retrieving said candidates from stored business entity information for said application layer.

15. The system according to claim 14, wherein said application layer comprises:

a decisioning component for determining a best match and an ordered list of said match candidates.

16. The system according to claim 15, wherein said web services interface also provides an ordered list of said match candidates from said application layer.

17. The system according to claim 14, further comprising:

a plurality of memories in said pre-processing layer, said application layer, and said database layer;

a plurality of asynchronous message queues in said pre-processing layer, said application layer, and said database layer; and

a plurality of caching systems in said pre-processing layer, said application layer, and said database layer.

18. A computer readable medium comprising instructions for performing a method that includes:

receiving input data having a plurality of elements;

converting selected elements in said plurality of elements to a set of terms;

generating a plurality of keys from said set of terms;

determining from stored data (a) optimization of said plurality of keys, thus yielding optimized keys, and (b) candidates that share a commonality with said optimized keys, thus yielding key intersections and a quantity for said key intersections;

generating a cost function for said key intersections;

prioritizing said key intersections according to said cost function, thus yielding cost-prioritized key intersections;

retrieving match candidates in order of said cost-prioritized key intersections, and bounded by a pre-determined threshold and said quantity; and

selecting a best match from said match candidates.

19. The computer readable medium according to claim 18, wherein said converting step comprises:

parsing said plurality of elements to identify said set of terms, including a company name and an address;

cleaning said set of terms, including removing extraneous words; and

standardizing said set of terms.

20. The computer readable medium according to claim 18, wherein said selecting step comprises:

determining a score for a business name, a street name, and a city name in a pair, said pair being said set of terms and one of said match candidates;

determining a uniqueness score based on a number of matching business names in said city name;

calculating a business density score for said pair;

calculating a zip score; and

calculating an industry score by matching words in said business name to standard industrial classification (SIC) key words.