The scalable hyperlink store

ABSTRACT

This paper describes the Scalable Hyperlink Store, a distributed in-memory "database" for storing large portions of the web graph. SHS is an enabler for research on structural properties of the web graph as well as new link-based ranking algorithms. Previous work on specialized hyperlink databases focused on finding efficient compression algorithms for web graphs. By contrast, this work focuses on the systems issues of building such a database. Specifically, it describes how to build a hyperlink database that is fast, scalable, fault-tolerant, and incrementally updateable.

REFERENCES

• 1: Micah Adler , Michael Mitzenmacher, Towards Compressing Web Graphs, Proceedings of the Data Compression Conference, p.203, March 27-29, 2001
• 2: Luca Becchetti , Carlos Castillo , Debora Donato , Ricardo Baeza-YATES , Stefano Leonardi, Link analysis for Web spam detection, ACM Transactions on the Web (TWEB), v.2 n.1, p.1-42, February 2008 [doi>10.1145/1326561.1326563]
• 3: Krishna Bharat , Andrei Broder , Monika Henzinger , Puneet Kumar , Suresh Venkatasubramanian, The connectivity server: fast access to linkage information on the Web, Proceedings of the seventh international conference on World Wide Web 7, p.469-477, April 1998, Brisbane, Australia
• 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: Andrei Z. Broder , Moses Charikar , Alan M. Frieze , Michael Mitzenmacher, Min-wise independent permutations, Journal of Computer and System Sciences, v.60 n.3, p.630-659, June 2000 [doi>10.1006/jcss.1999.1690]
• 7: Andrei Broder , Ravi Kumar , Farzin Maghoul , Prabhakar Raghavan , Sridhar Rajagopalan , Raymie Stata , Andrew Tomkins , Janet Wiener, Graph structure in the Web, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.309-320, June 2000, Amsterdam, The Netherlands
• 8: 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]
• 9: Ariel Fuxman , Panayiotis Tsaparas , Kannan Achan , Rakesh Agrawal, Using the wisdom of the crowds for keyword generation, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367506]
• 10: S. Gollapudi, M. Najork, and R. Panigrahy. Using Bloom Filters to Speed Up HITS-like Ranking Algorithms. In 5th Workshop on Algorithms and Models for the Web--Graph, December 2007, pages 195--201.
• 11: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.668-677, January 25-27, 1998, San Francisco, California, United States
• 12: Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, Trawling the Web for emerging cyber-communities, Proceedings of the eighth international conference on World Wide Web, p.1481-1493, May 1999, Toronto, Canada
• 13: R. Lempel , S. Moran, The stochastic approach for link-structure analysis (SALSA) and the TKC effect, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.33 n.1-6, p.387-401, June 2000
• 14: Massimo Marchiori, The quest for correct information on the Web: hyper search engines, Computer Networks and ISDN Systems, v.29 n.8-13, p.1225-1235, Sep. 1997
• 15: Alistair Moffat , Andrew Turpin, Compression and Coding Algorithms, Kluwer Academic Publishers, Norwell, MA, 2002
• 16: M. Najork. System and method for maintaining a distributed database of hyperlinks. US Patent 7340467; filed April 2003, issued March 2008.
• 17: Marc A. Najork, Comparing the effectiveness of hits and salsa, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal [doi>10.1145/1321440.1321465]
• 18: Marc Najork , Nick Craswell, Efficient and effective link analysis with precomputed salsa maps, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA [doi>10.1145/1458082.1458093]
• 19: Marc Najork , Sreenivas Gollapudi , Rina Panigrahy, Less is more: sampling the neighborhood graph makes SALSA better and faster, Proceedings of the Second ACM International Conference on Web Search and Data Mining, February 09-12, 2009, Barcelona, Spain [doi>10.1145/1498759.1498832]
• 20: Marc Najork , Allan Heydon, High-performance web crawling, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
• 21: Marc A. Najork , Hugo Zaragoza , Michael J. Taylor, Hits on the web: how does it compare?, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277823]
• 22: 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.
• 23: Keith H. Randall , Raymie Stata , Janet L. Wiener , Rajiv G. Wickremesinghe, The Link Database: Fast Access to Graphs of the Web, Proceedings of the Data Compression Conference, p.122, April 02-04, 2002
• 24: Torsten Suel , Jun Yuan, Compressing the Graph Structure of the Web, Proceedings of the Data Compression Conference, p.213, March 27-29, 2001
• 25: I. Witten, A. Moffat, and T. Bell. Managing Gigabytes (2nd edition).Academic Press, 1999.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

General Terms:
Performance, Reliability

Keywords:
hyperlink database, scalability, web graph