Storing Dynamic Graphs: Speed vs. Storage Trade-offs

Loading...
Thumbnail Image

View/Download File

Persistent link to this item

Statistics
View Statistics

Journal Title

Journal ISSN

Volume Title

Title

Storing Dynamic Graphs: Speed vs. Storage Trade-offs

Published Date

2014-07-30

Publisher

Type

Report

Abstract

With the ever increasing size and availability of web and social graph comes the need for compact and efficient data structures in which to store them. The problem of compact representations for sparse static graphs is a well studied problem in the domain of web and online social graphs, namely the WebGraph Framework and the Layered Label Propagation ordering for extending WebGraph to online social networks, among others. While these techniques do a satisfactory job in the context of static sparse graphs, there is little literature on how these techniques can be extended to dynamic sparse graphs. In this paper, we present algorithms and experimental analysis for five data structures for representing dynamic sparse graphs: Linked-List (LL), Batch Compressed Sparse Row (BCSR), Dynamic Adjacency Array (DAA), Dynamic Intervalized Adjacency Array (DIAA), and Dynamic Compressed Adjacency Array (DCAA). The goal of the presented data structures is two fold. First, the data structures must be compact, as the size of the graphs being operated on continues to grow to less manageable sizes. Second, the cost of operating on the data structures must be within a small factor of the cost of operating on the static graph, else these data structures will not be useful. Of these five algorithms, LL, BCSR, and DAA are baseline approaches, DCAA is semi-compact, but suited for fast operation, and DIAA is focused on compactness and is a dynamic extension of the WebGraph Framework. Our results show that for well intervalized graphs, like web graphs, DCAA is superior to all other data structures in terms of memory and access time. Furthermore, we show that in terms of memory, the compact data structure DIAA outperforms all other data structures at the cost of a modest increase in update and access time.

Keywords

Description

Related to

Replaces

License

Series/Report Number

Technical Report; 14-018

Funding information

Isbn identifier

Doi identifier

Previously Published Citation

Other identifiers

Suggested citation

Iverson, Jeremy; Karypis, George. (2014). Storing Dynamic Graphs: Speed vs. Storage Trade-offs. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/215955.

Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.