Search query processing to identify related search terms and to correct misspellings of search terms

• US 7,840,577 B2
• Filed: 01/06/2006
• Issued: 11/23/2010
• Est. Priority Date: 07/15/1998
• Status: Expired due to Fees

• Current Assignee: A9.com Incorporated (Amazon.com, Inc.)
• Original Assignee: A9.com Incorporated (Amazon.com, Inc.)
• Inventors: Ortega, Ruben Ernesto, Bowman, Dwayne Edward
• Primary Examiner(s): Lu; Kuen S
• Application Number:
  US11/326,629
• Publication Number:
  US 20060117003A1
• Time in Patent Office: 1,782 Days
• Field of Search: 707/3, 707/4, 707/758
• US Class Current: 707/758
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: G06F 16/90 Details of database functions independent of the retrieved data types
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9532 Query formulation
• CPC Class Codes: G06F 40/226 Validation
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: G06F 40/274 Converting codes to words; Guess-ahead of partial word inputs
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• 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/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A search engine process predicts the correct spellings of search terms within multiple-term search queries. In one embodiment, when a user submits a multiple-term search query that includes a non-matching term and at least one matching term, a table is accessed to look up a set of terms that are “related” to the matching term or terms. A spelling comparison function is then used to determine whether any of these related terms is sufficiently similar in spelling to the non-matching term to be deemed a candidate correctly-spelled replacement. A candidate replacement term may automatically be substituted for the non-matching term, or may be suggested to the user as a replacement. The invention also includes a process for identifying terms that are related to each other based on the relatively high frequencies with which they co-occur in search queries of users, database records, and/or specific database fields.

Claims

1. A system for processing search query submissions, the system comprising:

a data set that maps individual terms to sets of related terms, said data set stored in a computer memory and being based at least partly on a term co-occurrence analysis, said data set comprising a plurality of entries, each of which maps an individual term to a respective set of related terms; and

a query processing system that uses the data set to identify alternative spellings of misspelled search terms of multiple-term search queries, said query processing system comprising computer hardware that executes software.

2. The system as in claim 1, wherein the data set reflects a result of a search term co-occurrence analysis of search query submissions.

3. The system as in claim 1, wherein the data set reflects a result of a search term co-occurrence analysis in which a weight accorded to a search query submission from a user is dependent upon actions performed by the user with respect to associated query result items.

4. The system of claim 3, wherein the weight accorded to the search query submission is dependent upon whether the user viewed a resulting query result item.

5. The system of claim 3, wherein the weight accorded to the search query submission is dependent upon whether the user selected a resulting query result item for purposes of performing a transaction.

6. The system of claim 1, wherein the data set comprises search term correlation data for each of a plurality of search fields.

7. The system as in claim 1, wherein the data set reflects a result of a term co-occurrence analysis of a database searched by the query processing system.

8. The system as in claim 1, further comprising a component that generates the data set, at least in-part, by programmatically analyzing search query submissions of a plurality of users.

9. The system as in claim 8, wherein the component generates, for each of a plurality of pairs of terms, a score that reflects a number of times the pair of terms have co-occurred in search query submissions of users.

10. The system as in claim 1, further comprising a component that generates the data set, at least in-part, by programmatically analyzing a data repository of content items to identify terms that are related to each other based on co-occurrences of said terms in said content items.

11. The system as in claim 1, wherein the query processing system evaluates a spelling of a multiple-term search query, at least in part, by accessing the data set to identify at least one related term that is related to a first search term of said multiple-term search query, and comparing a spelling of the related term to a second search term of said multiple-term search query.

12. The system as in claim 11, wherein the query processing system suggests the related term to a user who submitted the multiple-term search query if the related term and the second search term satisfy a spelling similarity test.

13. The system as in claim 1, wherein the query processing system is operative to use the data set to look up terms that are related to a first search term of a multiple-term search query, and to compare spellings of the looked-up related terms to a spelling of a second search term of the multiple-term search query, said second term being a potentially misspelled term.

14. The system as in claim 1, further comprising a component that generates the data set at least partly by performing a term co-occurrence analysis of a database of product information.

15. The system as in claim 1, further comprising a component that generates the data set, at least in-part, by measuring a degree to which particular search terms co-occur in search query submission of users, said component operative to weight some search query submissions differently than others based on user actions performed in connection with corresponding search query results.