System and method for searching and matching data having ideogrammatic content

• US 20070162445A1
• Filed: 11/22/2006
• Published: 07/12/2007
• Est. Priority Date: 11/23/2005
• 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 Corp.
• Inventors: Okada, Masayuki, Teoh, Nicholas, Scriffignano, Anthony, Shao, Peihsin, Nedd, Kevin, Matthews, Warwick, Kasai, Mayako, Sy, Jeremy, Lu, Sarah, Prower, Julian, Simpeng, Gan
• Granted Patent: US 7,584,188 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/28 Databases characterised by their database models, e.g. relational or object models
• CPC Class Codes: G06F 16/3331 Query processing
• CPC Class Codes: G06V 30/244 using graphical properties, e.g. alphabet type or font
• 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/99936 Pattern matching access

Abstract

A method of searching and matching non-phonetic or ideogrammatic input data to stored data, including the steps of receiving input data comprising a search string having a plurality of elements, converting a subset of the elements into a set of terms, generating an optimized plurality of keys from the set of terms, retrieving stored data based on the optimized keys corresponding to most likely candidates for match, and selecting a best match from the plurality of candidates. At least some of the ideogrammatic elements form part of an ideogrammatic writing system. The method may also include dividing the search string into a plurality of overlapping sub-segments and identifying sub-segments having inferred semantic meaning as well as sub-segments having no semantic meaning in the ideogrammatic writing system, and using the various sub-segments to generate the optimized keys.

Claims

1. A computerized method of searching and matching input data to stored data, the method comprising:

receiving input data comprising a search string having a plurality of elements, at least some of the elements forming part of an ideogrammatic writing system;

converting a subset of the plurality of elements to a set of terms using at least one method selected from the group consisting of polylogogrammatic semantic disambiguation, hanzee acronym expansion, kanji acronym expansion, and business word recognition;

generating an optimized plurality of keys from the set of terms;

retrieving stored data based on the optimized keys corresponding to most likely candidates for match to the input data; and

selecting a best match from the match candidates.

2. The method of claim 1, wherein the retrieving step uses at least one method selected from the group consisting of sticky hanzee shingling, sticky kanji shingling, dumb hanzee shingling, dumb kanji shingling, and text indexing across a plurality of writing systems.

3. The method of claim 1, wherein the converting step comprises dividing the search string into a plurality of overlapping sub-segments.

4. The method of claim 3, wherein the converting step further comprises identifying sticky sub-segments comprising sub-segments having semantic meaning in the ideogrammatic writing system.

5. The method of claim 4, wherein the converting step further comprises removing noisy sub-segments.

6. The method of claim 5, wherein the converting step further comprises:

identifying dumb sub-segments comprising adjacent elements having no semantic meaning in the ideogrammatic writing system; and

imputing predictiveness from the dumb sub-segments.

7. The method of claim 6, wherein the generating step comprises using the sticky sub-segments and dumb sub-segments to generate the optimized plurality of keys.

8. The method of claim 1, wherein the converting step comprises normalizing traditional and simple versions of the ideogrammatic writing system.

9. The method of claim 1, wherein the ideogrammatic writing system is at least one selected from the group consisting of:

Japanese Kanji, Chinese Traditional, and Chinese Simplified (Hanzee).

10. The method of claim 1, wherein the elements comprise Asian and Roman characters.

11. The method of claim 1, wherein the converting step comprises:

parsing said plurality of elements to identify said set of terms, including name elements, phone number elements, and address elements;

inferring business line through polylogogrammatic methods, cross-checking phone number elements with the address elements; and

recognizing idioms and expressions of the ideogrammatic writing system and keeping the idioms and expressions together to maintain meaning.

12. The method of claim 11, wherein the converting step further comprises identifying structural indicators and acronyms within a name element.

13. The method of claim 11, further comprising establishing longitude and latitude information based on the address elements and through inference of flexible Asian addressing conventions.

14. The method of claim 1 wherein the retrieving step further comprises:

limiting match candidates for certain keys in the plurality of keys that return counts surpassing a predetermined threshold;

generating a cost function for select key intersections;

prioritizing the key intersections according to the cost function; and

retrieving the match candidates in order of the key intersections.

15. The method of claim 1, wherein the retrieving step further comprises generating a matchgrade, a confidence code, and and match data profile for each match candidate based on a degree of match.

16. The method of claim 15, wherein the confidence code is determined at least in part based on the semantic meaning and inferred content of the search string.

17. The method of claim 14, further comprising providing an ordered list of selected match candidates based on said confidence code.

18. The method of claim 15, further comprising assigning each of the candidates in the ordered list to one of a plurality of match levels.

19. The method of claim 18, further comprising determining the assignment of match level by ranking the match candidates in order of their confidence codes and then further differentiating the highest ranking levels based on user-defined tiebreaking rules.

20. A computer readable medium having instructions for performing a method of searching and matching input data to stored data, the method comprising:

receiving input data comprising a search string having a plurality of elements, at least some of the elements forming part of an ideogrammatic writing system;

converting a subset of the plurality of elements to a set of terms using at least one method selected from the group consisting of polylogogrammatic semantic disambiguation, hanzee acronym expansion, kanji acronym expansion, and business word recognition;

generating an optimized plurality of keys from the set of terms;

retrieving stored data based on the optimized keys corresponding to most likely candidates for match to the input data; and

selecting a best match from the match candidates.