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

• US 20060117003A1
• Filed: 01/06/2006
• Published: 06/01/2006
• Est. Priority Date: 07/15/1998
• Status: Active Grant

• Current Assignee: Dwayne Edward Bowman, Ruben Ernesto Ortega
• Original Assignee: Dwayne Edward Bowman, Ruben Ernesto Ortega
• Inventors: Ortega, Ruben Ernesto, Bowman, Dwayne Edward
• Granted Patent: US 7,840,577 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 method of processing search query submissions, the method comprising:

programmatically analyzing search query submissions of a plurality of search engine users to identify search terms that co-occur within search query submissions relatively frequently; and

generating, within computer storage, a table reflective of a result of the programmatic analysis of search query submissions, said table identifying specific search terms that are related to each other.

2. The method as in claim 1, wherein programmatically analyzing the search query submissions comprises weighting some search query submissions differently than other search query submissions.

3. The method of claim 2, wherein weighting some search query submissions differently comprises according, to a search query submission of a user, a weight that is dependent upon whether the user viewed an associated query result item.

4. The method as in claim 1, further comprising using the table to predict correct spellings of selected search terms in multiple-term search queries submitted by users.

5. The method as in claim 4, further comprising updating the table over time to reflect new query submissions from users such that spelling predictions reflect current searching patterns of users.

6. The method as in claim 1, further comprising using the table to select a term to use in place of a non-matching search term in a multi-term search query submitted by a current user.

7. The method as in claim 1, wherein analyzing the search query submissions comprises keeping track of specific search fields in which search terms were entered by users.

8. The method as in claim 1, wherein generating the table comprises incorporating into the table term correlation data derived from a term co-occurrence analysis of a database to which the search queries are directed.

9. A computer storage medium having stored therein a computer program that embodies the method of claim 1.

10. A computer storage medium having stored therein a table generated according to the method of claim 1.

11. The method as in claim 1, wherein programmatically analyzing search query submissions of a plurality of search engine users comprises collectively analyzing query submission histories of said plurality of users in an off-line processing mode.

12. The method as in claim 1, wherein programmatically analyzing search query submissions of a plurality of search engine users comprises generating, for each of a plurality of pairs of search terms, a score that reflects an occurrence count of search query submissions containing the respective pair of search terms.

13. The method as in claim 1, further comprising using the table to programmatically analyze spellings of selected search terms in multiple-term search queries submitted by users.

14. The method as in claim 1, further comprising programmatically analyzing a search query submission that includes a first search term and a second search term, at least in part, by accessing the table to look up at least one additional term that is related to the first search term, and comparing a spelling of the additional term to the second search term.

15. The method as in claim 14, wherein programmatically analyzing the search query submission further comprises suggesting the additional term to a user who made the search query submission if the additional term and the second search term satisfy a spelling similarity test.

16. The method as in claim 1, wherein the table comprises a B-tree data structure.

17. 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

a query processing module that uses the data set to evaluate spellings of search terms of multiple-term search queries.

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

19. The system as in claim 17, 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.

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

21. The system of claim 19, 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.

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

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

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

25. The system as in claim 24, 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.

26. The system as in claim 17, further comprising a component that generates the data set, at least in-part, by programmatically analyzing a data repository of content items to identify pairs of terms that co-occur relatively frequently in said content items.

27. The system as in claim 17, wherein the query processing module 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.

28. The method as in claim 27, wherein the query processing module 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.