The DOI matches its Crossref record; 1 of the 1 references it cites were found in a registry or an index.
Design patterns for efficient graph algorithms in MapReduce
Abstract
Graphs are analyzed in many important contexts, including ranking search results based on the hyperlink structure of the world wide web, module detection of proteinprotein interaction networks, and privacy analysis of social networks. Many graphs of interest are difficult to analyze because of their large size, often spanning millions of vertices and billions of edges. As such, researchers have increasingly turned to distributed solutions. In particular, MapReduce has emerged as an enabling technology for large-scale graph processing. However, existing best practices for MapReduce graph algorithms have significant shortcomings that limit performance, especially with respect to partitioning, serializing, and distributing the graph. In this paper, we present three design patterns that address these issues and can be used to accelerate a large class of graph algorithms based on message passing, exemplified by PageRank. Experiments show that the application of our design patterns reduces the running time of PageRank on a web graph with 1.4 billion edges by 69%. 1.
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
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
Cited by
Boyd, S., Parikh, N., Chu, E., Peleato, B., & Eckstein, J. (2011) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000016 · Cited by 17,075
Boyd, S. (2010) · now publishers, Inc. eBooks · doi:10.1561/9781601984616 · Cited by 12,677
WTF: the who to follow service at Twitter
Gupta, P., Goel, A., Lin, J., Sharma, A., Wang, D., & Zadeh, R. (2013) · Proceedings of the 22nd international conference on World Wide Web · doi:10.1145/2488388.2488433 · Cited by 461
Self-citationAn overview of the Hadoop/MapReduce/HBase framework and its current applications in bioinformatics
Taylor, R. C. (2010) · BMC Bioinformatics · doi:10.1186/1471-2105-11-s12-s1 · Cited by 431
McCune, R. R., Weninger, T., & Madey, G. (2015) · ACM Computing Surveys · doi:10.1145/2818185 · Cited by 294
Metadata
- Authors
- Lin, J., & Schatz, M.
- Venue
- Proceedings of the Eighth Workshop on Mining and Learning with Graphs
- Publisher
- ACM
- Published
- 2010-07-24
- Pages
- 78-85
- OpenAlex
- W2020302654
- Cited by
- 167
- References
- 1
- FWCI
- 20.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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Design patterns for efficient graph algorithms in MapReduce. https://app.cochat.ai/papers/10.1145/1830252.1830263
- The paper
- Lin, J., & Schatz, M. (2010). Design patterns for efficient graph algorithms in MapReduce. Proceedings of the Eighth Workshop on Mining and Learning with Graphs. https://doi.org/10.1145/1830252.1830263
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.