The DOI matches its Crossref record; 32 of the 32 references it cites were found in a registry or an index.
Pregel: a system for large-scale graph processing
Abstract
Many practical computing problems concern large graphs. Standard examples include the Web graph and various social networks. The scale of these graphs - in some cases billions of vertices, trillions of edges - poses challenges to their efficient processing. In this paper we present a computational model suitable for this task. Programs are expressed as a sequence of iterations, in each of which a vertex can receive messages sent in the previous iteration, send messages to other vertices, and modify its own state and that of its outgoing edges or mutate graph topology. This vertex-centric approach is flexible enough to express a broad set of algorithms. The model has been designed for efficient, scalable and fault-tolerant implementation on clusters of thousands of commodity computers, and its implied synchronicity makes reasoning about programs easier. Distribution-related details are hidden behind an abstract API. The result is a framework for processing large graphs that is expressive and easy to program.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
A note on two problems in connexion with graphs
Dijkstra, E. W. (1959) · Numerische Mathematik · doi:10.1007/bf01386390 · Cited by 24,043
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
The Grid 2: Blueprint for a New Computing Infrastructure
Foster, I. T., & Kesselman, C. (1998) · Cited by 7,637
Exploring Network Structure, Dynamics, and Function Using NetworkX
Hagberg, A. A., Schult, D. A., & Swart, P. J. (2008) · Proceedings of the Python in Science Conference · doi:10.25080/tcwv9851 · Cited by 7,477
Ghemawat, S., Gobioff, H., & Leung, S.-T. (2003) · ACM SIGOPS Operating Systems Review · doi:10.1145/1165389.945450 · Cited by 4,984
Ford, D. R., & Fulkerson, D. R. (1962) · Cited by 4,072
A Bridging Model for Parallel Computation
Valiant, L. G. (1990) · ACM eBooks · doi:10.1145/3749740.3749753 · Cited by 3,664
Bigtable: A Distributed Storage System for Structured Data
Chang, F., Dean, J., Ghemawat, S., Hsieh, W. C., Wallach, D. A., Burrows, M., Chandra, T., Fikes, A., & Gruber, R. E. (2008) · ACM Transactions on Computer Systems · doi:10.1145/1365815.1365816 · Cited by 3,460
Bellman, R. (1958) · Quarterly of Applied Mathematics · doi:10.1090/qam/102435 · Cited by 2,758
Dryad: distributed data-parallel programs from sequential building blocks
Isard, M., Budiu, M., Yu, Y., Birrell, A., & Fetterly, D. (2007) · Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007 · doi:10.1145/1272996.1273005 · Cited by 2,432
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
Graph Theory and Its Applications
Gross, J. L., & Yellen, J. (2005) · Chapman & Hall/CRC eBooks · doi:10.1201/9781420057140 · Cited by 1,582
Ghemawat, S., Gobioff, H., & Leung, S.-T. (2003) · Proceedings of the nineteenth ACM symposium on Operating systems principles · doi:10.1145/945445.945450 · Cited by 1,423
The Grid 2: Blueprint for a New Computing Infrastructure
van Nieuwpoort, R. V. (2003) · Grid Computing · Cited by 1,415
The LEDA platform for combinatorial and geometric computing
Mehlhorn, K., Näher, S., & Uhrig, C. (1997) · Lecture Notes in Computer Science · doi:10.1007/3-540-63165-8_161 · Cited by 1,199
Web search for a planet: the google cluster architecture
Barroso, L. A., Dean, J., & Holzle, U. (2003) · IEEE Micro · doi:10.1109/mm.2003.1196112 · Cited by 1,025
Stanford GraphBase: A Platform for Combinatorial Computing, The
Knuth, D. E. (1993) · Cited by 927
High-speed switch scheduling for local-area networks
Anderson, T. E., Owicki, S. S., Saxe, J. B., & Thacker, C. P. (1993) · ACM Transactions on Computer Systems · doi:10.1145/161541.161736 · Cited by 892
Shortest paths algorithms: Theory and experimental evaluation
Cherkassky, B. V., Goldberg, A. V., & Radzik, T. (1996) · Mathematical Programming · doi:10.1007/bf02592101 · Cited by 743
Yu, Y., Isard, M., Fetterly, D., Budiu, M., Erlingsson, Ú., Gunda, P. K., & Currey, J. (2008) · doi:10.5555/1855741.1855742 · Cited by 689
PEGASUS: A Peta-Scale Graph Mining System Implementation and Observations
Kang, U., Tsourakakis, C. E., & Faloutsos, C. (2009) · 2009 Ninth IEEE International Conference on Data Mining · doi:10.1109/icdm.2009.14 · Cited by 628
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
The Boost graph library : user guide and reference manual
Siek, J. G., Lee, L., & Lumsdaine, A. (2002) · CERN Document Server (European Organization for Nuclear Research) · Cited by 608
LEDA: A platform for combinatorial and geometric computing
(2000) · Computers & Mathematics with Applications · doi:10.1016/s0898-1221(00)90217-7 · Cited by 489
CHALLENGES IN PARALLEL GRAPH PROCESSING
LUMSDAINE, A., GREGOR, D., HENDRICKSON, B., & BERRY, J. (2007) · Parallel Processing Letters · doi:10.1142/s0129626407002843 · Cited by 469
Δ-stepping: a parallelizable shortest path algorithm
Meyer, U., & Sanders, P. (2003) · Journal of Algorithms · doi:10.1016/s0196-6774(03)00076-2 · Cited by 309
A Scalable Distributed Parallel Breadth-First Search Algorithm on BlueGene/L
Yoo, A., Chow, E., Henderson, K., McLendon, W., Hendrickson, B., & Catalyurek, U. (2005) · ACM/IEEE SC 2005 Conference (SC'05) · doi:10.1109/sc.2005.4 · Cited by 261
Designing Multithreaded Algorithms for Breadth-First Search and st-connectivity on the Cray MTA-2
Bader, D. A., & Madduri, K. (2006) · 2006 International Conference on Parallel Processing (ICPP'06) · doi:10.1109/icpp.2006.34 · Cited by 216
Maximum weight matching via max-product belief propagation
Bayati, M., Shah, D., & Sharma, M. (2005) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2005.1523648 · Cited by 99
Lifting sequential graph algorithms for distributed-memory parallel computation
Gregor, D., & Lumsdaine, A. (2005) · Conference on Object-Oriented Programming Systems, Languages, and Applications · doi:10.1145/1094811.1094844 · Cited by 69
Parallel shortest path algorithms for solving large-scale instances
Madduri, K., Bader, D. A., Berry, J. W., et al. (2009) · DIMACS series in discrete mathematics and theoretical computer science · doi:10.1090/dimacs/074/10 · Cited by 48
Cited by
Boyd, S. (2010) · now publishers, Inc. eBooks · doi:10.1561/9781601984616 · Cited by 12,677
Chen, M., Mao, S., & Liu, Y. (2014) · Mobile Networks and Applications · doi:10.1007/s11036-013-0489-0 · Cited by 2,913
Apache Spark: A unified engine for big data processing
Zaharia, M., Xin, R. S., Wendell, P., Das, T., Armbrust, M., Dave, A., Meng, X., Rosen, J., Venkataraman, S., Franklin, M. J., et al. (2016) · Communications of the ACM · doi:10.1145/2934664 · Cited by 2,757
Rajaraman, A., & Ullman, J. D. (2011) · Cambridge University Press eBooks · doi:10.1017/cbo9781139058452 · Cited by 2,262
Hogan, A., Blomqvist, E., Cochez, M., D’amato, C., Melo, G. D., Gutierrez, C., Kirrane, S., Gayo, J. E. L., Navigli, R., Neumaier, S., et al. (2022) · ACM Computing Surveys · doi:10.1145/3447772 · Cited by 1,904
Metadata
- Authors
- Malewicz, G., Austern, M. H., Bik, A. J. C., Dehnert, J. C., Horn, I., Leiser, N., & Czajkowski, G.
- Venue
- Proceedings of the 2010 ACM SIGMOD International Conference on Management of data
- Publisher
- ACM
- Published
- 2010-06-06
- Pages
- 135-146
- ISSN
- 0730-8078 (ISSN-L)
- OpenAlex
- W2170616854
- Cited by
- 3,515
- References
- 32
- FWCI
- 136.07
- 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.