US Patent:
20120330864, Dec 27, 2012
Inventors:
Kaushik Chakrabarti - Redmond WA, US
Dong Xin - Redmond WA, US
Bahman Bahmani - Stanford CA, US
Assignee:
Microsoft Corporation - Redmond WA
International Classification:
G06N 3/12
Abstract:
A personalized page rank computation system is described herein that provides a fast MapReduce method for Monte Carlo approximation of personalized PageRank vectors of all the nodes in a graph. The method presented is both faster and less computationally intensive than existing methods, allowing a broader scope of problems to be solved by existing computing hardware. The system adopts the Monte Carlo approach and provides a method to compute single random walks of a given length for all nodes in a graph that it is superior in terms of the number of map-reduce iterations among a broad class of methods. The resulting solution reduces the I/O cost and outperforms the state-of-the-art FPPR approximation methods, in terms of efficiency and approximation error. Thus, the system can very efficiently perform single random walks of a given length starting at each node in the graph and can very efficiently approximate all the personalized PageRank vectors.
