The DOI matches its Crossref record; 32 of the 32 references it cites were found in a registry or an index.
PEGASUS: A Peta-Scale Graph Mining System Implementation and Observations
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
MapReduce: simplified data processing on large clusters
Dean, J., & Ghemawat, S. (2008) · Communications of the ACM · doi:10.1145/1327452.1327492 · Cited by 18,476
The anatomy of a large-scale hypertextual Web search engine
Brin, S., & Page, L. (1998) · Computer Networks and ISDN Systems · doi:10.1016/s0169-7552(98)00110-x · Cited by 16,004
Authoritative sources in a hyperlinked environment
Kleinberg, J. M. (1999) · Journal of the ACM · doi:10.1145/324133.324140 · Cited by 8,959
Newman (2005) · doi:10.1080/00107510500052444 · Cited by 5,749
Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A., & Wiener, J. (2000) · Computer Networks · doi:10.1016/s1389-1286(00)00083-9 · Cited by 2,810
gSpan: graph-based substructure pattern mining
Yan, X., & Han, J. (2003) · 2002 IEEE International Conference on Data Mining, 2002. Proceedings. · doi:10.1109/icdm.2002.1184038 · Cited by 2,013
Authoritative sources in a hyperlinked environment
Kleinberg, J. M. (1998) · Symposium on Discrete Algorithms · doi:10.5555/314613.315045 · Cited by 1,814
Pig latin: a not-so-foreign language for data processing
Olston, C., Reed, B., Srivastava, U., Kumar, R., & Tomkins, A. (2008) · Proceedings of the 2008 ACM SIGMOD international conference on Management of data · doi:10.1145/1376616.1376726 · Cited by 1,730
Grooming, Gossip, and the Evolution of Language
Dunbar, R., & Fisher, M. (1998) · Cited by 796
SCOPE: easy and efficient parallel processing of massive data sets
Chaiken, R., Jenkins, B., Larson, P.-Å., Ramsey, B., Shakib, D., Weaver, S., & Zhou, J. (2008) · Proceedings of the VLDB Endowment · doi:10.14778/1454159.1454166 · Cited by 727
An O(logn) parallel connectivity algorithm
Shiloach, Y., & Vishkin, U. (1982) · Journal of Algorithms · doi:10.1016/0196-6774(82)90008-6 · Cited by 672
Interpreting the Data: Parallel Analysis with Sawzall
Pike, R., Dorward, S., Griesemer, R., & Quinlan, S. (2005) · Scientific Programming · doi:10.1155/2005/962135 · Cited by 611
Google’s MapReduce programming model — Revisited
Lämmel, R. (2008) · Science of Computer Programming · doi:10.1016/j.scico.2007.07.001 · Cited by 489
Automatic multimedia cross-modal correlation discovery
Pan, J.-Y., Yang, H.-J., Faloutsos, C., & Duygulu, P. (2004) · Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1014052.1014135 · Cited by 479
Self-citationGrooming, gossip, and the evolution of language
Cussins, C. (1998) · Journal of the History of the Behavioral Sciences · doi:10.1002/(sici)1520-6696(199823)34:4<398::aid-jhbs13>3.0.co;2-u · Cited by 424
Finding Frequent Patterns in a Large Sparse Graph*
Kuramochi, M., & Karypis, G. (2005) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-005-0003-9 · Cited by 371
Scalable Tensor Decompositions for Multi-aspect Data Mining
Kolda, T. G., & Sun, J. (2008) · 2008 Eighth IEEE International Conference on Data Mining · doi:10.1109/icdm.2008.89 · Cited by 358
Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication
Leskovec, J., Chakrabarti, D., Kleinberg, J., & Faloutsos, C. (2005) · Lecture Notes in Computer Science · doi:10.1007/11564126_17 · Cited by 356
Self-citationDOULION: counting triangles in massive graphs with a coin
Tsourakakis, C. E., Kang, U., Miller, G. L., & Faloutsos, C. (2009) · Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1557019.1557111 · Cited by 328
Self-citationComputing connected components on parallel computers
Hirschberg, D. S., Chandra, A. K., & Sarwate, D. V. (1979) · Communications of the ACM · doi:10.1145/359138.359141 · Cited by 266
Papadimitriou, S., & Sun, J. (2008) · 2008 Eighth IEEE International Conference on Data Mining · doi:10.1109/icdm.2008.142 · Cited by 209
Using PageRank to Characterize Web Structure
Pandurangan, G., Raghavan, P., & Upfal, E. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45655-4_36 · Cited by 164
Cheng, J., Yu, J. X., Ding, B., Yu, P. S., & Wang, H. (2008) · 2008 IEEE 24th International Conference on Data Engineering · doi:10.1109/icde.2008.4497500 · Cited by 164
GraphSig: A Scalable Approach to Mining Significant Subgraphs in Large Graph Databases
Ranu, S., & Singh, A. K. (2009) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2009.133 · Cited by 156
Weighted graphs and disconnected components
McGlohon, M., Akoglu, L., & Faloutsos, C. (2008) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1401890.1401955 · Cited by 111
Self-citationDetecting Communities in Social Networks using Max-Min Modularity
Chen, J., Zai͏̈ane, O. R., & Goebel, R. G. (2009) · SIAM International Conference on Data Mining · doi:10.1137/1.9781611972795.84 · Cited by 100
Mining (Social) Network Graphs to Detect Random Link Attacks
Shrivastava, N., Majumder, A., & Rastogi, R. R. (2008) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2008.4497457 · Cited by 93
Finding Frequent Patterns in a Large Sparse Graph
Kuramochi, M., & Karypis, G. (2004) · SIAM International Conference on Data Mining · doi:10.1137/1.9781611972740.32 · Cited by 91
gPrune: A Constraint Pushing Framework for Graph Pattern Mining
Zhu, F., Yan, X., Han, J., & Yu, P. S. (2007) · Springer eBooks · doi:10.1007/978-3-540-71701-0_38 · Cited by 79
CSV: visualizing and mining cohesive subgraphs
Wang, N., Parthasarathy, S., Tan, K., & Tung, A. K. H. (2008) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/1376616.1376663 · Cited by 60
Top-k Correlative Graph Mining
Ke, Y., Cheng, J. S.-C., & Yu, J. X. (2009) · SIAM International Conference on Data Mining · doi:10.1137/1.9781611972795.89 · Cited by 31
Finding Reliable Subgraphs from Large Probabilistic Graphs
Hintsanen, P., & Toivonen, H. T. T. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-87479-9_13 · Cited by 5
Cited by
Pregel: a system for large-scale graph processing
Malewicz, G., Austern, M. H., Bik, A. J. C., Dehnert, J. C., Horn, I., Leiser, N., & Czajkowski, G. (2010) · Proceedings of the 2010 ACM SIGMOD International Conference on Management of data · doi:10.1145/1807167.1807184 · Cited by 3,515
Distributed GraphLab: a framework for machine learning and data mining in the cloud
Low, Y., Bickson, D., Gonzalez, J., Guestrin, C., Kyrola, A., & Hellerstein, J. M. (2012) · Proceedings of the VLDB Endowment · doi:10.14778/2212351.2212354 · Cited by 1,653
PowerGraph: distributed graph-parallel computation on natural graphs
Gonzalez, J. E., Low, Y., Gu, H., Bickson, D., & Guestrin, C. (2012) · doi:10.5555/2387880.2387883 · Cited by 1,451
A survey of heterogeneous information network analysis
Shi, C., Li, Y., Zhang, J., Sun, Y., & Yu, P. S. (2017) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2016.2598561 · Cited by 1,112
SNAP: A General-Purpose Network Analysis and Graph-Mining Library
Leskovec, J., & Sosič, R. (2017) · ACM Transactions on Intelligent Systems and Technology · doi:10.1145/2898361 · Cited by 870
Metadata
- Authors
- Kang, U., Tsourakakis, C. E., & Faloutsos, C.
- Venue
- 2009 Ninth IEEE International Conference on Data Mining
- Publisher
- IEEE
- Published
- 2009-12
- Pages
- 229-238
- ISSN
- 1550-4786 (ISSN-L)
- OpenAlex
- W2167927436
- Cited by
- 628
- References
- 32
- FWCI
- 32.71
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.