Short paths in web graphs with small query time
AssigneeMicrosoft Corporation
InventorsReid Andersen, Kumar Chellapilla, Chinmay Karande
Life of this patent
Estimating the term…
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.
Claims20
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.
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.
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.
Dependencies are inferred from the claim text.