bei Google ScholarTitelangaben
Mayer, Ruben ; Jacobsen, Hans-Arno:
Hybrid edge partitioner : Partitioning large power-law graphs under memory constraints.
In:
Proceedings of the 2021 International Conference on Management of Data. -
New York
: Association for Computing Machinery
,
2021
. - S. 1289-1302
ISBN 978-1-4503-8343-1
DOI: https://doi.org/10.1145/3448016.3457300
Abstract
Distributed systems that manage and process graph-structured data internally solve a graph partitioning problem to minimize their communication overhead and query run-time. Besides computational complexity---optimal graph partitioning is NP-hard---another important consideration is the memory overhead. Real-world graphs often have an immense size, such that loading the complete graph into memory for partitioning is not economical or feasible. Currently, the common approach to reduce memory overhead is to rely on streaming partitioning algorithms. While the latest streaming algorithms lead to reasonable partitioning quality on some graphs, they are still not completely competitive to in-memory partitioners. In this paper, we propose a new system, Hybrid Edge Partitioner (HEP), that can partition graphs that fit partly into memory while yielding a high partitioning quality. HEP can flexibly adapt its memory overhead by separating the edge set of the graph into two sub-sets. One sub-set is partitioned by NE++, a novel, efficient in-memory algorithm, while the other sub-set is partitioned by a streaming approach. Our evaluations on large real-world graphs show that in many cases, HEP outperforms both in-memory partitioning and streaming partitioning at the same time. Hence, HEP is an attractive alternative to existing solutions that cannot fine-tune their memory overheads. Finally, we show that using HEP, we achieve a significant speedup of distributed graph processing jobs on Spark/GraphX compared to state-of-the-art partitioning algorithms.
Weitere Angaben
| Publikationsform: | Aufsatz in einem Buch |
|---|---|
| Begutachteter Beitrag: | Ja |
| Institutionen der Universität: | Fakultäten Fakultäten > Fakultät für Mathematik, Physik und Informatik Fakultäten > Fakultät für Mathematik, Physik und Informatik > Institut für Informatik > Lehrstuhl Data Systems Fakultäten > Fakultät für Mathematik, Physik und Informatik > Institut für Informatik > Lehrstuhl Data Systems > Lehrstuhl Data Systems - Univ.-Prof. Dr. Ruben Mayer Fakultäten > Fakultät für Mathematik, Physik und Informatik > Institut für Informatik |
| Titel an der UBT entstanden: | Nein |
| Themengebiete aus DDC: | 000 Informatik,Informationswissenschaft, allgemeine Werke > 004 Informatik |
| Eingestellt am: | 25 Apr 2023 13:23 |
| Letzte Änderung: | 05 Feb 2024 07:34 |
| URI: | https://eref.uni-bayreuth.de/id/eprint/76039 |