Context-aware query suggestion by mining log data

• US 9,330,165 B2
• Filed: 02/13/2009
• Issued: 05/03/2016
• Est. Priority Date: 02/13/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Jiang, Daxin, Li, Hang
• Primary Examiner(s): Beausoliel, Jr., Robert
• Assistant Examiner(s): Khakhar, Nirav K
• Application Number:
  US12/371,296
• Publication Number:
  US 20100211588A1
• Time in Patent Office: 2,636 Days
• Field of Search: 707/759, 707/767, 707/768, 707/769, 707/771, 707/776, 707/778, 707/751
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2425 Iterative querying; Query formulation based on the results of a preceding query
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/332 Query formulation
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/3325 Reformulation based on results of preceding query
• CPC Class Codes: G06F 16/3349 Reuse of stored results of previous queries
• CPC Class Codes: G06F 16/90324 using system suggestions

Abstract

Techniques described herein describe a context-aware query suggestion process. Context of a current query may be calculated by analyzing a sequence of previous queries. Historical search data may be mined to generate groups of query suggestion candidates. Using the context of the current query, the current query may be matched with the groups of query suggestion candidates to find a matching query suggestion candidate, which may be provided to the user.

Claims

1. A method comprising:

calculating context of a current query, the context of the current query comprising a sequence of input queries including the current query;

matching the current query with a group of query suggestion candidates to find one or more matching query suggestion candidates based at least in part on the context of the current query, the matching comprises;

matching the sequence of input queries to a sequence of concepts;

matching the sequence of concepts to one or more elements in a concept sequence tree wherein the matching the sequence of concepts comprises;

traversing the concept sequence tree from one level to another level based at least in part on the different consecutive concepts of the sequence of concepts; and

obtaining the one or more catching query suggestion candidates from a node of the concept sequence tree, the node comprising the last matchable concept of the sequence of concepts; and

providing the one or more matching query suggestion candidates.

2. The method of claim 1, further comprising mining historical data to generate groups of query suggestion candidates, wherein mining the historical data comprises:

finding one or more concepts associated with a plurality of queries in the historical search data;

finding one or more frequent contexts in the historical search data; and

generating the groups of query suggestion candidates using the one or more concepts and the frequent contexts.

3. The method of claim 2, wherein the historical search data comprises a plurality of subsequences of sessions, wherein said finding the one or more frequent contexts in the historical search data comprises enumerating the plurality of the subsequences of sessions.

4. The method of claim 2, wherein the historical search data comprises historical data including a plurality of queries and a plurality of Uniform Resource Locators (URLs), and wherein said finding the one or more concepts comprises:

relating each of the plurality of queries to one or more URLs of the plurality of URLs to generate relationships between the one or more queries and the one or more URLs; and

creating the one or more concepts from the relationships between the one or more queries and the one or more URLs.

5. The method of claim 4, further comprising:

creating the concept sequence tree from the one or more frequent contexts and the one or more concept sequences.

6. The method of claim 4, wherein said relating one or more queries to one or more URLs comprises creating a bipartite graph, wherein a first set of elements in the bipartite graph comprises the one or more queries, wherein a second set of elements in the bipartite graph comprises the one or more URLs, wherein each of the first set of elements is related to one or more elements of the second set of elements in the bipartite graph.

7. The method of claim 1, wherein calculating the context of the current query is performed off-line;

and wherein matching the current query and providing the matching query suggestion candidate are performed on-line.

8. The method of claim 1, further comprising mining historical search data to generate groups of query suggestion candidates, wherein the historical search data comprises historical data including a plurality of queries and a plurality of Uniform Resource Locators (URLs) for a plurality of users.

9. The method of claim 1, further comprising mining historical search data to generate groups of query suggestion candidates, wherein the historical search data comprises historical data including a plurality of queries and a plurality of Uniform Resource Locators (URLs) only for a user providing the current query.

10. A system comprising:

one or more processors; and

memory storing instructions that, when executed by the one or more processors, configure the one or more processors to perform operations comprising;

receiving a sequence of input queries including a current query;

mapping the sequence of input queries to a sequence of concepts, each concept comprising a cluster of queries and an input query of the sequence of input queries being converted to at most one concept of the sequence of concepts, wherein;

when no click-through information is available for a particular input query, mapping the sequence of input queries to the sequence of concepts stops at the particular input query and the sequence of concepts corresponds to one or more input queries of the sequence of input queries that have been mapped prior to the particular input query; and

matching the sequence of concepts to an element in a concept data structure to obtain one or more matching query suggestions, each element of the concept data structure corresponding to a particular sequence of concepts and associated with a particular set of query suggestions.

11. The system of claim 10, the operations further comprising mining one or more search logs to create the concept data structure, wherein the one or more search logs comprise historical data relating each of a plurality of queries to one or more Uniform Resource Locators (URLs), and wherein said mining the one or more search logs comprises:

relating one or more queries of the plurality of queries to one or more URLs of the plurality of URLs to generate relationships between the one or more queries and the one or more URLs; and

creating one or more concepts from the relationships between the one or more queries and the one or more URLs.

12. The system of claim 11, wherein said mining the one or more search logs to create the concept data structure comprises:

finding one or more query sessions associated with the plurality of queries in the one or more search logs; and

generating the concept data structure from the one or more query sessions and the one or more concepts, wherein each node in the concept data structure corresponds to one or more query suggestions.

13. The system of claim 11, wherein the relationships between the one or more queries and the one or more URLs comprise a bipartite data graph, wherein a first set of elements in the bipartite graph comprises the one or more queries, wherein a second set of elements in the bipartite graph comprises the one or more URLs, wherein each of the first set of elements is related to one or more elements of the second set of elements in the bipartite graph.

14. The system of claim 11, wherein said mining the one or more search logs is performed off-line and wherein said matching the current query is performed on-line.

15. A system comprising:

one or more processors;

memory storing instructions executable by the one or more processors, cause the one or more processors to perform acts comprising;

receiving a sequence of input queries including a current query;

mapping the sequence of input queries to a sequence of concepts, each concept of the sequence of concepts comprising a cluster of queries and an input query of the sequence of input queries being configured to map to at most one concept of the sequence of concepts; and

matching the sequence of concepts to one or more elements in a concept sequence tree to generate one or more matching query suggestions, wherein matching the sequence of concepts comprises;

traversing the concept sequence tree from one level to another level based at least in part on different and consecutive concepts of the sequence of concepts; and

obtaining the one or more matching query suggestions from a node of the concept sequence tree, the node comprising the last matchable concept of the sequence of concepts.

16. The system of claim 15, wherein the acts further comprise providing the one or more matching query suggestions.

17. The system of claim 15, wherein the acts further comprise mining one or more search logs to generate one or more concepts, each of the one or more search logs comprising a plurality of queries and a plurality of URLs, wherein mining the one or more search logs to generate the one or more concepts comprises:

relating one or more queries of the plurality of queries to one or more URLs of the plurality of URLs to generate relationships between the one or more queries and the one or more URLs; and

creating the one or more concepts from the relationships between the one or more queries and the one or more URLs.

18. The system of claim 17, wherein the acts further comprises building the concept sequence tree, and the building comprises:

finding one or more query sessions from the one or more search logs; and

creating the concept sequence tree from the one or more query sessions and the one or more concepts.