Segmentation of search topics in query logs

• US 8,478,737 B2
• Filed: 12/10/2010
• Issued: 07/02/2013
• Est. Priority Date: 12/14/2007
• Status: Expired due to Fees

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Klinkner, Kristina Lisa, Jones, Rosie
• Primary Examiner(s): Lee, Wilson
• Application Number:
  US12/965,396
• Publication Number:
  US 20110078147A1
• Time in Patent Office: 935 Days
• Field of Search: None
• US Class Current: 707/713
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

A system identifies the tasks that a user is attempting to perform when submitting a series of search queries. A task may be categorized hierarchically into a mission and a goal in order to classify a series of queries and determine the user'"'"'s intent. The user'"'"'s mission may be an extended task and the user'"'"'s goal may be a specific task. A pair of queries may be analyzed to determine whether those queries have the same mission and/or the same goal. For a series of queries, boundaries may be identified between the queries to identify where a user has changed her goal or changed her mission. The identification of goals, missions and boundaries may be automated based on an analysis of features of the queries that are compared.

Claims

1. A system for segmenting a session of queries comprising:

a search log database operative to store search queries; and

a segmenter coupled with the search log database, the segmenter further including;

a receiver operative to receive a pair of queries from the search log database;

a feature analyzer coupled with the receiver and operative to compare the pair of queries based on at least one feature; and

an identifier coupled with the feature analyzer and operative to identify a goal boundary between the pair of queries when the at least one feature of the pair of queries indicates a change between the pair of queries;

wherein the receiver is further operative to receive additional successive pairs of the stored search queries for identifying goal boundaries in the session of queries.

2. The system according to claim 1 further comprising a search engine coupled with the search log database and the segmenter and operative to receive a user query, wherein the user query is stored in the search log database.

3. The system according to claim 1 wherein the goal boundary establishes a segment of queries with a similar goal.

4. The system according to claim 3 wherein the change indicates that a successive pair of queries have different goals.

5. The system according to claim 1 wherein the identifier is further operative to identify a mission boundary between the pair of queries when the at least one feature of the pair of queries indicates a change between the pair of queries, wherein the mission boundary establishes a segment of successive queries with a similar mission.

6. The system according to claim 5 wherein a goal is a subset of a mission in hierarchical classification of user intent, wherein the mission is a first level of intent and the goal is a second level of intent.

7. The system according to claim 1 wherein the change comprises a difference in the at least one feature between the successive pair.

8. The system according to claim 1 wherein the at least one feature comprises an edit distance comparison between the one of the successive pairs.

9. The system according to claim 8 wherein the change comprises a high value for a normalized value of the edit distance.

10. The system according to claim 8 wherein the edit feature comprises a Levenshtein edit distance.

11. The system according to claim 10 wherein the goal boundary is identified between successive queries when a normalized value of the Levenshtein edit distance is above a threshold value.

12. The system according to claim 1 wherein the at least one feature comprises at least one of a temporal feature, a character prefix overlap, a word prefix overlap, a common words feature, a ratio of common words feature, a log likelihood ratio score, a probability that a query is the last query, a vector similarity, or a number of unique domains.

13. A system for segmenting a session of queries comprising:

a search log database operative to store search queries; and

a segmenter coupled with the search log database, the segmenter further including;

a receiver operative to receive a pair of queries from the search log database;

a feature analyzer coupled with the receiver and operative to compare the pair of queries based on at least one feature; and

an identifier coupled with the feature analyzer and operative to identify a goal boundary between the pair of queries when the at least one feature of the pair of queries indicates a change between the pair of queries, wherein the identifier is further operative to identify a mission boundary between the pair of queries when the at least one feature of the pair of queries indicates a change between the pair of queries, wherein the mission boundary establishes a segment of successive queries with a similar mission.

14. The system according to claim 13 wherein a goal is a subset of a mission in hierarchical classification of user intent, wherein the mission is a first level of intent and the goal is a second level of intent.

15. The system according to claim 14 wherein the goal and the mission are hierarchical categories of the task, and further wherein the mission is a broad task and the goal is a specific task.