I/O efficient computation of First Order Markov Measures for Large and Evolving Graphs

Live blogging from WebKDD 08:
I/O efficient computation of First Order Markov Measures for Large and Evolving Graphs
Prasanna K Desikan and Jaideep Srivastava

This paper addresses

• Disk IO for single iteration
• Num of iterations to converge

in pagerank computation.

Typical method is to do binning of the vectors so that the vectors are accessed as blocks in the graph. This requires more IO but low memory. The approach presented in this paper is to make used of the structure of the graph in a divide and conquer like fashion (sort of like community detection).

A related paper I recalled during this talk is:

Local Approximation of PageRank and Reverse PageRank

 Further the paper presents an approach for dynamic, evolving graphs that takes advantage of the fact that subgraphs can have a faster convergence rate. Their approach provides about 20% improvement in time efficiency.