PEGASUS - Large Scale and Big Data: Processing and Management - page 283

winning combination, which achieves more than 5 times faster perfor-
mance to the naive implementation.

• We implemented PEGASUS and ran it on M45, one of the 50 largest

supercomputers in the world (3.5 TB memory, 1.5 PB disk storage). Using
PEGASUS and our optimized generalized iterative matrix-vector multipli-
cation variants, we analyzed real-world graphs to reveal important patterns
including power law tails, stability of connected components, and anoma-
lous components. Our largest graph, “YahooWeb,” spanned 120 Gb, and is
one of the largest publicly available graph that has ever been studied.

REFERENCES
1. http://googleblog.blogspot.co.uk/2008/07/we-knew-web-was-big.html.
2. http://tinyurl.com/afzzuvd.
3. http://incubator.apache.org/giraph/.
4. http://tinyurl.com/csqljsr.
5. R. Albert, H. Jeong, and A.-L. Barabasi. Diameter of the world wide web. Nature ,
(401):130-131, 1999.
6. N. Alon, Y. Matias, and M. Szegedy. The space complexity of approximating the fre-
quency moments. In Proceedings of the Twenty-Eighth Annual ACM Symposium on
Theory of Computing , STOC'96 , pages 20-29, New York, 1996. ACM.
7. L. Backstrom, P. Boldi, M. Rosa, J. Ugander, and S. Vigna. Four degrees of separation.
In WebSci , pages 33-42, 2012.
8. D. A. Bader and K. Madduri. A graph-theoretic analysis of the human protein-interaction
network using multicore parallel algorithms. Parallel Computing , 34(11):627-639, 2008.
9. Z. Bar-Yossef, T. S. Jayram, R. Kumar, D. Sivakumar, and L. Trevisan. Counting dis-
tinct elements in a data stream. In Proceedings of the 6th International Workshop on
Randomization and Approximation Techniques , RANDOM'02 , pages 1-10. Springer-
Verlag, 2002.
10. Z. Bar-Yossef, R. Kumar, and D. Sivakumar. Reductions in streaming algorithms,
with an application to counting triangles in graphs. In Proceedings of the Thirteenth
Annual ACM-SIAM Symposium on Discrete Algorithms , SODA'02 , pages 623-632,
Philadelphia, PA, USA, 2002. Society for Industrial and Applied Mathematics.
11. K. Beyer, P. J. Haas, B. Reinwald, Y. Sismanis, and R. Gemulla. On synopses for distinct-
value estimation under multiset operations. In Proceedings of the 2007 ACM SIGMOD
International Conference on Management of data , SIGMOD'07 , pages 199-210, New
York, 2007. ACM.
12. K. Bharat, B.-W. Chang, M. R. Henzinger, and M. Ruhl. Who links to whom: Mining
linkage between web sites. In Proceedings of the 2001 IEEE International Conference
on Data Mining , ICDM'01 , pages 51-58, Washington, DC, USA, 2001. IEEE Computer
Society.
13. P. Boldi, M. Rosa, and S. Vigna. Hyperanf: Approximating the neighbourhood function
of very large graphs on a budget. In Proceedings of the 20th International Conference
on World Wide Web , WWW'11 , pages 625-634, New York, 2011. ACM.
14. J. A. Bondy and U. S. Ramachandra Murty. Graph Theory with Applications , volume
290. MacMillan, London, 1976.
15. S. Brin and L. Page. The anatomy of a large-scale hypertextual (web) search engine.
In Proceedings of the 7th International World Wide Web Conference (WWW7)/Computer
Networks , pages 107-117, 1998. Published as Proc. 7th International World Wide Web
Conference (WWW7)/Computer Networks, volume 30, number 1-7.