2009 PEGASUSAPetaScaleGraphMini

• (Kang et al., 2009) ⇒ U. Kang, Charalampos E. Tsourakakis, and Christos Faloutsos. (2009). “PEGASUS: A Peta-Scale Graph Mining System Implementation and Observations.” In: Proceedings of the Ninth IEEE International Conference on Data Mining (ICDM 2009). doi:10.1109/ICDM.2009.14

Subject Headings:

Quotes

Abstract

In this paper, we describe PEGASUS, an open source peta graph mining library which performs typical graph mining tasks such as computing the diameter of the graph, computing the radius of each node and finding the connected components. As the size of graphs reaches several giga-, tera- or peta-bytes, the necessity for such a library grows too. To the best of our knowledge, PEGASUS is the first such library, implemented on the top of the HADOOP platform, the open source version of MAPREDUCE. Many graph mining operations (PageRank, spectral clustering, diameter estimation, connected components etc.) are essentially a repeated matrix-vector multiplication. In this paper we describe a very important primitive for PEGASUS, called GIM-V (generalized iterated matrix-vector multiplication). GIM-V is highly optimized, achieving (a) good scale-up on the number of available machines (b) linear running time on the number of edges, and (c) more than 5 times faster performance over the non-optimized version of GIM-V. Our experiments ran on M45, one of the top 50 supercomputers in the world. We report our findings on several real graphs, including one of the largest publicly available Web graphs, thanks to Yahoo!, with ≈ 6,7 billion edges.

---

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2009 PEGASUSAPetaScaleGraphMini	Christos Faloutsos U. Kang Charalampos E. Tsourakakis			PEGASUS: A Peta-Scale Graph Mining System Implementation and Observations		ICDM 2009 Proceedings		10.1109/ICDM.2009.14		2009