# US 8,280,918 B2 · 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 8,280,918 B2
- Document ID: US8280918B2
- Status: Granted
- Kind: B2
- Application number: 12/890,086
- Filed: 2010-09-24
- Published: 2011-01-20
- Granted: 2012-10-02
- Earliest claimed: 2007-06-11
- Assignees: Microsoft Corporation
- Inventors: Nicholas Eric Craswell; Hugh Evan Williams; Ariel J. Lazier
- Web page: https://patentgrep.com/patent/US8280918B2

## 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 storing computer-useable instructions that, when used by a computing device, cause the computing device to perform a method to generate information to facilitate suggesting related queries for search queries 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 the plurality of documents are in the document set, the document set having a linking structure between the plurality of documents;
identifying each document title of the plurality of electronic documents, the title of each document designated as a potential search query;
extracting links among the plurality of electronic documents; and
storing information regarding the document titles and the links extracted from the plurality of electronic documents to facilitate suggesting related queries for search queries.

### Claim 2 (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 3 (depends on 2)

The one or more computer-readable media of claim 2, wherein the high-quality document set comprises an electronic encyclopedia document set, and wherein each electronic document contains information on a given subject and includes a title for that given subject.

### Claim 4 (depends on 2)

The one or more computer-readable media of claim 2, wherein the high-quality document set comprises a collection of product pages from a product shopping site, and wherein each electronic document contains information on a given product and includes a title for that given product.

### Claim 5 (depends on 1)

The one or more computer-readable media of claim 1, wherein extracting links among the plurality of electronic documents comprises identifying each link as one of a plurality of link types, and wherein storing information regarding the document titles and the links to facilitate suggesting related queries for search queries comprises storing information regarding link type for links.

### Claim 6 (depends on 5)

The one or more computer-readable media of claim 5, wherein the plurality of link types include a direct link type and an indirect link type.

### Claim 7 (depends on 1)

The one or more computer-readable media of claim 1, wherein at least a portion of the links among the plurality of electronic documents comprise explicit links between electronic documents.

### Claim 8 (depends on 7)

The one or more computer-readable media of claim 7, wherein the explicit links comprise hyperlinks in text of electronic documents linking to other electronic documents within the plurality of electronic documents.

### Claim 9 (depends on 1)

The one or more computer-readable media of claim 1, wherein at least a portion of the links among the plurality of electronic documents comprise implicit links between electronic documents inferred based on document content.

### Claim 10 (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 regarding the document titles and the links.

### Claim 11 (depends on 10)

The one or more computer-readable media of claim 10, 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 12 (depends on 10)

The one or more computer-readable media of claim 10, wherein the links among the plurality of electronic documents comprise different connection-types and wherein the one or more related queries are ranked by applying weightings to the different connection-types.

### Claim 13

A method for generating information to facilitate suggesting related queries for search queries based on a linking structure among a plurality of electronic documents in a document set, the method comprising:
identifying document titles from the plurality of electronic documents, wherein the plurality of documents are in the document set having a linking structure between the plurality of documents;
identifying each document title of the plurality of electronic documents, the title of each document designated as a potential search query;
identifying links among the plurality of electronic documents, wherein at least a portion of the links among the plurality of electronic documents comprise explicit links between electronic documents; and
storing information regarding the document titles and the links in a data structure that identifies connections between document titles based on links between electronic documents, wherein each document title represents a designated potential related query that may be returned in response to a search query.

### Claim 14 (depends on 13)

The method of claim 13, wherein the electronic documents comprise a high-quality document set from a trusted data source.

### Claim 15 (depends on 14)

The method of claim 14, wherein the high-quality document set comprises an electronic encyclopedia document set, and wherein each electronic document contains information on a given subject and includes a title for that given subject.

### Claim 16 (depends on 14)

The method of claim 14, wherein the high-quality document set comprises a collection of product pages from a product shopping site, and wherein each electronic document contains information on a given product and includes a title for that given product.

### Claim 17 (depends on 13)

The method of claim 13, wherein at least a portion of the links among the plurality of electronic documents comprise explicit links between electronic documents.

### Claim 18 (depends on 17)

The method of claim 17, wherein the explicit links comprise hyperlinks in text of electronic documents linking to other electronic documents within the plurality of electronic documents.

### Claim 19 (depends on 13)

The method of claim 13, wherein at least a portion of the links among the plurality of electronic documents comprise implicit links between electronic documents inferred based on document content.

### Claim 20

A computerized system having one or more computer-readable media comprising software components for extracting information 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, identifies each document title in the plurality of electronic documents, each title designated as a potential related query, and stores information regarding the document titles and the links to facilitate suggesting related queries for search queries, wherein the document titles represent potential related queries and linking between the electronic documents represent relationships among the potential related queries.
