GPS: a graph processing system
The DOI matches its Crossref record; 25 of the 25 references it cites were found in a registry or an index.
Abstract
GPS (for Graph Processing System) is a complete open-source system we developed for scalable, fault-tolerant, and easy-to-program execution of algorithms on extremely large graphs. This paper serves the dual role of describing the GPS system, and presenting techniques and experimental results for graph partitioning in distributed graph-processing systems like GPS. GPS is similar to Google's proprietary Pregel system, with three new features: (1) an extended API to make global computations more easily expressed and more efficient; (2) a dynamic repartitioning scheme that reassigns vertices to different workers during the computation, based on messaging patterns; and (3) an optimization that distributes adjacency lists of high-degree vertices across all compute nodes to improve performance. In addition to presenting the implementation of GPS and its novel features, we also present experimental results on the performance effects of both static and dynamic graph partitioning schemes, and we describe the compilation of a high-level domain-specific programming language to GPS, enabling easy expression of complex algorithms.
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
A faster algorithm for betweenness centrality*
Brandes, U. (2001) · The Journal of Mathematical Sociology · doi:10.1080/0022250x.2001.9990249 · Cited by 4,936
(2010) · Cited by 4,411
A Bridging Model for Parallel Computation
Valiant, L. G. (1990) · ACM eBooks · doi:10.1145/3749740.3749753 · Cited by 3,664
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
Prud’hommeaux, E. (2008) · Medical Entomology and Zoology · Cited by 3,097
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
Hive: a warehousing solution over a map-reduce framework
Thusoo, A., Sarma, J. S., Jain, N., Shao, Z., Chakka, P., Anthony, S., Liu, H., Wyckoff, P., & Murthy, R. (2009) · Proceedings of the VLDB Endowment · doi:10.14778/1687553.1687609 · Cited by 1,556
The webgraph framework I: compression techniques
Boldi, P., & Vigna, S. (2004) · Proceedings of the 13th international conference on World Wide Web · doi:10.1145/988672.988752 · Cited by 1,201
Twister: a runtime for iterative MapReduce
Ekanayake, J., Li, H., Zhang, B., Gunarathne, T., Bae, S.-H., Qiu, J., & Fox, G. (2010) · Proceedings of the 19th ACM International Symposium on High Performance Distributed Computing · doi:10.1145/1851476.1851593 · Cited by 777
HaLoop: efficient iterative data processing on large clusters
Bu, Y., Howe, B., Balazinska, M., & Ernst, M. D. (2010) · Proceedings of the VLDB Endowment · doi:10.14778/1920841.1920881 · Cited by 693
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
Boldi, P., Rosa, M., Santini, M., & Vigna, S. (2011) · Proceedings of the 20th international conference on World wide web · doi:10.1145/1963405.1963488 · Cited by 592
UbiCrawler: a scalable fully distributed Web crawler
Boldi, P., Codenotti, B., Santini, M., & Vigna, S. (2004) · Software: Practice and Experience · doi:10.1002/spe.587 · Cited by 560
Scalable SPARQL querying of large RDF graphs
Huang, J., Abadi, D. J., & Ren, K. (2011) · Proceedings of the VLDB Endowment · doi:10.14778/3402707.3402747 · Cited by 461
Streaming graph partitioning for large distributed graphs
Stanton, I., & Kliot, G. (2012) · Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2339530.2339722 · Cited by 446
The Combinatorial BLAS: design, implementation, and applications
Buluç, A., & Gilbert, J. R. (2011) · The International Journal of High Performance Computing Applications · doi:10.1177/1094342011403516 · Cited by 415
Lin, F., & Cohen, W. W. (2018) · Figshare · doi:10.1184/r1/6476252 · Cited by 188
iMapReduce: A Distributed Computing Framework for Iterative Computation
Zhang, Y., Gao, Q., Gao, L., & Wang, C. (2012) · Journal of Grid Computing · doi:10.1007/s10723-012-9204-9 · Cited by 179
Signal/Collect: Graph Algorithms for the (Semantic) Web
Stutz, P., Bernstein, A., & Cohen, W. W. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-17746-0_48 · Cited by 141
Image webs: Computing and exploiting connectivity in image collections
Heath, K., Gelfand, N., Ovsjanikov, M., Aanjaneya, M., & Guibas, L. J. (2010) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2010.5539991 · Cited by 93
Spectral Analysis for Billion-Scale Graphs: Discoveries and Implementation
Kang, U., Meeder, B., & Faloutsos, C. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-20847-8_2 · Cited by 88
iMapReduce: A Distributed Computing Framework for Iterative Computation
Zhang, Y., Gao, Q., Gao, L., & Wang, C. (2011) · IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum · doi:10.1109/ipdps.2011.260 · Cited by 67
Site-Based Partitioning and Repartitioning Techniques for Parallel PageRank Computation
Cevahir, A., Aykanat, C., Türk, A., & Cambazoglu, B. B. (2010) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2010.119 · Cited by 19
Cited by
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
GraphChi: Large-Scale Graph Computation on Just a PC
Kyrola, A., Blelloch, G. E., & Guestrin, C. (2018) · Figshare · doi:10.1184/r1/6605999 · Cited by 868
Ligra: a lightweight graph processing framework for shared memory
Shun, J., & Blelloch, G. E. (2013) · Proceedings of the 18th ACM SIGPLAN symposium on Principles and practice of parallel programming · doi:10.1145/2442516.2442530 · Cited by 798
A scalable processing-in-memory accelerator for parallel graph processing
Ahn, J., Hong, S., Yoo, S., Mutlu, O., & Choi, K. (2015) · Proceedings of the 42nd Annual International Symposium on Computer Architecture · doi:10.1145/2749469.2750386 · Cited by 767
Recent Advances in Graph Partitioning
Buluç, A., Meyerhenke, H., Safro, I., Sanders, P., & Schulz, C. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-49487-6_4 · Cited by 482
Metadata
- Authors
- Salihoglu, S., & Widom, J.
- Venue
- Proceedings of the 25th International Conference on Scientific and Statistical Database Management
- Publisher
- ACM
- Published
- 2013-07-29
- Pages
- 1-12
- ISSN
- 1551-6393 (ISSN-L)
- OpenAlex
- W1969970763
- Cited by
- 510
- References
- 25
- FWCI
- 48.43
- 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.