Context-Aware Query Suggestion By Mining Log Data

• US 20100211588A1
• Filed: 02/13/2009
• Published: 08/19/2010
• Est. Priority Date: 02/13/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Li, Hang, Jiang, Daxin
• Granted Patent: US 9,330,165 B2
• Time in Patent Office: Days
• US Class Current: 707/768
• 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 by analyzing a sequence of previous queries;

mining historical search data to generate groups of query suggestion candidates;

matching the current query with the groups of query suggestion candidates to find a matching query suggestion candidate using the context of the current query; and

providing the matching query suggestion candidate.

2. The method of claim 1, wherein said mining historical data comprises:

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

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

wherein said mining historical search data to generate groups of query suggestion candidates comprises 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 a concept data structure 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 4, wherein said matching the current query with the groups of query suggestion candidates to find the matching query suggestion candidate comprises using the context of the current query to match a node in the concept data structure that corresponds to the current query.

8. The method of claim 1, wherein said calculating the context of the current query and said mining the historical search data are performed off-line;

and

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

9. The method of claim 1, 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.

10. The method of claim 1, 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.

11. A method comprising:

mining one or more search logs to create a concept data structure, wherein each element in the concept data structure corresponds to one or more query suggestions;

receiving a sequence of input queries including a current query;

calculating context of the current query by analyzing the sequence of input queries; and

matching the current query to elements in the concept data structure to generate one or more matching query suggestions using the context of the current query.

12. The method of claim 11, 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.

13. The method of claim 12, 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.

14. The method of claim 12, 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.

15. The method 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.

16. A computer accessible memory medium which stores program instructions executable by a processor to perform:

receiving a sequence of input queries including a current query;

mining one or more search logs to generate one or more concepts;

calculating context of a current query by analyzing the sequence of input queries using the one or more concepts;

building a concept data structure, wherein each element in the concept data structure corresponds to one or more query suggestions; and

using the context of the current query, matching the current query to elements in the concept data structure to generate one or more matching query suggestions.

17. The computer accessible memory medium of claim 16, wherein the program instructions are further executable by a processor to perform:

providing the one or more matching query suggestions.

18. The computer accessible memory medium of claim 16, wherein each of the one or more search logs comprises a plurality of queries and a plurality of URLs, and wherein said 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.

19. The computer accessible memory medium of claim 18, wherein said building the concept data structure comprises:

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

creating 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.

20. The computer accessible memory medium of claim 18, 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.