Name
Abstract | ||
|---|---|---|
Several compressed graph representations were proposed in the last 15 years. Today, all these representations are highly relevant in practice since they enable to keep large-scale web and social graphs in the main memory of a single machine and consequently facilitate fast random access to nodes and edges. While much effort was spent on finding space-efficient and fast representations, one issue was only partially addressed: developing resourceefficient construction algorithms. In this paper, we engineer the construction of regular and hybrid k(2)-trees. We show that algorithms based on the Z-order sorting reduce the memory footprint significantly and at the same time are faster than previous approaches. We also engineer a parallel version, which fully utilizes all CPUs and caches. We show the practicality of the latter version by constructing partitioned hybrid k-trees for Web graphs in the scale of a billion nodes and up to 100 billion edges. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/978-3-319-67428-5_11 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
Web graphs,Compact data structures,Graph compression | Graph,Graph compression,Information retrieval,Computer science,Random access | Conference |
Volume | ISSN | Citations |
10508 | 0302-9743 | 0 |
PageRank | References | Authors |
0.34 | 15 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jan Broß | 1 | 0 | 0.34 |
| Simon Gog | 2 | 345 | 24.99 |
| Matthias Hauck | 3 | 3 | 1.41 |
| Marcus Paradies | 4 | 82 | 10.36 |