Method and system for interpreting multiple-term queries

• US 20040117366A1
• Filed: 12/12/2002
• Published: 06/17/2004
• Est. Priority Date: 12/12/2002
• Status: Abandoned Application

• Current Assignee: Endeca Technologies Incorporated (Oracle Corporation)
• Original Assignee: Endeca Technologies Incorporated (Oracle Corporation)
• Inventors: Ferrari, Adam J., Tunkelang, Daniel
• Application Number:
  US10/317,337
• Publication Number:
  US 20040117366A1
• Time in Patent Office: Days
• US Class Current: 707/5
• CPC Class Codes: G06F 16/3344 using natural language analysis

Abstract

A query interpretation method and system uses a combination of context-independent and contextual evaluation to compute interpretations for multiple-term queries. The present invention can be used to search a collection of items, each of which is associated with one or more terms. In certain embodiments, query interpretation involves generating several candidate multiple-term interpretations and scoring them to select one or more interpretations. In certain embodiments, query interpretation involves identifying single-term interpretations for the terms in the query, determining context-independent scores for those single-term interpretations, identifying a plurality of candidate multiple-term interpretations, determining a contextual score for each candidate multiple-term interpretation, and generating one or more multiple-term interpretations that are optimal with respect to a combination of the context-independent and contextual scoring functions.

Claims

1. A method of interpreting a query formed of at least a first term and a second term with respect to a database of items, comprising:

identifying at least one candidate single-term interpretation for the first term;

identifying at least one candidate single-term interpretation for the second term;

determining a context-independent score for each candidate single-term interpretation;

identifying one or more candidate multiple-term interpretations, wherein a candidate multiple-term interpretation is a combination of candidate single-term interpretations;

determining a combined context-independent score for each candidate multiple-term interpretation using the context-independent score for each candidate single-term interpretation in the multiple-term interpretation;

determining a contextual score for each candidate multiple-term interpretation using the database; and

determining an overall score for each candidate multiple-term interpretation by using the contextual score and the combined context-independent score for the multiple-term interpretation.

2. The method of claim 1, wherein identifying one or more candidate multiple-term interpretations includes identifying a plurality of candidate multiple-term interpretations, and further including the step of identifying at least one multiple-term interpretation from the plurality of candidate multiple-term interpretations that is optimal based on the overall scores.

3. The method of claim 1, wherein the first term and the second term correspond to individual words.

4. The method of claim 1, wherein the first term corresponds to a phrase of two or more words.

5. The method of claim 1, wherein the first set and the second set of candidate single-term interpretations include the terms in the query.

6. The method of claim 1, wherein the candidate single-term interpretations are generated by using the first term and the second term into a single term.

7. The method of claim 1, wherein the candidate single-term interpretations are generated by splitting the first term into two terms.

8. The method of claim 1, wherein the candidate single-term interpretations are generated by character-editing transformations.

9. The method of claim 1, wherein the candidate single-term interpretations are generated using syntactic transformations.

10. The method of claim 1, wherein the candidate single-term interpretations are generated using a thesaurus.

11. The method of claim 1, wherein determining the context-independent scores includes incorporating edit distances.

12. The method of claim 1, wherein determining the context-independent scores includes incorporating probabilities associated with syntactic transformations.

13. The method of claim 1, wherein determining the context-independent scores includes incorporating probabilities associated with semantic relationships.

14. The method of claim 1, wherein determining the context-independent scores includes distinguishing between single-term interpretations that include at least one result and those that return no results.

15. The method claim 1, wherein determining the context-independent scores includes incorporating the number of results that would be returned for that single-term interpretation.

16. The method of claim 1, wherein determining the context-independent scores includes using a quality measure of the results corresponding to that single-term interpretation.

17. The method of claim 1, wherein identifying one or more candidate multiple-term interpretations includes considering all possible combinations of candidate single-term interpretations in which the terms in the query are represented once.

18. The method of claim 1, wherein identifying one or more candidate multiple-term interpretations includes considering a subset of all possible combinations of candidate single-term interpretations in which each term in the query is represented once.

19. The method of claim 18, wherein the subset is obtained using a greedy algorithm.

20. The method of claim 18, wherein the subset is obtained using a best-first-search algorithm.

21. The method of claim 18, wherein the subset is obtained using a branch-and-bound algorithm.

22. The method of claim 18, wherein the subset is obtained using a dynamic programming algorithm.

23. The method of claim 1, wherein identifying a plurality of candidate multiple-term interpretations includes considering combinations that include candidate single-term interpretations corresponding to all terms in the query.

24. The method of claim 1, wherein identifying a plurality of candidate multiple-term interpretations includes considering combinations that include candidate single-term interpretations corresponding to a part of the query.

25. The method of claim 1, wherein determining a contextual score includes distinguishing between multiple-term interpretations that return at least one result and those that return no results.

26. The method of claim 1, wherein determining a contextual score includes determining a number of result items corresponding to the multiple-term interpretation.

27. The method of claim 1, wherein at least one of the items includes more than one field, wherein determining a contextual score includes determining whether the multiple terms match the same field.

28. The method of claim 27, wherein determining a contextual score includes considering the field that is matched.

29. The method of claim 1, wherein determining a contextual score includes incorporating a quality of results measure.

30. The method of claim 1, wherein determining a contextual score includes determining whether the order of the terms from the multiple-term interpretation in the results matches the order of corresponding terms in the query.

31. The method of claim 1, wherein determining an overall score includes using the contextual score to break ties between multiple-term interpretations with the same context-independent score.

32. The method of claim 1, further including the step of parsing the query to identify at least the first term and the second term.

33. The method of claim 1, wherein determining a contextual score for each candidate multiple-term interpretation includes treating the candidate multiple-term interpretations as a conjunction.

34. The method of claim 1, wherein determining a contextual score for each candidate multiple-term interpretation includes treating the candidate multiple-term interpretations as disjunctions.

35. The method of claim 1, wherein determining a contextual score for each candidate multiple-term interpretation includes considering partial matches of the candidate multiple-term interpretations.

36. The method of claim 1, wherein determining a contextual score for each candidate multiple-term interpretation includes considering a high-information component of the candidate multiple-term interpretations.

37. The method of claim 1, wherein determining a contextual score for each candidate multiple-term interpretation includes considering term proximity in the candidate multiple-term interpretations.

38. A computer program product, residing on a computer readable medium, for use in interpreting queries composed of at least a first term and a second term relative to a database of items, the computer program product comprising instructions for causing a computer to:

identify a first set of at least one candidate single-term interpretation for the first term;

identify a second set of at least one candidate single-term interpretation for the second term;

determine a context-independent score for each candidate single-term interpretation;

identify one or more candidate multiple-term interpretations, wherein a candidate multiple-term interpretation is a combination of candidate single-term interpretations;

determine a combined context-independent score for each candidate multiple-term interpretation using the context-independent score for each candidate single-term interpretation in the multiple-term interpretation;

determine a contextual score for each candidate multiple-term interpretation using the database;

determine an overall score for each candidate multiple-term interpretation by using the contextual score and the combined context-independent score for the multiple-term interpretation; and

identify at least one multiple-term interpretation from the plurality of candidate multiple-term interpretations that is optimal based on the overall scores.

39. The method of claim 38, wherein identifying one or more candidate multiple-term interpretations includes identifying a plurality of candidate multiple-term interpretations, and further including the step of identifying at least one multiple-term interpretation from the plurality of candidate multiple-term interpretations that is optimal based on the overall scores.

40. The method of claim 38, wherein the candidate single-term interpretations are generated by using the first term and the second term into a single term.

41. The method of claim 38, wherein the candidate single-term interpretations are generated by splitting the first term into two terms.

42. The method of claim 38, wherein the candidate single-term interpretations are generated by character-editing transformations.

43. The method of claim 38, wherein the candidate single-term interpretations are generated using syntactic transformations.

44. A method for interpreting a query composed of at least a first term and a second term relative to a database of items, comprising:

identifying at least one candidate single-term interpretation for the first term;

identifying at least one candidate single-term interpretation for the second term;

evaluating a plausibility of each candidate single-term interpretation;

identifying one or more candidate multiple-term interpretations, wherein a candidate multiple-term interpretation is a combination of candidate single-term interpretations; and

evaluating a plausibility of each candidate multiple-term interpretation based on the plausibility of each candidate single-term interpretation and based on comparing the candidate multiple-term interpretation against the items in the database identifying at least one multiple-term interpretation from the plurality of candidate multiple-term interpretations that has greater plausibility than the other candidate multiple-term interpretations.

45. The method of claim 44, wherein identifying one or more candidate multiple-term interpretations includes identifying a plurality of candidate multiple-term interpretations, and further including the step of identifying at least one multiple-term interpretation from the plurality of candidate multiple-term interpretations that is optimal based on the overall scores.

46. A method for processing a query with respect to a database of items, comprising:

obtaining a query from a user;

identifying at least a first term and a second term in the query;

identifying at least one candidate single-term interpretation for the first term;

identifying at least one candidate single-term interpretation for the second term;

determining a context-independent score for each candidate single-term interpretation;

identifying a plurality of candidate multiple-term interpretations, wherein a candidate multiple-term interpretation is a combination of candidate single-term interpretations;

determining a combined context-independent score for each candidate multiple-term interpretation using the context-independent score for each candidate single-term interpretation in the multiple-term interpretation;

determining a contextual score for each candidate multiple-term interpretation using the database;

determining an overall score for each candidate multiple-term interpretation by using the contextual score and the combined context-independent score for the multiple-term interpretation;

identifying at least one multiple-term interpretation from the plurality of candidate multiple-term interpretations that is optimal based on the overall scores; and

using the at least one multiple-term interpretation that is optimal in a result provided to the user.