  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.
