Weight-based stemming for improving search quality

• US 8,661,049 B2
• Filed: 07/09/2012
• Issued: 02/25/2014
• Est. Priority Date: 07/09/2012
• Status: Active Grant

• Current Assignee: Zendesk Incorporated
• Original Assignee: Zendesk Incorporated
• Inventors: Will, Stefan, Grenier, Pierre C.
• Primary Examiner(s): Coby, Frantz
• Application Number:
  US13/544,890
• Publication Number:
  US 20140012841A1
• Time in Patent Office: 596 Days
• Field of Search: 707706-707, 707722-723, 707/748, 707/752, 707/759, 707765-766, 707/769, 709/201, 709/203, 709/213, 709/217
• US Class Current: 707/759
• CPC Class Codes: G06F 16/3338 Query expansion

Abstract

A technique including receiving a search query; identifying a first original query term based on the query; identifying a first expanded query term related to the first original query term; determining a first lexical distance between the first original query term and the first expanded query term; determining a first weight for the first expanded query term based on the determined first lexical distance; identifying a plurality of documents, from among a corpus of documents, as each relevant to the search query, the plurality of documents including a first document identified based on its inclusion of the first expanded query term; ranking the plurality of documents, with the ranking of the first document being based upon the calculated first weight; and generating a response to the search query identifying two or more of the plurality of documents, ordered according to the ranking.

Claims

1. A computer-implemented method comprising:

receiving a search query;

identifying a first original query term based on the query;

identifying a first expanded query term related to the first original query term;

determining a first lexical distance between the first original query term and the first expanded query term;

determining a first weight for the first expanded query term based on the determined first lexical distance;

identifying a plurality of documents, from among a corpus of documents, as each relevant to the search query, the plurality of documents including a first document identified based on an inclusion of the first expanded query term;

ranking the plurality of documents, with the ranking of the first document being based upon the calculated first weight; and

generating a response to the search query identifying two or more of the plurality of documents, ordered according to the ranking.

2. The method of claim 1, further comprising:

identifying a second expanded query term related to the first original query term;

determining a second lexical distance between the first original query term and the second expanded query term;

determining a second weight for the second expanded query term based on the determined second lexical distance; and

identifying a second document from among the corpus of documents based on an inclusion of the second expanded query term, the second document being included in the plurality of documents,

wherein the ranking of the second document is based upon the calculated second weight.

3. The method of claim 1, wherein the determining the first lexical distance comprises determining an edit distance between the first original query term and the first expanded query term.

4. The method of claim 3, wherein the determining the edit distance comprises determining a Levenshtein distance between the first original query term and the first expanded query term.

5. The method of claim 1, wherein the first weight is determined according to a function approximately equal to exp(−

d), where d corresponds to the lexical distance.

6. The method of claim 1, wherein the identifying the first expanded query term comprises identifying a word based on the word having a stem in common with the first original query term key.

7. The method of claim 6, wherein the identifying the word comprises:

determining a stem for the first original query term; and

retrieving the word from an index or table by utilizing the determined stem as a key.

8. The method of claim 1, further comprising:

identifying a second expanded query term related to the first original query term;

determining a second lexical distance between the first original query term and the second expanded query term;

determining a second weight for the second expanded query term based on the calculated second lexical distance, where the second weight is determined in accordance with the first strictly decreasing function of lexical distance; and

determining not to utilize the second expanded query term for the identifying the plurality of documents as a result of the second weight being at or below a threshold value.

9. The method of claim 1, further comprising:

identifying a second expanded query term related to the first original query term;

determining a second lexical distance between the first original query term and the second expanded query term; and

determining not to utilize the second expanded query term for the identifying the plurality of documents as a result of the second lexical distance being at or above a threshold value.

10. The method of claim 1, wherein the plurality of documents are support tickets for a customer support system.

11. The method of claim 1, further comprising:

identifying a second expanded query term related to the first original query term;

identifying a third expanded query term based on the third expanded query term having a stem in common with the second expanded query term;

determining a second lexical distance between the second expanded query term and the third expanded query term;

determining a second weight for the third expanded query term based on the determined second lexical distance; and

identifying a second document from among the corpus of documents based on an inclusion of the third expanded query term, the second document being included in the plurality of documents,

wherein the ranking of the second document is based upon the calculated second weight.

12. The method of claim 11, wherein the identifying the second expanded query term comprises selecting the second expanded query term from a thesaurus which identifies the second expanded query term as related to the first original query term.

13. A search system comprising:

a query expansion engine programmed to

receive a search query;

identify a first original query term based on the query;

identify a first expanded query term related to the first original query term;

determine a first lexical distance between the first original query term and the first expanded query term; and

determine a first weight for the first expanded query term based on the determined first lexical distance;

a search system programmed to identify a plurality of documents, from among a corpus of documents, as each relevant to the search query, the plurality of documents including a first document identified based on an inclusion of the first expanded query term; and

a ranking engine programmed to rank the plurality of documents, with the ranking of the first document being based upon the calculated first weight,

wherein the search system is further programmed to generate a response to the search query identifying two or more of the plurality of documents, ordered according to the ranking.

14. The search system of claim 13, wherein

the query expansion engine is further programmed to identify a second expanded query term related to the first original query term;

determine a second lexical distance between the first original query term and the second expanded query term; and

determine a second weight for the second expanded query term based on the determined second lexical distance; and

the search system is further programmed to identify a second document from among the corpus of documents based on an inclusion of the second expanded query term, the second document being included in the plurality of documents,

wherein the ranking of the second document is based upon the calculated second weight.

15. The search system of claim 13, wherein the programming for the query expansion engine to determine the first lexical distance includes instructions which determine an edit distance between the first original query term and the first expanded query term.

16. The search system of claim 15, wherein the programming for the query expansion engine to determine the edit distance comprises instructions which determine a Levenshtein distance between the first original query term and the first expanded query term.

17. The search system of claim 13, wherein the first weight is determined according to a function approximately equal to exp(−

d), where d corresponds to the lexical distance.

18. The search system of claim 13, wherein the programming for the query expansion engine to identify the first expanded query term comprises instructions which identify a word based on the word having a stem in common with the first original query term.

19. The search system of claim 18, wherein the instructions which identify the word comprise:

instructions to determine a stem for the first original query term; and

instructions to retrieve the word from an index or table by utilizing the determined stem as a key.

20. The search system of claim 13, wherein

the query engine is further programmed to identify a second expanded query term related to the first original query term;

determine a second lexical distance between the first original query term and the second expanded query term; and

determine a second weight for the second expanded query term based on the calculated second lexical distance, where the second weight is determined in accordance with the first strictly decreasing function of lexical distance,

wherein the second expanded query term is not used to identify the plurality of documents as a result of the second weight being at or below a threshold value.