# US 2010/0306216 A1 · Short paths in web graphs with small query time

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

- Number: US 2010/0306216 A1
- Document ID: US20100306216A1
- Status: Published application
- Kind: A1
- Application number: 12/473,706
- Filed: 2009-05-28
- Published: 2010-12-02
- Earliest claimed: 2009-05-28
- Assignees: Microsoft Corporation
- Inventors: Reid Andersen; Kumar Chellapilla; Chinmay Karande
- Web page: https://patentgrep.com/patent/US20100306216A1

## CPC

- G06F 16/95: Retrieval from the web
- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Short paths are found with a small query time in scale-free directed graphs using a two-phase process by which data structures comprising shortest path trees are first pre-computed for a group of central vertices called “hubs” that have short paths to most other vertices in the graph. In a query time phase, a short path between two vertices of interest in the graph is found by looking up the path to the root in each of the shortest path trees.

## Claims

### Claim 1

One or more computer-readable storage media containing instructions which, when executed by one or more processors disposed in an electronic device, perform a method for computing short paths in a scale-free directed graph, the method comprising the steps of:
identifying one or more hubs in the graph, the hubs being high-degree vertices;
pre-computing data structures for each of the one of more hubs, each of the pre-computed data structures comprising an in-tree and an out-tree, the in-tree including shortest paths directed from vertices in the graph to a given hub, the out-tree including shortest paths directed from the given hub to vertices in the graph, the pre-computing being performed prior to processing of a path query on the graph; and
storing the pre-computed data structures.

### Claim 2 (depends on 1)

The one or more computer-readable storage media of claim 1 in which the method includes a further step of making the pre-computed data structures accessible during the processing of the path query.

### Claim 3 (depends on 1)

The one or more computer-readable storage media of claim 1 in which the identifying comprises performing a PageRank algorithm on vertices and edges in the graph or analyzing the vertices' degree.

### Claim 4 (depends on 1)

The one or more computer-readable storage media of claim 1 in which the graphs defined by G=(V,E) in which V is a set of vertices and E is a set of directed edges between the vertices and the storing is implemented using only O(|V|) memory.

### Claim 5 (depends on 1)

The one or more computer-readable storage media of claim 1 including a further step of utilizing the pre-computed data structures to return a short path in response to the path query in approximately constant time.

### Claim 6 (depends on 5)

The one or more computer-readable storage media of claim 5 in which the utilizing comprises finding a short path between two vertices specified in the path query by looking up a path to a hub in each of the pre-computed data structures.

### Claim 7 (depends on 1)

The one or more computer-readable storage media of claim 1 in which the scale-free directed graph is associated with one of World Wide Web, social network, or communications network.

### Claim 8

One or more computer-readable storage media containing instructions which, when executed by one or more processors disposed in an electronic device, perform a method for executing a path query on a scale-free directed graph G=(V,E) in which V is a set of vertices and E is a set of directed edges between the vertices, the method comprising the steps of:
receiving a path query specifying vertices u and v that define a short path search;
accessing a set of data structures, each of the data structures representing a shortest path tree including an in-tree and an out-tree that is associated with respective hubs in the graph, the hubs being identified as having short paths to most of the other vertices in the graph;
looking up a shortest path from u to a hub in each in-tree in which u appears and generating a set of trail vertices that are located on a path from u to the hub;
looking up a shortest path from the hub to v in each out-tree in which v appears and generating a set of trail vertices that are located on a path from the hub to v;
locating an intersecting vertex x that is common between the set of trail vertices for u and the set of trail vertices for v; and
combining a path from u to x and a path from x to v to generate a short path from u to v.

### Claim 9 (depends on 8)

The one or more computer-readable media of claim 8 in which the method includes a further step of computing lengths of all short paths from u to v that are associated with all the shortest path trees in which u and v appear.

### Claim 10 (depends on 9)

The one or more computer-readable media of claim 9 in which the method includes a further step of outputting a shortest path from among the computed lengths of all the short paths.

### Claim 11 (depends on 8)

The one or more computer-readable media of claim 8 in which the data structures are pre-computed in advance of the step of accessing.

### Claim 12 (depends on 8)

The one or more computer-readable media of claim 8 in which the hubs are each associated with shortest path trees having relatively small depth.

### Claim 13 (depends on 8)

The one or more computer-readable media of claim 8 in which the short path from u to v is generated by only accessing the set of data structures but not the entire graph G.

### Claim 14

A machine-implemented method for providing a web graph service, the method comprising the steps of:
pre-computing short path trees for each of a selected group of central vertices within a scale-free directed graph, each of the central vertices being a root of respective pre-computed short path trees and having a relatively high degree compared with an average degree for other vertices in the graph;
receiving a path query comprising vertices u and v between which a short path is calculable;
performing lookups on the pre-computed short path trees to identify a path from u to a root and a path from the root to v; and
generating a short path from u to v using the identified paths.

### Claim 15 (depends on 14)

The machine-implemented method of claim 14 in which the generating comprises finding a common vertex of intersection x between the path from u to the root and the path from the root to v and combining a path from u to x with a path from x to v.

### Claim 16 (depends on 14)

The machine-implemented method of claim 14 including a further step of generating an upper bound on an exact shortest path from u to v if the generated short path is not the exact shortest path.

### Claim 17 (depends on 16)

The machine-implemented method of claim 16 including a further step of performing a secondary path finding technique in the neighborhood of the short path in order to find the exact shortest path.

### Claim 18 (depends on 15)

The machine-implemented method of claim 15 in which the pre-computed short path trees comprise an in-tree and an out-tree, the in-tree including shortest paths directed from vertices in the graph to a given root, the out-tree including shortest paths directed from the given root to vertices in the graph.

### Claim 19 (depends on 14)

The machine-implemented method of claim 14 including a further step of iterating the generating step for each of the pre-computed short path trees in which u and v appear.

### Claim 20 (depends on 19)

The machine-implemented method of claim 19 including the further steps of computing a length of each combined path resulting from the iterating step, and outputting a shortest computed path.
