Home Publications all years 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 theses techreports presentations edited volumes conferences Awards Research Teaching BLOG Miscellaneous Full CV [pdf] ross2019
Events

Past Events
|
Publications of Torsten Hoefler
Copyright Notice:
The documents distributed by this server have been provided by the
contributing authors as a means to ensure timely dissemination of
scholarly and technical work on a noncommercial basis. Copyright and all
rights therein are maintained by the authors or by other copyright
holders, notwithstanding that they have offered their works here
electronically. It is understood that all persons copying this
information will adhere to the terms and constraints invoked by each
author's copyright. These works may not be reposted without the explicit
permission of the copyright holder.
M. Besta, D. Stanojevic, T. Zivic, J. Singh, M. Hoerold, T. Hoefler:
| | Log(Graph): A Near-Optimal High-Performance Graph Representation
(presented in Limassol, Cyprus, ACM, Nov. 2018, Accepted at the 27th International Conference on Parallel Architectures and Compilation (PACT'18) )
AbstractToday’s graphs used in domains such as machine learning or
social network analysis may contain hundreds of billions of
edges. Yet, they are not necessarily stored efficiently, and standard
graph representations such as adjacency lists waste a
significant number of bits while graph compression schemes
such as WebGraph often require time-consuming decompression.
To address this, we propose Log(Graph): a graph representation
that combines high compression ratios with very
low-overhead decompression to enable cheaper and faster
graph processing. The key idea is to encode a graph so that
the parts of the representation approach or match the respective
storage lower bounds. We call our approach “graph
logarithmization” because these bounds are usually logarithmic.
Our high-performance Log(Graph) implementation
based on modern bitwise operations and state-of-the-art succinct
data structures achieves high compression ratios as well
as performance. For example, compared to the tuned Graph
Algorithm Processing Benchmark Suite (GAPBS), it reduces
graph sizes by 20-35% while matching GAPBS’ performance
or even delivering speedups due to reducing amounts of
transferred data. It approaches the compression ratio of the
established WebGraph compression library while enabling
speedups of up to more than 2×. Log(Graph) can improve
the design of various graph processing engines or libraries on
single NUMA nodes as well as distributed-memory systems.
Documentsdownload article:  | | BibTeX | @inproceedings{, author={M. Besta and D. Stanojevic and T. Zivic and J. Singh and M. Hoerold and T. Hoefler}, title={{Log(Graph): A Near-Optimal High-Performance Graph Representation}}, year={2018}, month={Nov.}, location={Limassol, Cyprus}, publisher={ACM}, note={Accepted at the 27th International Conference on Parallel Architectures and Compilation (PACT'18)}, source={http://www.unixer.de/~htor/publications/}, } |
|
|