Constructing a graph that facilitates provision of exploratory suggestions

Patent metadata

Field	Value
Publication number	US-10290125-B2
Application number	US-201414322258-A
Country	US
Kind code	B2
Filing date	Jul 2, 2014
Priority date	Jul 2, 2014
Publication date	May 14, 2019
Grant date	May 14, 2019

Abstract

Various technologies pertaining to exploratory suggestions are described herein. A computer-implemented graph is constructed, where the graph includes nodes that are representative of aspects and edges that are representative of associations between aspects. An aspect is representative of a sub-topic of a topic or a sub-task of a task. The computer-implemented graph is learned based upon content of search logs, and is used to output exploratory suggestions, where a user is exploring a topic or attempting to complete a multi-step task.

First claim

What is claimed is:

1. A computing system, comprising:
a processor; and
memory that comprises instructions that, when executed by the processor, cause the processor to perform acts comprising:
constructing a computer-implemented graph based upon search logs of a search engine, the computer-implemented graph comprises:
a first node that is representative of a first sub-task of a task that includes multiple sub-tasks that collectively make up the task, the first node comprises a first plurality of queries that define the first sub-task, wherein a first query is included in the first plurality of queries;
a second node that is representative of a second sub-task of the task, the second node comprises a second plurality of queries that defines the second sub-task that is represented by the second node, wherein a second query is included in the second plurality of queries, and further wherein completion of the task includes completion of the first sub-task and the second sub-task; and
a weighted edge that connects the first node and the second node, a weight assigned to the weighted edge is indicative of a likelihood that a searcher will transition from the first sub-task represented by the first node to the second sub-task represented by the second node when completing the task;

subsequent to constructing the computer-implement graph, receiving the first query from a client computing device;
identifying that the first node includes the first query based upon a search over the computer-implemented graph for the first query;
responsive to identifying that the first node includes the first query, selecting the second node based upon the weight assigned to the edge that connects the first node and the second node; and
transmitting the second query to the client computing device as a suggested query responsive to selecting the second node.

2. The computing system of claim 1 , wherein constructing the computer-implemented graph comprises:
identifying exploratory search sessions in the search logs, the exploratory search sessions being search sessions where searchers are completing tasks that include sub-tasks, wherein the computer-implemented graph is constructed based upon the identified exploratory search sessions.

3. The computing system of claim 1 , wherein constructing the computer-implemented graph comprises:
identifying entities in queries of the search logs, wherein the computer-implemented graph is constructed based upon the identified entities.

4. The computing system of claim 1 , wherein constructing the computer-implemented graph comprises:
identifying term collocations in queries in the search logs, a term collocation being a sequence of terms that occur more often than would be expected by chance, wherein the computer-implemented graph is constructed based upon the identified term collocations.

5. The computing system of claim 1 , wherein constructing the computer-implemented graph comprises:
identifying prepositions in queries in the search logs, wherein the computer-implemented graph is constructed based upon the identified prepositions.

6. The computing system of claim 1 , wherein constructing the computer-implemented graph comprises:
identifying term patterns in queries in the search logs, wherein the computer-implemented graph is constructed based upon the identified term patterns.

7. The computing system of claim 1 , wherein constructing the computer-implemented graph comprises:
grouping queries in the search logs into a plurality of query groups, each query group defines a respective sub-task.

8. The computing system of claim 1 , wherein constructing the computer-implemented graph comprises:
computing weights to assign to edges in the graph based upon the search logs, wherein the computer-implemented graph is constructed based upon the weights.

9. The computing system of claim 1 , wherein the second query is transmitted to the client computing device due to the second query being a most frequently issued query in the second plurality of queries.

10. A method executed by a processor of a computing device, the method comprising:
receiving a first query from a client computing device that is in network communication with the computing device;
responsive to receiving the first query, conducting a search for the first query over a computer-implemented graph, wherein the computer-implemented graph is constructed based upon search logs of a search engine, and further wherein the computer-implemented graph comprises:
a first node that is representative of a first sub-task of a task that includes multiple sub-tasks that collectively make up the task, the first node comprises a first plurality of queries that includes the first query, wherein the first plurality of queries defines the first sub-task of the task;
a second node that is representative of a second sub-task of the task, the second node comprises a second plurality of queries that includes a second query, wherein the second plurality of queries define the second sub-task of the task, wherein completion of the task includes completion of the first sub-task and completion of the second sub-task; and
an edge that connects the first node with the second node, wherein the edge is assigned a weight that is representative of a likelihood that a searcher will transition from completing the first sub-task to completing the second sub-task;

identifying that the first node includes the first query received from the client computing device based upon the search for the first query;
responsive to identifying the first node, selecting the second node based upon the weight assigned to the edge that connects the first node with the second node; and
responsive to selecting the second node, returning the second query to the client computing device as a suggested query.

11. The method of claim 10 , further comprising:
constructing the computer-implemented graph, wherein constructing the computer-implemented graph comprises identifying exploratory search sessions in the search logs, and further wherein identifying the exploratory search sessions comprises:
identifying a search session with at least a predefined threshold number of queries therein; and
identifying the exploratory search session based upon identifying the search sessions with the at least the predefined threshold number of queries therein, wherein the exploratory search session comprises the first query and the second query.

12. The method of claim 11 , wherein constructing the computer-implemented graph comprises:
identifying a pivot in the first query in the exploratory search session, the pivot being an entity or a term collocation, the term collocation being a sequence of terms that occur more often than would be expected by chance;
identifying a refiner in the first query, the refiner characterizing the pivot; and
indicating that the first query is to at least partially define the first sub-task based upon the pivot and the refiner.

13. The method of claim 12 , wherein constructing the computer-implemented graph further comprises:
assigning lexical tags to elements in the first query;
comparing the lexical tags to a predefined pattern; and
identifying the pivot and the refiner based upon the comparing of the lexical tags to the predefined pattern.

14. The method of claim 11 , wherein constructing the computer-implemented graph comprises clustering queries in exploratory search sessions, wherein a first cluster comprises the first plurality of queries and a second cluster comprises the second plurality of queries.

15. The method of claim 10 , further com

Assignees

• Microsoft Corp
• Microsoft Technology Licensing Llc

Inventors

• Awadallah Ahmed Hassan
• White Ryen
• Pantel Patrick
• Dumais Susan
• Wang Yi-Min

Classifications

• G06T11/26 Primary

  Drawing of charts or graphs · CPC title

• G06T11/206 Primary

  Physics · mapped topic

• G06F17/3064

  Physics · mapped topic

• G06F16/3322 Primary

  using system suggestions (G06F16/3325 takes precedence) · CPC title