Record Details

Index design for dynamic personalized PageRank

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Index design for dynamic personalized PageRank
 
Creator PATHAK, AMIT
CHAKRABARTI, SOUMEN
GUPTA, MANISH
 
Subject numerical analysis
technology
query processing
 
Description Personalized PageRank, related to random walks with restarts and conductance in resistive networks, is a frequent search paradigm for graph-structured databases. While efficient batch algorithms exist for static whole-graph PageRank, interactive query-time personalized PageRank has proved more challenging. Here we describe how to select and build indices for a popular class of PageRank algorithms, so as to provide real-time personalized PageRank and smoothly trade off between index size, preprocessing time, and query speed. We achieve this by developing a precise, yet efficiently estimated performance model for personalized PageRank query execution. We use this model in conjunction with a query workload in a cost-benefit type index optimizer. On millions of queries from CITESEER and its data graphs with 74-320 thousand nodes, our algorithm runs 50-400x faster than whole-graph PageRank, the gap growing with graph size. Index size is 10-20% of a text index. Ranking accuracy is above 94%.
 
Publisher IEEE
 
Date 2009-05-19T09:11:54Z
2011-11-28T08:06:39Z
2011-12-15T09:57:25Z
2009-05-19T09:11:54Z
2011-11-28T08:06:39Z
2011-12-15T09:57:25Z
2008
 
Type Article
 
Identifier Proceedings of the IEEE 24th International Conference on Data Engineering, Cancún, Mexico, 7-12 April 2008, 1489-1491
978-1-4244-1836-7
10.1109/ICDE.2008.4497599
http://hdl.handle.net/10054/1384
http://dspace.library.iitb.ac.in/xmlui/handle/10054/1384
 
Language en