System and method for producing scored search results on a database using approximate search queries
View Patent ↗A method for searching a database to produce search results from queries likely to contain errors. The process begins by identifying database features likely to be useful in searching, and those features are employed to index the database. After receiving a query from a user, the system develops a rough score for the query, by extracting features from the query, assigning match scores to query features matching database features; and assigning approximation scores to query features amenable to approximation analysis with database features. The rough score is used to identify identifying a set of database records for further analysis. Those records are then subjected to a more detailed rescoring process, based on correspondence between individual query elements and individual record elements, and between the query and the database record content, taken as a whole. Based on the rescoring process, output is provided to the user.
1. A method for searching a computer database to produce search results from queries containing errors, comprising the steps of
indexing features and fields of the computer database, including words and phonetic encodings of the words;
receiving a computer database query from a user;
rough scoring the computer database query against database records, including
extracting words from the computer database query;
assigning match scores to query words matching the computer database features;
assigning approximation scores to the computer database query words amenable to approximation analysis with the computer database features; and
identifying a set of computer database records for further analysis;
rescoring the set of identified computer database records, based on matching the individual computer database query words and individual record fields, and matching at least one phrase of words in the query and multiple fields in the database record; and
providing output to the user based on the results of the rescoring step.
2. The method of claim 1 , wherein the phonetic encodings are Soundex codes.
3. The method of claim 1 , wherein the phonetic encodings are Metaphone codes.
4. The method of claim 1 , wherein the phonetic encodings are Double Metaphone codes.
5. The method of claim 1 , wherein the computer database features include text features.
6. The method of claim 1 , wherein text features are indexed by factors including variants.
7. The method of claim 1 , wherein text features are indexed by factors including semantic equivalents.
8. The method of claim 1 , wherein assigning approximation scores includes calculating the edit distance between a query term under analysis and reference term.
9. The method of claim 1 , wherein assigning approximation scores includes calculating the Hamming distance between a query term under analysis and reference term.
10. The method of claim 1 , wherein assigning approximation scores includes calculating the Levenshtein distance between a query term under analysis and reference term.
11. The method of claim 1 , wherein rescoring includes calculating a word score for each word of the query.
12. The method of claim 11 , wherein the word score is given by
sw
item
=
1
N
∑
j
=
1
N
l
j
-
d
min
(
j
)
l
j
where lj is the length of the j-th word in the query; the subscript item refers to the specific data item under consideration; N is the number of words in the query; and d min (j) is the minimum edit distance between the query item and a reference item.
13. The method of claim 1 , wherein rescoring includes calculating a phrase score for the query.
14. The method of claim 13 , wherein the phrase score is given by
sp
item
=
l
-
d
phrase
l
where l is the length of the phrase and d phrase is the edit distance between the phrase and a reference phrase.
15. The method of claim 1 , wherein rescoring includes calculating a total score for the query.
16. The method of claim 15 , wherein total score is given by
s item =q×sw item +(1 −q )× sp item
where sw item is a word score and sp item is a phrase score, and q is a tunable parameter between 1 and 0.