Similarity search engine for use with relational databases

• US 20050055345A1
• Filed: 10/20/2004
• Published: 03/10/2005
• Est. Priority Date: 02/14/2002
• Status: Active Grant

• Current Assignee: Fair Isaac Corporation
• Original Assignee: Infoglide Software Corp. (Fair Isaac Corporation)
• Inventors: Ripley, John R.
• Granted Patent: US 7,020,651 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• CPC Class Codes: G06F 16/2468 Fuzzy queries
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

The invention provides a system and method for defining a schema and sending a query to a Similarity Search Engine to determine a quantitative assessment of the similarity of attributes between an anchor record and one or more target records. The Similarity Search Engine makes a similarity assessment in a single pass through the target records having multiple relationship characteristics. The Similarity Search Engine is a server configuration that comprises a Gateway for command and response routing, a Virtual Document Manager for document generation, a Search Manager for document scoring, and an Relational Database Management System for providing data persistence, data retrieval and access to User Defined Functions. The Similarity Search Engine uses a unique command syntax based on the Extensible Markup Language to implement functions necessary for similarity searching and scoring.

Claims

1. A system for performing similarity searching, comprising:

a gateway for handling all communication between a client, a virtual document manager and a search manager;

the virtual document manager connected between the gateway and a relational database management system for providing document management;

the search manager connected between the gateway and the relational database management system for searching and scoring documents; and

the relational database management system for providing relational data management, document and measure persistence, and similarity measure execution.

2. The system of claim 1, wherein the virtual document manager includes a relational database driver for mapping XML documents to relational database tables.

3. The system of claim 1, wherein the virtual document manager includes a statistics processing module for generating statistics based on similarity search results.

4. The system of claim 1, wherein the relational database management system includes means for storing and executing user defined functions.

5. The system of claim 4, wherein the user defined functions include measurement algorithms for determining attribute token similarity scores.

6. A method for performing similarity searching, comprising the steps of:

creating a search schema document by a virtual document manager;

generating one or more query commands by a gateway;

executing one or more query commands in a search manager and relational database management system for determining the degree of similarity between an anchor document and search documents; and

assembling a result document containing document similarity scores of between 0.00 and 1.00.

7. The method of claim 6, wherein the step of creating a schema document comprises designating a structure of search documents, datasets for mapping search document attributes to relational database locations, and semantics identifying measures for computing token attribute similarity search scores between search documents and an anchor document, weights for modulating token attribute similarity search scores, choices for aggregating token attribute similarity search scores into document similarity search scores, and paths to the search document structure attributes.

8. The method of claim 6, wherein the step of generating one or more query commands comprises designating an anchor document, search or schema documents, restrictions on result sets, structure of result sets, and semantics for overriding schema document semantics including measures, weights, choices and paths.

9. The method of claim 6, wherein the step of executing one or more query commands comprises:

computing token attribute similarity search scores having values of between 0.00 and 1.00 for each search document and an anchor document in a relational database management system using measures; and

modulating the token attribute similarity search scores using weights and aggregating the token attribute similarity scores into document similarity scores having values of between 0.00 and 1.00 in the search manager using choices.

10. The method of claim 6, wherein the step of assembling a result document comprises identifying associated query commands and schema documents, document structure, paths to search terms, and similarity scores by the search manager.

11. The method of claim 6, wherein the search schema, the query commands, the search documents, the anchor document and the result document are represented by hierarchical XML documents.

12. The method of claim 7, further comprising selecting measure algorithms from the group consisting of name equivalents, foreign name equivalents, textual, sound coding, string difference, numeric, numbered difference, ranges, numeric combinations, range combinations, fuzzy, date oriented, date to range, date difference, and date combination.

13. The method of claim 7, further comprising selecting choice algorithms from the group consisting of single best, greedy sum, overall sum, greedy minimum, overall minimum, and overall maximum.

14. A computer-readable medium containing instructions for controlling a computer system to implement the method of claim 6.