A lightweight infrastructure for graph analytics
Open accessThe DOI matches its Crossref record; 19 of the 19 references it cites were found in a registry or an index.
Abstract
Several domain-specific languages (DSLs) for parallel graph analytics have been proposed recently. In this paper, we argue that existing DSLs can be implemented on top of a general-purpose infrastructure that (i) supports very fine-grain tasks, (ii) implements autonomous, speculative execution of these tasks, and (iii) allows application-specific control of task scheduling policies. To support this claim, we describe such an implementation called the Galois system.
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
Rayward-Smith, V. J. (1991) · Journal of the Operational Research Society · doi:10.1057/jors.1991.155 · Cited by 16,821
What is Twitter, a social network or a news media?
Kwak, H., Lee, C., Park, H., & Moon, S. (2010) · Proceedings of the 19th international conference on World wide web · doi:10.1145/1772690.1772751 · Cited by 6,652
Parallel and Distributed Computation: Numerical Methods
Bertsekas, D. P., & Tsitsiklis, J. N. (1989) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 5,293
A faster algorithm for betweenness centrality*
Brandes, U. (2001) · The Journal of Mathematical Sociology · doi:10.1080/0022250x.2001.9990249 · Cited by 4,936
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
Measuring user influence in twitter: The million follower fallacy
Cha, M., Haddadi, H., Benevenuto, F., & Gummadi, K. (2010) · Proceedings of the International AAAI Conference on Web and Social Media · doi:10.1609/icwsm.v4i1.14033 · Cited by 3,022 · cited 1×
“The twitter40 [16] and twitter50 [6] graphs are real-world social network graphs.”
BackgroundAn introduction to parallel algorithms
JáJá, J. F. (1992) · Cited by 1,600
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
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
Optimistic parallelism requires abstractions
Kulkarni, M., Pingali, K., Walter, B., Ramanarayanan, G., Bala, K., & Chew, L. P. (2007) · Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/1250734.1250759 · Cited by 441
Self-citationThe drinking philosophers problem
Chandy, K. M., & Misra, J. (1984) · ACM Transactions on Programming Languages and Systems · doi:10.1145/1780.1804 · Cited by 390
The tao of parallelism in algorithms
Pingali, K., Nguyen, D., Kulkarni, M., Burtscher, M., Hassaan, M. A., Kaleem, R., Lee, T.-H., Lenharth, A., Manevich, R., Méndez-Lojo, M., et al. (2011) · ACM SIGPLAN Notices · doi:10.1145/1993316.1993501 · Cited by 312
Self-citationThe tao of parallelism in algorithms
Pingali, K., Nguyen, D., Kulkarni, M., Burtscher, M., Hassaan, M. A., Kaleem, R., Lee, T.-H., Lenharth, A., Manevich, R., Méndez-Lojo, M., et al. (2011) · Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/1993498.1993501 · Cited by 234
Self-citationScalable locality-conscious multithreaded memory allocation
Schneider, S., Antonopoulos, C. D., & Nikolopoulos, D. S. (2006) · International Symposium on Memory Management · doi:10.1145/1133956.1133968 · Cited by 99
Synthesizing concurrent schedulers for irregular algorithms
Nguyen, D. D., & Pingali, K. K. (2011) · International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) · doi:10.1145/1950365.1950404 · Cited by 39
Self-citationThe soft heap: an approximate priority queue with optimal error rate
Chazelle, B. (2000) · Journal of the ACM · doi:10.1145/355541.355554 · Cited by 32
(1990)
Cited by
Gunrock: a high-performance graph processing library on the GPU
Wang, Y., Davidson, A., Pan, Y., Wu, Y., Riffel, A., & Owens, J. D. (2016) · Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · doi:10.1145/2851141.2851145 · Cited by 338
PowerLyra: differentiated graph computation and partitioning on skewed graphs
Chen, R., Shi, J., Chen, Y., & Chen, H. (2015) · Proceedings of the Tenth European Conference on Computer Systems · doi:10.1145/2741948.2741970 · Cited by 299
McCune, R. R., Weninger, T., & Madey, G. (2015) · ACM Computing Surveys · doi:10.1145/2818185 · Cited by 294
Gunrock: a high-performance graph processing library on the GPU
Wang, Y., Davidson, A., Pan, Y., Wu, Y., Riffel, A., & Owens, J. D. (2015) · Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · doi:10.1145/2688500.2688538 · Cited by 287
GraphMat: high performance graph analytics made productive
Sundaram, N., Satish, N., Patwary, M. M. A., Dulloor, S. R., Anderson, M. J., Vadlamudi, S. G., Das, D., & Dubey, P. (2015) · Proceedings of the VLDB Endowment · doi:10.14778/2809974.2809983 · Cited by 282
Metadata
- Authors
- Nguyen, D., Lenharth, A., & Pingali, K.
- Venue
- Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles
- Publisher
- ACM
- Published
- 2013-11-03
- Pages
- 456-471
- OpenAlex
- W2034102265
- Cited by
- 579
- References
- 19
- FWCI
- 23.47
- Type
- conference paper
- Language
- en
- Open access
- gold
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.