@proceedings {260, title = {LLAMA: Efficient graph analytics using Large Multiversioned Arrays}, journal = {2015 IEEE 31st International Conference on Data Engineering (ICDE)}, year = {2015}, month = {04/2015}, publisher = {IEEE}, address = {Seoul, South Korea}, abstract = {We present LLAMA, a graph storage and analysis system that supports mutability and out-of-memory execution. LLAMA performs comparably to immutable main-memory analysis systems for graphs that fit in memory and significantly outperforms existing out-of-memory analysis systems for graphs that exceed main memory. LLAMA bases its implementation on the compressed sparse row (CSR) representation, which is a read-only representation commonly used for graph analytics. We augment this representation to support mutability and persistence using a novel implementation of multi-versioned array snapshots, making it ideal for applications that receive a steady stream of new data, but need to perform whole-graph analysis on consistent views of the data. We compare LLAMA to state-of-the-art systems on representative graph analysis workloads, showing that LLAMA scales well both out-of-memory and across parallel cores. Our evaluation shows that LLAMA{\textquoteright}s mutability introduces modest overheads of 3-18\% relative to immutable CSR for in-memory execution and that it outperforms state-of-the-art out-of-memory systems in most cases, with a best case improvement of 5x on breadth-first-search.}, doi = {10.1109/ICDE.2015.7113298}, author = {Peter Macko and Virendra Marathe and Daniel Margo and Seltzer, Margo} }