Speeding up analysis of compressed web graphs
AssigneeMicrosoft Corporation
InventorsReid Andersen, Kumar Chellapilla, Chinmay Karande
Life of this patent
Estimating the term…
Abstract
Classes of web graph algorithms are extended to run directly on virtual node-type compressed web graphs where a reduction in runtime of the extended algorithms is realized which is approximately proportional to the compression ratio applied to the original (i.e., uncompressed) graph. In the virtual node compression technique, a succinct representation of a web graph is constructed by replacing dense subgraphs by sparse ones so that the resulting compressed graph has significantly fewer edges and a relatively small number of additional nodes.
Claims20
One or more computer-readable media containing instructions which, when executed by one or more processors disposed in an electronic device, perform a method for speeding tip execution of a web graph algorithm, the method comprising the steps of:
- retrieving a compressed representation of a web graph, the compressed representation including real nodes and virtual nodes and having an unique adjacency matrix;
- and
- performing multiplication of a vector with the adjacency matrix of the compressed representation.
One or more computer-readable media containing instructions which, when executed by one or more processors disposed in an electronic device, perform a method for speeding up execution of a web graph algorithm, the method comprising the steps of:
- retrieving a compressed representation of a web graph, the compressed representation including real nodes and virtual nodes;
- extending the web graph algorithm through modification of Markov chain transition probabilities;
- running the extended algorithm directly on the compressed representation;
- and
- applying a transformation to a result of the extended algorithm to obtain a stationary vector for the web graph.
A machine-implemented method for providing a web graph service, the method comprising the-steps of:
- generating a virtual node compressed web graph by applying a bipartite clique-star transformation to an original web graph in which compression depth is bounded by a relatively small constant;
- extending one or more classes of link-based ranking algorithms for running directly on the virtual node compressed graph without decompression;
- running an extended algorithm on the virtual node compressed graph by performing power method iterations until convergence;
- and
- using results of the extended algorithm to perform web page rankings.
Dependencies are inferred from the claim text.