Systems and methods for interactive search query refinement

• US 6,947,930 B2
• Filed: 04/25/2003
• Issued: 09/20/2005
• Est. Priority Date: 03/21/2003
• Status: Active Grant

• Current Assignee: Jollify Management Limited
• Original Assignee: Overture Services Incorporated (Apollo Global Management, Inc.)
• Inventors: Thrall, John, Gourlay, Alastair, Anick, Peter G.
• Primary Examiner(s): BREENE, JOHN E
• Assistant Examiner(s): BREENE, JOHN E
• Application Number:
  US10/424,180
• Publication Number:
  US 20040186827A1
• Time in Patent Office: 879 Days
• Field of Search: 707 2- 5, 707/100, 707/101, 707/102, 707/104.1, 707/9, 707/10, 715/500, 715/501.1, 715/513
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3325 Reformulation based on results of preceding query
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A received query is processed so as to generate an initial group of ranked documents corresponding to the received query. Each document in all or a portion of the documents in the initial group of ranked documents is associated with a respective set of ranked candidate terms such that each candidate term in the respective set of ranked candidate terms is embedded within the document. Each respective set of ranked candidate terms is identified at a time prior to the processing of the received query. In accordance with a selection function, a subset of the candidate terms in one or more of the respective sets of candidate terms is selected. In response to the received query, the initial group of ranked documents and the subset of candidate terms are presented.

Claims

1. A method of refining a received query, comprising processing said received query so as to generate an initial group of ranked documents corresponding to the received query, wherein each document in all or a portion of the documents in said initial group of ranked documents is associated with a respective set of precomputed ranked candidate terms such that each candidate term in said respective set of ranked candidate terms is embedded within said document;

selecting, in accordance with a selection function, a subset of candidate terms that are in one or more of said respective sets of ranked candidate terms;

an presenting, in response to the received query, the initial group of ranked documents and said subset of candidate terms.

2. The method of claim 1 wherein, for all or a portion of the top-ranked documents in said initial group of ranked documents, the respective set of ranked candidate terms associated with said document is identified by:

(A) comparing a term in said document to a master list of candidate terms, wherein, when said term is in said master list of candidate terms, said term is added to a set of candidate terms;

(B) repeating said comparing number of times; and

(C) ranking said candidate terms in said set of candidate terms, thereby forming said respective set of ranked candidate terms.

3. The method of claim 2 wherein, for all or a portion of the respective top-ranked documents in said initial group of ranked documents, a classification of the document is included with said respective set of ranked candidate terms associated with said document, wherein said classification comprises a first classification or a second classification.

4. The method of claim 3 wherein said selection function comprises:

determining, for each respective set of ranked candidate terms associated with a top-ranked document in said initial group of ranked documents, said classification of said associated top-ranked document; and

when a threshold percentage of said associated top-ranked documents evaluated in said determining belong to said first classification, all sets of candidate terms that are associated with a document belonging to said second classification are not used to form said subset of candidate terms.

5. The method of claim 2 wherein, for all or a portion of the top-ranked document in said initial group of ranked documents, a number of times a candidate term is identified by an instance of said comparing (A) is used by said ranking (C) to rank said candidate term in said set of ranked candidate terms.

6. The method of claim 5 wherein said ranking (C) further uses a first position of said candidate term in the respective associated document to rank said candidate term.

7. The method of claim 5, the identification further comprising:

(C) discarding a first candidate term when said first candidate term is a subset of a second candidate term in said respective set of candidate terms;

(D) crediting said second candidate term with a number of times said first candidate term was identified in said document associated with said respective set of ranked candidate terms by instances of said comparing (A); and

(E) repeating said discarding (C) and said crediting (D) until there is no first candidate term that is a subset of a second candidate term in said respective set of ranked candidate terms.

8. The method of claim 5, the identification further comprising:

(C) discarding a first candidate term when said first candidate term is an orthographic or inflectional variant of a second candidate term in said respective set of ranked candidate terms;

(D) crediting said second candidate term with a number of times said first candidate term as identified in said document associated with said respective set of ranked candidate terms by instance of said comparing (A); and

(E) repeating said discarding (C) and said crediting (D) until there is no first candidate term that is an orthographic or inflectional variant of a second candidate term in said respective set of ranked candidate terms.

9. The method of claim 8 wherein said crediting said second candidate term (D) further comprises:

rewriting said second candidate term as a combined term that includes said first candidate term and said second candidate term, wherein the one of said first candidate term or said second candidate term identified by an instance of said comparing (A) the most times appears at the beginning of said combined term.

10. The method of claim 9 wherein only the term appearing at the beginning of said combined term is used in said presenting.

11. The method of claim 2 wherein, for all or a portion of the top-ranked documents in said initial group of ranked documents, the respective set of ranked candidate terms associated with the document includes, for each candidate term in said respective set, a first position of said candidate term in said document.

12. The method of claim 2 wherein said identification further comprises:

(C) terminating said comparing (A) and terminating said repeating (B) when a threshold number of unique terms have been considered by said comparing (A).

13. The method of claim 2 wherein said master list of candidate terms is optimized for a specific language.

14. The method of claim 13 wherein said specific language is English, Spanish, French, German, Portuguese, Italian, Russian, Chinese, of Japanese.

15. The method off claim 13 wherein all of a portion of the top-ranked documents in said initial group off ranked documents are in the same language for which said master list off candidate terms is optimized.

16. The method off claim 2 wherein each term in said master list off candidate terms is a word of a phrase.

17. The method off claim 2 wherein said master list off candidate terms comprises more than 1,000,000 terms.

18. The method of claim 1 wherein each said respective set of ranked candidate terms is identified at a time prior to said processing said received query.

19. The method off claim 1, the method further comprising repeating said processing, selecting, and presenting using a revised query that includes said received query and a candidate term from said subset off candidate terms.

20. The method off claim 1 wherein said selection function comprises:

(i) applying a weighting function to each candidate term in each respective set ranked candidate terms that is associated with a top-ranked document in said initial group off ranked documents, wherein each top-ranked document in said initial group off ranked documents has a ranking that is numerically less than a threshold ranking; and

(ii) selecting, for said subset of candidate terms, those candidate terms receiving a highest weight.

21. The method of claim 20 wherein a weight that is applied to a candidate term by said weighting function is determined in accordance with a the number off sets off ranked candidate terms that both (i) include the candidate term and (ii) are respectively associated with a top-ranked document.

22. The method off claim 20 wherein a weight that is a applied to a candidate term by said weighting function is determined in accordance with the average position off the candidate term in those sets off ranked candidate terms that both (i) include the candidate term and (ii) are respectively associated with a top-ranked document.

23. The method off claim 20 wherein a weight that is a applied to a candidate term by said weighting function is determined in accordance with whether a term in said received query is in said candidate term.

24. The method off claim 20 wherein a weight that is applied to a candidate term by said weighting function is determined in accordance with a number of characters in said candidate term.

25. The method off claim 20 wherein a weight that is applied to a candidate term by said weighting function is determined in accordance with the average rank off those top-ranked documents that are associated with a set off ranked candidate terms that includes the candidate term.

26. The method off claim 20 wherein a weight that is a applied to a candidate term by said weighting function is determined in accordance with any combination of TermCount, TermPosition, ResultPosition, TermLength, and QueryInclusion, where TermCount is a number off sets off ranked candidate terms that both (i) include the candidate term and (ii) are respectively associated with a top-ranked document, TermPosition is a function of the rank position off the candidate term in those sets of ranked candidate terms that both (i) include the candidate term and (ii) are respectively associated with a top-ranked document, ResultPosition is a function off the rank off those top-ranked documents that are associated with a set off ranked candidate terms that includes the candidate term, TermLength is a number of characters in the candidate term (candidate term complexity), and QueryInclusion is a value that indicates whether a term in the received query is in the candidate term.

27. The method off claim 26 wherein a weight that is applied to a candidate term by said weighting function is determined in accordance with the formula:

TermCount+TermPosition+ResultPosition+TermLength+QueryInclusion.

28. The method off claim 27 wherein TermCount, TermPosition, ResultPosition, TermLength, and QueryInclusion are each independently weighted.

29. The method off claim 26, the method further comprising optionally repeating said processing, selecting, and presenting using a revised query that includes said received query and a candidate term from said subset of candidate terms.

30. The method of claim 29 wherein a weight that is applied to a candidate term by said weighting function is determined in accordance with the formula:

(TermCount*w₁)+(Term Position*(w₂+(RefinementDepth*w₂′

)))+(ResultPosition*w₃)+(TermLength*(w₄+(RefinementDepth*w₄′

)))+(QueryInclusion*(w₅+(RefinementDepth*w₅′

)))

where w₁, w₂, w₃, w₄, w₅, w₂′

, w₄′

, and w₅′

are independent weights and RefinementDepth is a number of times said processing has been performed for said received query.

31. A computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:

an query refinement suggestion engine for refining a received query, comprising;

instructions for processing said received query so as to generate an initial group of ranked documents corresponding to the received query, wherein each document in all of a portion of the documents in said initial group of ranked documents is associated with a respective set of precomputed ranked candidate terms such that each candidate term in said respective set of ranked candidate terms is embedded within said document;

instructions for selecting, in accordance with a selection function, a subset of candidate terms that are in one of more of said respective sets of candidate terms; and

instructions for presenting, in response to the received query, the initial group of ranked documents and said subset of candidate terms.

32. The computer program product of claim 31 wherein, for all of a portion of the top-ranked documents in said initial group of ranked documents, the respective set of ranked candidate terms associated with said document is identified by:

(A) instructions for comparing a term in said document to a master list of candidate terms, wherein, when said term is in said master list of candidate terms, said term is added to said respective set of ranked candidate terms associated with said document as a candidate term; and

(B) instructions for re-executing said instructions for comparing until a maximum number of terms in said document has been considered.

33. The computer program product of claim 32 wherein, for all of a portion of the top-ranked documents in said initial group of ranked documents, a classification of the candidate terms in the respective set of ranked candidate terms associated with said document is included within said respective set of ranked candidate terms associated with said document, wherein said classification comprises a first classification or a second classification.

34. The computer program product of claim 33 wherein said selection function comprises:

instructions for determining, for each respective set of ranked candidate terms associated with a top-ranked document in said initial group of ranked documents, said classification of said respective set of ranked candidate terms; and

when a threshold percentage of said sets of candidate terms evaluated in said determining belong to said first classification, all sets of candidate terms that belong to said second classification are not used to form said subset of candidate terms.

35. The computer program product of claim 32 wherein, for all or a portion of the top-ranked documents in said initial group of ranked documents, a number of times a candidate term is identified by an instance of said instructions for comparing (A) is included in said respective set of ranked candidate terms associated with said document.

36. The computer program product of claim 35 wherein said number of times said candidate term is identified by an instance of said instructions for comparing (A) is upweighted when said candidate term is identified within a first threshold number of words in said document.

37. The computer program product of claim 35, the identification further comprising:

(C) instructions for discarding a first candidate term when said first candidate term is a subset of a second candidate term in said respective set of ranked candidate terms;

(D) instructions for crediting said second candidate term with a number of times said first candidate term was identified in said document associated with said respective set of ranked candidate terms by instances of said comparing (A); and

(E) instructions for repeating said instructions for discarding (C) and said instructions for crediting (D) until there is no first candidate term that is a subset of a second candidate term in said respective set of ranked candidate terms.

38. The computer program product of claim 35, identification further comprising:

(C) instructions for discarding a first candidate term when said first candidate term is an orthographic of inflectional variant of a second candidate term in said respective set of ranked candidate terms;

(D) instructions for crediting said second candidate term with a number of times said first candidate term was identified in said document associated with said respective set of ranked candidate terms by an instance of said comparing (A); and

(E) instructions for repeating said instructions for discarding (C) and said instructions for crediting (D) until there is no first candidate term that is an orthographic of inflectional variant of a second candidate term in said respective set of ranked candidate terms.

41. The computer program product of claim 32 wherein, for all of a portion of the top-ranked documents in said initial group of ranked documents, the respective set of ranked candidate terms associated with the document includes, for each candidate term in said respective set, an average position of said candidate term in said document.

42. The computer program product of claim 41 wherein the average position of said candidate term in said document is determined in accordance with the averaging the position of each instance of the candidate term identified during an instance of said instructions for comparing (A).

43. The computer program product of claim 32 wherein said identification further comprises:

(C) instructions for terminating said instructions for comparing (A) and instructions for terminating said instructions for repeating (B) when a threshold number of unique terms have been considered by said instructions for comparing (A).

44. The compute program product of claim 32 wherein said master list of candidate terms is optimized for a specific language.

45. The computer program product of claim 44 wherein each document in all of a portion of the documents in said initial group of ranked documents are in the same language for which said master list of candidate terms is optimized.

46. The computer program product of claim 32 wherein each term in said master list of candidate terms is a word of a phrase.

47. The computer program product of claim 32 wherein each said respective set of ranked candidate terms is identified at a time prior to said processing said received query.

48. The computer program product of claim 31, wherein said query refinement suggestion engine further comprises instructions for repeating said instructions for processing, instructions for selecting, and instructions for presenting using a revised query that includes said received query and a candidate term from said subset of candidate terms.

49. The computer program product of claim 31 wherein said selection function comprises:

(i) instructions for applying a weighting function to each candidate term in each respective set of ranked candidate terms that is associated with a top-ranked document in said initial group of ranked documents, wherein each top-ranked document in said initial group of ranked documents has a ranking that is numerically less than a threshold ranking; and

(ii) instructions for selecting, for said subset of candidate terms, those candidate terms receiving a highest weight.

50. The computer program product of claim 49 wherein a weight that is applied to a candidate term by said weighting function is determined in accordance with a number of times said candidate term appears in an upper portion of top-rank document.

51. The computer program product of claim 49 wherein a weight that is applied to a candidate term by said weighting function is determined in accordance with a position of said candidate term in a top-ranked document in which said candidate term appears.

52. The computer program product of claim 49 wherein a weight that is applied to a candidate term by said weighting function is determined in accordance with whether a term in said received query is in said candidate term.

53. The computer program product of claim 49 wherein a weight that is applied to a candidate term by said weighting function is determined in accordance with a number of characters in said candidate term.

54. The computer program product of claim 49 wherein a weight that is applied to a candidate term by said weighting function is determined in accordance with a position of a document in said initial group of ranked documents that include said candidate term.

55. The computer program product of claim 49 wherein a weight that is applied to a candidate term by said weighting function is determined in accordance with any combination of TermCount, TermPosition, ResultPosition, TermLength, and QueryInclusion, where TermCount is a number of times said candidate term appears in an upper portion of each top-ranked document, TermPosition is a function of the position of said candidate term within each top-ranked document in which said candidate term appears, ResultPosition is a function of the position of documents in top-ranked documents, in the initial group of ranked documents, that include the candidate term, TermLength is a number of characters in said candidate term, and QueryInclusion not zero when a term in said received query is in said candidate term and QueryInclusion is zero when a term in said received query is not in said candidate term.

56. The computer program product of claim 55 wherein a weight that is applied to a candidate term by said weighting function is determined in accordance with the formula:

TermCount+TermPosition+ResultPosition+TermLength+QueryInclusion.

57. The computer program product of claim 56 wherein TermCount, TermPosition, ResultPosition, TermLength, and QueryInclusion are each independently weighted.

39. The computer program product 38 wherein said instructions for crediting said second candidate term (D) further comprise:

instructions for rewriting said second candidate term as a combined term that includes said first candidate term and said second candidate term, wherein the one of said first candidate term or said second candidate term identified by an instance of said instructions for comparing (A) the most times appears at the beginning of said combined term.

40. The computer program product of claim 39 wherein only the term appearing at the beginning of said combined term is used by said instruction for presenting.

58. A computer system for refining a received query, the computer system comprising:

a central processing unit;

a memory, coupled to the central processing unit, the memory storing an query refinement suggestion engine comprising;

instructions for processing said received query so as to generate an initial group of ranked documents corresponding to the received query, wherein each document in all or a portion of the documents in said initial group of ranked documents is associated with a respective set of precomputed ranked candidate terms such that each candidate term in said respective set of ranked candidate term is embedded within said document;

instructions for selecting, in accordance with a selection function, a subset of candidate terms that are in one or more of said respective sets of candidate terms; and

instructions for presenting, in response to the received query, the initial group of ranked documents and said subset of candidate terms.

59. The computer system claim 58 wherein, for all or a option of the top-ranked documents in said initial group of ranked documents, the respective set of ranked candidate terms associated with said document is identified by:

(A) instructions for comparing a term in said document to a master list of candidate terms, wherein, when said term is in said master list of candidate terms, said term is added to said respective set of ranked candidate terms associated with said document as a candidate term; and

(B) instructions for re-executing said instructions for comparing until a maximum number of terms in said document has been considered.

60. The computer system of claim 59 wherein, for all of a portion of the top-ranked documents in said initial group of ranked documents, a classification of the candidate terms in the respective set of ranked candidate terms associated with said document is included within said respective set of ranked candidate terms associated with said document, wherein said classification comprises a first classification of a second classification.

61. The computer system of claim 60 wherein said selection function comprises:

instructions for determining, for each respective set of ranked candidate terms associated with a document in said initial group of ranked documents, said classification of said respective set of ranked candidate terms; and

when a threshold percentage of said sets of candidate terms evaluated in said determining belong to said first classification, all sets of candidate terms that belong to said second classification are not used to form said subset of candidate terms.

62. The computer system of claim 59 wherein, for all of a portion of the top-ranked documents in said initial group of ranked documents, a number of times a candidate term is identified by an instance of said instructions for comparing (A) is included in said respective set of ranked candidate terms associated with said document.

63. The computer system of claim 62, the identification further comprising:

(C) instructions for discarding a first candidate term when said first candidate term is a subset of a second candidate term in said respective set of ranked candidate terms;

(D) instructions for crediting said second candidate term with a number of times said first candidate term was identified in said document associated with said respective set of ranked candidate terms by instances of said comparing (A); and

(E) instructions for repeating said instructions for discarding (C) and said instructions for crediting (D) until there is no first candidate term that is a subset of a second candidate term in said respective set of ranked candidate terms.

64. The computer system of claim 63 wherein said selection function comprises:

(i) instructions for applying a weighting function to each candidate term in each respective set of ranked candidate terms that is associated with a top-ranked document in said initial group of ranked documents, wherein each top-ranked document in said initial group of ranked documents has a ranking that is numerically less than a threshold ranking; and

(ii) instructions for selecting, for said subset of candidate terms, those candidate terms receiving a highest weight.

65. The computer system of claim 64 wherein a weight that is applied to a candidate term by said weighting function is determined in accordance with any combination of TermCount, TermPosition, ResultPosition, TermLength, and QueryInclusion, where TermCount is a number of times said candidate term appears in an upper portion of each top-ranked document, TermPosition is a function of the position of said candidate term within each top-ranked document in which said candidate term appears, ResultPosition is a function of the position of documents in top-ranked documents, in the initial group of ranked documents, that include the candidate term, TermLength is a number of characters in said candidate term, and QueryInclusion is applied when a term in said received query is in said candidate term and QueryInclusion is not applied when a term in said received query is not in said candidate term.

66. The computer system of claim 65 wherein a weight that is applied to a candidate term by said weighting function is determined in accordance with the formula:

TermCount+TermPosition+ResultPosition+TermLength+QueryInclusion.

67. The computer system of claim 66 wherein TermCount, TermPosition, ResultPosition, TermLength, and QueryInclusion are each independently weighted.

68. The computer system of claim 62, the identification further comprising:

(C) instructions for discarding a first candidate term when said first candidate term is an orthographic of inflectional variant of a second candidate term in said respective set of ranked candidate terms;

(D) instructions for crediting said second candidate term with a number of times said first candidate term was identified in said document associated with said respective set of ranked candidate terms by an instance of said comparing (A); and

(E) instructions for repeating said instructions for discarding (C) and said instructions for crediting (D) until there is no first candidate term that is an orthographic of inflectional variant of a second candidate term in said respective set of ranked candidate terms.

69. The computer system of claim 59 wherein, for all or a portion of the top-ranked documents in said initial group of ranked documents, the respective set of ranked candidate terms associated with the document includes, for each candidate term in said respective set, an average position of said candidate term in said document.

70. The computer system of claim 59 wherein said identification further comprises:

(C) instructions for terminating said instructions for comparing (A) and instructions for terminating said instructions for repeating (B) when a threshold number of unique terms have been considered by said instructions for comparing (A).

71. The computer system of claim 58, wherein said query refinement suggestion engine further comprises instructions for repeating said instructions for processing, instructions for selecting, and instructions for presenting using a revised query that includes said received query and a candidate term from said subset of candidate terms.

72. The computer system of claim 58, wherein each said respective set of ranked candidate terms is identified at a time prior to said processing said received query.

73. A document index data structure comprising a plurality of uniform resource locators (URLs), each URL designating a respective document;

wherein each document in all of a portion of the respective documents designated by said plurality of URLs is associated with a respective set of ranked candidate terms, wherein each candidate term in a respective set of ranked candidate terms comprises candidate terms that are embedded in the document associated with said set of ranked candidate terms.

74. The data structure of claim 73 wherein a respective set of ranked candidate terms is created by (A) comparing a term in the document associated with said respective set of ranked candidate terms to a master list of candidate terms, wherein, when said term is in said master list of candidate terms, said term is added to said respective set of ranked candidate terms as a candidate term;

and (B) repeating said comparing until a maximum number of terms in said document has been considered.

75. The data structure of claim 74 wherein each said respective set of ranked candidate terms includes a first classification of a second classification and wherein inclusion of said first classification of a second classification in said respective set of ranked candidate terms is determined in accordance with an identity of one or more candidate terms in said respective set of ranked candidate terms.