Similarity search engine for use with relational databases

• US 7,020,651 B2
• Filed: 10/20/2004
• Issued: 03/28/2006
• Est. Priority Date: 02/14/2002
• Status: Expired due to Fees

• Current Assignee: Fair Isaac Corporation
• Original Assignee: Infoglide Software Corp. (Fair Isaac Corporation)
• Inventors: Ripley, John R.
• Primary Examiner(s): Alam, Shahid
• Application Number:
  US10/969,473
• Publication Number:
  US 20050055345A1
• Time in Patent Office: 524 Days
• Field of Search: 707/3, 707/4, 707/5, 707/6, 707/10, 707/100, 707/104.1, 707/103.R, 705/8, 705/10, 713/200, 715/506, 715/700, 715/716, 717/108, 717/126, 709/218, 709/219
• 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 software system implemented by instructions in a computer system for performing similarity searching, comprising:

a gateway that handles all communication between a client and the software system, between the gateway and a virtual document manager and between the gateway and a search manager;

the virtual document manager connected between the gateway and a relational database management system that receives command from the gateway and provides schema and document management;

the search manager connected between the gateway and the relational database management system that receives commands from the gateway, initiates attribute token similarity searches in the relational database management system using prestored attribute token similarity measure algorithms, receives attribute token similarity search results from the relational database management system, aggregates the attribute token similarity search results into document similarity search results sets, and forwards the document similarity search result sets to the gateway;

the relational database management system that provides relational data management, document and attribute token similarity measure algorithm persistence, and attribute token similarity measure algorithm execution; and

the gateway that sends documents from the virtual document manager and document similarity search result sets from the search manager to the client.

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 software method implemented by instructions in a computer system for performing similarity searching, comprising the steps of:

receiving a request by a gateway from a client for initiating a similarity search;

creating a search schema document by a virtual document manager;

generating one or more query commands by the gateway;

executing one or more query commands in a search manager that causes a relational database management system to perform attribute token similarity searches;

determining the degree of similarity between an anchor document and search documents by the search manager that aggregates attribute token similarity search scores from the relational database management system; and

assembles document similarity search result sets containing document similarity scores of between 0.00 and 1.00; and

sending the similarity search sets to the client by the gateway.

7. The method of claim 6, wherein the step of creating a schema document comprises;

designating a structure of search documents;

designating datasets for mapping search document attributes to relational database locations; and

designating 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, stnicture 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 mare 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 measure algorithms; 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 choice algorithms.

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.