Speeding up algorithms on compressed web graphs

ABSTRACT

A variety of lossless compression schemes have been proposed to reduce the storage requirements of web graphs. One successful approach is virtual node compression [7], in which often-used patterns of links are replaced by links to virtual nodes, creating a compressed graph that succinctly represents the original. In this paper, we show that several important classes of web graph algorithms can be extended to run directly on virtual node compressed graphs, such that their running times depend on the size of the compressed graph rather than the original. These include algorithms for link analysis, estimating the size of vertex neighborhoods, and a variety of algorithms based on matrix-vector products and random walks. Similar speed-ups have been obtained previously for classical graph algorithms like shortest paths and maximum bipartite matching. We measure the performance of our modified algorithms on several publicly available web graph datasets, and demonstrate significant empirical speedups that nearly match the compression ratios.

REFERENCES

• 1: Reid Andersen , Kevin J. Lang, Communities from seed sets, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135814]
• 2: L. Becchetti, C. Castillo, D. Donato, S. Leonardi, and R. Baeza-Yates. Using rank propagation and probabilistic counting for link-based spam detection. In Proceedings of the Workshop on Web Mining and Web Usage Analysis (WebKDD), Pennsylvania, USA, August 2006. ACM Press.
• 3: Paolo Boldi , Bruno Codenotti , Massimo Santini , Sebastiano Vigna, UbiCrawler: a scalable fully distributed web crawler, Software—Practice & Experience, v.34 n.8, p.711-726, 10 July 2004 [doi>10.1002/spe.587]
• 4: P. Boldi , S. Vigna, The webgraph framework I: compression techniques, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988752]
• 5: Paolo Boldi , Sebastiano Vigna, The WebGraph Framework II: Codes For The World-Wide Web, Proceedings of the Conference on Data Compression, p.528, March 23-25, 2004
• 6: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 7: Gregory Buehrer , Kumar Chellapilla, A scalable pattern mining approach to web graph compression with communities, Proceedings of the international conference on Web search and web data mining, February 11-12, 2008, Palo Alto, California, USA [doi>10.1145/1341531.1341547]
• 8: F. R. K. Chung. Spectral Graph Theory.
• 9: Tomás Feder , Adam Meyerson , Rajeev Motwani , Loc O'Callaghan , Rinap Panigrahy, Representing Graph Metrics with Fewest Edges, Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, p.355-366, February 27-March 01, 2003
• 10: Tomás Feder , Rajeev Motwani, Clique partitions, graph compression and speeding-up algorithms, Journal of Computer and System Sciences, v.51 n.2, p.261-272, Oct. 1995 [doi>10.1006/jcss.1995.1065]
• 11: Taher H. Haveliwala, Topic-Sensitive PageRank: A Context-Sensitive Ranking Algorithm for Web Search, IEEE Transactions on Knowledge and Data Engineering, v.15 n.4, p.784-796, July 2003 [doi>10.1109/TKDE.2003.1208999]
• 12: Glen Jeh , Jennifer Widom, Scaling personalized web search, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775191]
• 13: R. Kannan and V. Vinay. Analyzing the structure of large graphs. Manuscript, 1999.
• 14: David Kempe , Frank McSherry, A decentralized algorithm for spectral analysis, Journal of Computer and System Sciences, v.74 n.1, p.70-83, February, 2008 [doi>10.1016/j.jcss.2007.04.014]
• 15: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 16: Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, Trawling the Web for emerging cyber-communities, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.11-16, p.1481-1493, May 17, 1999
• 17: R. Lempel , S. Moran, The stochastic approach for link-structure analysis (SALSA) and the TKC effect, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.387-401, June 2000, Amsterdam, The Netherlands
• 18: Frank McSherry, A uniform approach to accelerated PageRank computation, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060829]
• 19: L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford Digital Library Technologies Project, 1998.
• 20: Dengyong Zhou , Christopher J. C. Burges , Tao Tao, Transductive link spam detection, Proceedings of the 3rd international workshop on Adversarial information retrieval on the web, May 08-08, 2007, Banff, Alberta, Canada [doi>10.1145/1244408.1244413]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms

Keywords:
algorithms, graph compression, stochastic processes, web graph analysis