RECORD
Adapting Graph Application Performance via Alternate Data Structure Representation
Programming Languages · Submitted 28 Dec 2014
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim Experiments with graph algorithms on real-world (e.g., Wikipedia metadata, Gnutella topology) and synthetic graph datasets show that our adaptive applications run to completion with lower execution time and/or memory utilization in comparison to their non-adaptive versions.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
Graph processing is used extensively in areas from social networking mining to web indexing. We demonstrate that the performance and dependability of such applications critically hinges on the graph data structure used, because a fixed, compile-time choice of data structure can lead to poor performance or applications unable to complete. To address this problem, we introduce an approach that helps programmers transform regular, off-the-shelf graph applications into adaptive, more dependable applications where adaptations are performed via runtime selection from alternate data structure representations. Using our approach, applications dynamically adapt to the input graph's characteristics and changes in available memory so they continue to run when faced with adverse conditions such as low memory. Experiments with graph algorithms on real-world (e.g., Wikipedia metadata, Gnutella topology) and synthetic graph datasets show that our adaptive applications run to completion with lower execution time and/or memory utilization in comparison to their non-adaptive versions.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Graph processing is used extensively in areas from social networking mining to web indexing. | background 1.00 | 0.04 | 0.02 | asserted 1.00 |
| s1 | We demonstrate that the performance and dependability of such applications critically hinges on the graph data structure used, because a fixed, compile-time choice of data structure can lead to poor performance or applications unable to complete. | background 0.78 | 0.53 | 0.32 | asserted 0.99 |
| s2 | To address this problem, we introduce an approach that helps programmers transform regular, off-the-shelf graph applications into adaptive, more dependable applications where adaptations are performed via runtime selection from alternate data structure representations. | contribution 0.93 | 0.83 | 0.20 | asserted 0.99 |
| s3 | Using our approach, applications dynamically adapt to the input graph's characteristics and changes in available memory so they continue to run when faced with adverse conditions such as low memory. | method 0.57 | 0.72 | 0.16 | asserted 1.00 |
| s4 | Experiments with graph algorithms on real-world (e.g., Wikipedia metadata, Gnutella topology) and synthetic graph datasets show that our adaptive applications run to completion with lower execution time and/or memory utilization in comparison to their non-adaptive versions. | result 1.00 | 0.96 | 0.69 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
Graph processing is used extensively in areas from social networking mining to web indexing. We demonstrate that the performance and dependability of such applications critically hinges on the graph data structure used, because a fixed, compile-time choice of data structure can lead to poor performance or applications unable to complete. To address this problem, we introduce an approach that helps programmers transform regular, off-the-shelf graph applications into adaptive, more dependable applications where adaptations are performed via runtime selection from alternate data structure representations. Using our approach, applications dynamically adapt to the input graph's characteristics and changes in available memory so they continue to run when faced with adverse conditions such as low memory. Experiments with graph algorithms on real-world (e.g., Wikipedia metadata, Gnutella topology) and synthetic graph datasets show that our adaptive applications run to completion with lower execution time and/or memory utilization in comparison to their non-adaptive versions.
Human review
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.