# US 2008/0306934 A1 · Using link structure for suggesting related queries

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2008/0306934 A1
- Document ID: US20080306934A1
- Status: Published application
- Kind: A1
- Application number: 11/761,038
- Filed: 2007-06-11
- Published: 2008-12-11
- Earliest claimed: 2007-06-11
- Assignees: Microsoft Corporation
- Inventors: NICHOLAS ERIC CRASWELL; HUGH EVAN WILLIAMS; ARIEL J. LAZIER
- Web page: https://patentgrep.com/patent/US20080306934A1

## CPC

- G06F 16/3322: {using system suggestions (G06F16/3325 takes precedence)}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

An approach is provided for determining related queries for a given search query based on the linking structure of electronic documents within a document set. Document titles are used to represent potential search queries and links between the electronic documents are used to determine relationships between the potential search queries. As such, the document set may be represented as a directed graph in which document titles (which represent potential search queries) are nodes and links are edges between the nodes. When a particular search query is received, a corresponding node is identified and related queries are determined by identifying other nodes having connections with that node.

## Claims

### Claim 1

One or more computer-readable media embodying computer-useable instructions for performing a method to generate information to facilitate suggesting related queries for a search query based on a linking structure among a plurality of electronic documents in a document set, the method comprising:
extracting document titles from the plurality of electronic documents, wherein each document title is identified as a potential related query;
extracting links among the plurality of documents;
generating a directed graph in which the document titles are nodes and the links are edges between the nodes; and
storing information associated with the directed graph to facilitate suggesting related queries for a search query.

### Claim 2 (depends on 1)

The one or more computer-readable media of claim 1, wherein the method further comprises receiving a search query and determining one or more related queries using the information associated with the directed graph.

### Claim 3 (depends on 2)

The one or more computer-readable media of claim 2, wherein determining one or more related queries using the information associated with the directed graph comprises identifying the search query as a first node in the directed graph and identifying the one or more related queries as additional nodes linked to the first node in the directed graph.

### Claim 4 (depends on 3)

The one or more computer-readable media of claim 3, wherein the one or more related queries are ranked based on connections between the first node and a node corresponding with each related query.

### Claim 5 (depends on 4)

The one or more computer-readable media of claim 4, wherein connections between nodes in the directed graph comprise different connection-types.

### Claim 6 (depends on 5)

The one or more computer-readable media of claim 5, wherein the one or more related queries are ranked by applying weightings to the different connection-types.

### Claim 7 (depends on 1)

The one or more computer-readable media of claim 1, wherein the method further comprises receiving a user selection of at least one of the related queries and providing search results based on the user selection.

### Claim 8 (depends on 1)

The one or more computer-readable media of claim 1, wherein the electronic documents comprise a high-quality document set from a trusted data source.

### Claim 9

A computerized method for providing related queries for a search query, the method comprising:
receiving the search query;
determining one or more related queries for the search query based on the linking structure of electronic documents within a document set, wherein titles of the electronic documents represent potential related queries; and
communicating at least a portion of the one or more related queries for presentation to an end user.

### Claim 10 (depends on 9)

The method of claim 9, wherein determining one or more related queries comprises analyzing a directed graph generated based on the linking structure between the electronic documents, wherein the titles of the electronic documents are nodes and links between the documents are edges between the nodes.

### Claim 11 (depends on 10)

The method of claim 10, wherein analyzing the directed graph comprises identifying a first node as corresponding with the search query and determining the one or more related queries by identifying one or more other nodes having a relationship with the first node.

### Claim 12 (depends on 9)

The method of claim 9, wherein communicating at least a portion of the one or more related queries comprises communicating the at least a portion of the one or more related queries with a first set of search results associated with the search query.

### Claim 13 (depends on 12)

The method of claim 12, wherein the method further comprises performing a search using at least one related query to obtain a second set of search results associated with the at least one related query.

### Claim 14 (depends on 13)

The method of claim 13, wherein communicating at least a portion of the one or more related queries for presentation to the end user comprises communicating at least a portion of the second set of search results for presentation to the end user.

### Claim 15 (depends on 13)

The method of claim 13, wherein performing the search using the at least one related query is in response to receiving a user selection of the at least one related query.

### Claim 16

A computerized system having one or more computer-readable media comprising software components for generating a directed graph based on the linking structure of a plurality of electronic documents in a document set to facilitate identification of related queries for search queries, the system comprising
an extraction component that scans the plurality of electronic documents within the document set to extract document titles and links among the plurality of documents, wherein each document title is identified as a potential related query; and
a graph generating component that generates the directed graph in which the document titles are nodes within the directed graph and the links are edges between the nodes.

### Claim 17 (depends on 16)

The system of claim 16, further comprising a suggestion component that determines one or more related queries for a given search query using information associated with the directed graph.

### Claim 18 (depends on 16)

The system of claim 16, wherein the suggestion component determines related queries by identifying a first node in the directed graph corresponding with the search query and one or more other nodes having connections with the first node.

### Claim 19 (depends on 16)

The system of claim 16, wherein the suggestion component ranks the one or more related queries based on the connections between the first node and the one or more other nodes.

### Claim 20 (depends on 20)

The system of claim 20, wherein the system further comprises a search engine component that performs a search using at least one of the search query and one of the related queries.
