bei Google ScholarTitelangaben
Mayer, Christian ; Mayer, Ruben ; Tariq, Muhammad Adnan ; Geppert, Heiko ; Laich, Larissa ; Rieger, Lukas ; Rothermel, Kurt:
ADWISE : Adaptive window-based streaming edge partitioning for high-speed graph processing.
In:
2018 IEEE 38th International Conference on Distributed Computing Systems. -
Piscataway, NJ
: IEEE
,
2018
. - S. 685-695
ISBN 978-1-5386-6871-9
DOI: https://doi.org/10.1109/ICDCS.2018.00072
Abstract
In recent years, the graph partitioning problem gained importance as a mandatory preprocessing step for distributed graph processing on very large graphs. Existing graph partitioning algorithms minimize partitioning latency by assigning individual graph edges to partitions in a streaming manner - at the cost of reduced partitioning quality. However, we argue that the mere minimization of partitioning latency is not the optimal design choice in terms of minimizing total graph analysis latency, i.e., the sum of partitioning and processing latency. Instead, for complex and long-running graph processing algorithms that run on very large graphs, it is beneficial to invest more time into graph partitioning to reach a higher partitioning quality - which drastically reduces graph processing latency. In this paper, we propose ADWISE, a novel window-based streaming partitioning algorithm that increases the partitioning quality by always choosing the best edge from a set of edges for assignment to a partition. In doing so, ADWISE controls the partitioning latency by adapting the window size dynamically at run-time. Our evaluations show that ADWISE can reach the sweet spot between graph partitioning latency and graph processing latency, reducing the total latency of partitioning plus processing by up to 23-47 percent compared to the state-of-the-art.
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: | 26 Apr 2023 09:08 |
| Letzte Änderung: | 05 Feb 2024 07:37 |
| URI: | https://eref.uni-bayreuth.de/id/eprint/76028 |