Fuzzy search using progressive relaxation of search terms

• US 8,082,270 B2
• Filed: 03/25/2009
• Issued: 12/20/2011
• Est. Priority Date: 11/14/2008
• Status: Active Grant

• Current Assignee: Deem, Incorporated (Jack Taylor Family Voting Trust U A D 4 14 99)
• Original Assignee: Ketera Software India PVT Limited
• Inventors: Goyal, Ram Dayal
• Primary Examiner(s): LY, CHEYNE D
• Application Number:
  US12/410,465
• Publication Number:
  US 20100125596A1
• Time in Patent Office: 1,000 Days
• Field of Search: 707/713, 707/478, 707/780
• US Class Current: 707/780
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: G06F 16/38 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually

Abstract

Disclosed herein is a computer implemented method and system that progressively relaxes search terms provided by a user. Data of predefined types is stored in a database. The data is obtained by uniquely modifying data previously stored in the database, based on the predefined types. Search terms of predefined types are accepted from the user. The search terms are compared with the stored data to find exact matches, if length of the search terms exceeds a predefined value. On not finding exact matches, the accepted search terms are modified uniquely based on the predefined types to structure first alternative queries. The first alternative queries are compared with the stored data to find exact matches. On not finding exact matches, the first alternative queries are modified based on the predefined types to structure second alternative queries. The second alternative queries are compared with the stored data to find approximate matches.

Claims

1. A computer implemented method of progressively relaxing search terms provided by a user for finding matches of said search terms in a database, comprising the steps of:

storing data of predefined types into a plurality of first data fields of a multicolumn table in said database, wherein said data is obtained by uniquely modifying data previously stored in a plurality of second data fields in the database, wherein said previously stored data is modified based on said predefined types of the previously stored data, wherein the predefined types comprise name, street address, city, state, zip, and country;

accepting a plurality of the search terms of the predefined types from said user, wherein length of said accepted search terms is computed;

comparing the accepted search terms with said stored data in said first data fields to find exact matches, if said length of the accepted search terms is greater than a predefined value;

modifying the accepted search terms to structure first alternative queries if said exact matches are not found, wherein each of the accepted search terms is modified uniquely based on the predefined types of the accepted search terms;

comparing said structured first alternative queries with the stored data in the first data fields to find exact matches;

modifying the first alternative queries to structure second alternative queries if said exact matches are not found, wherein each of the first alternative queries is modified uniquely based on the predefined types of the first alternative queries, and wherein said steps of modifying the accepted search terms and modifying the first alternative queries comprise concatenating and compensating for spelling errors, typographical errors, punctuation errors, phonological ambiguity, and non standard querying; and

comparing by the comparison module said structured second alternative queries with the stored data in the first data fields to find approximate matches;

whereby said modification of the search terms and the first alternative queries to structure the first alternative queries and the second alternative queries respectively enables progressive relaxation of the search terms for finding matches of the search terms in the database.

2. The computer implemented method of claim 1, further comprising a step of ranking said found matches based on accuracy of the found matches.

3. The computer implemented method of claim 2, wherein said step of ranking the found matches is performed based on a matching score, wherein said matching score is computed based on accuracy of the found matches.

4. A computer implemented system for progressively relaxing search terms provided by a user for finding matches of said search terms in a database, comprising:

a processor;

a storage module storing data of predefined types into a plurality of first data fields of a multicolumn table in said database, wherein said data is obtained by uniquely modifying data previously stored in a plurality of second data fields in the database, wherein said previously stored data is modified based on said predefined types of the previously stored data, wherein the predefined types comprise name, street address, city, state, zip, and country;

an input module accepting a plurality of the search terms of the predefined types from said user, wherein length of said accepted search terms is computed;

a comparison module comparing the accepted search terms with said stored data in said first data fields to find exact matches, if said length of the accepted search terms is greater than a predefined value;

a modification module modifying the accepted search terms to structure first alternative queries if said exact matches are not found, wherein each of the accepted search terms is modified uniquely based on the predefined types of the accepted search terms;

comparing by the comparison module said structured first alternative queries with the stored data in the first data fields to find exact matches;

modifying by the modification module the first alternative queries to structure second alternative queries if said exact matches are not found, wherein each of the first alternative queries is modified uniquely based on the predefined types of the first alternative queries, and wherein said steps of modifying the accepted search terms and modifying the first alternative queries comprise concatenating and compensating for spelling errors, typographical errors, punctuation errors, phonological ambiguity, and non standard querying;

comparing by the comparison module said structured second alternative queries with the stored data in the first data fields to find approximate matches;

whereby said modification of the search terms and the first alternative queries to structure the first alternative queries and the second alternative queries respectively enables progressive relaxation of the search terms for finding matches of the search terms in the database.

5. The computer implemented system of claim 4, further comprising a ranking module for ranking said found matches based on accuracy of the found matches.

6. The computer implemented system of claim 4, further comprising a computation module for computing length of the accepted search terms, wherein said length is compared with a predefined value to determine need for comparing the accepted search terms with the stored data in the first data fields to find exact matches.

7. The computer implemented system of claim 6, wherein said computation module further computes a matching score for each of said found matches.

8. A non-transitory computer readable medium storing instructions for progressively relaxing search terms provided by a user for finding matches of said search terms in a database, wherein the instructions when executed by a processor performing steps of:

storing data of predefined types into a plurality of first data fields of a multicolumn table in said database, wherein said data is obtained by uniquely modifying data previously stored in a plurality of second data fields in the database, wherein said previously stored data is modified based on said predefined types of the previously stored data, wherein the predefined types comprise name, street address, city, state, zip, and country;

accepting a plurality of the search terms of the predefined types from said user, wherein length of said accepted search terms is computed;

comparing the accepted search terms with said stored data in said first data fields to find exact matches, if said length of the accepted search terms is greater than a predefined value;

modifying the accepted search terms to structure first alternative queries if said exact matches are not found, wherein each of the accepted search terms is modified uniquely based on the predefined types of the accepted search terms;

comparing said structured first alternative queries with the stored data in the first data fields to find exact matches;

modifying by the modification module the first alternative queries to structure second alternative queries if said exact matches are not found, wherein each of the first alternative queries is modified uniquely based on the predefined types of the first alternative queries, and wherein said steps of modifying the accepted search terms and modifying the first alternative queries comprise concatenating and compensating for spelling errors, typographical errors, punctuation errors, phonological ambiguity, and non standard querying;

comparing said structured second alternative queries with the stored data in the first data fields to find approximate matches;

whereby said modification of the search terms and the first alternative queries to structure the first alternative queries and the second alternative queries respectively enables progressive relaxation of the search terms for finding matches of the search terms in the database.