CUTTANA: Scalable Graph Partitioning for Faster Distributed Graph Databases and Analytics
Proceedings of the VLDB Endowment · 2024-09 · 18 (1) · 14-27
DOI: 10.14778/3696435.3696437 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 11.02.2025. Verfasst von Milad Rezaei Hajidehi und 2 weiteren Autor:innen. Die Arbeit wurde bisher 7-mal zitiert (Crossref) und nennt 61 Literaturangaben.
Abstract (Originalsprache)
Graph partitioning plays a pivotal role in various distributed graph processing applications, including graph analytics, graph neural network training, and distributed graph databases. A "good" graph partitioner reduces workload execution time, worker imbalance, and network overhead. Graphs that require distributed settings are often too large to fit in the main memory of a single machine. This challenge renders traditional in-memory graph partitioners infeasible, leading to the emergence of streaming solutions. Streaming partitioners produce lower-quality partitions, because they work from partial information and must make premature decisions before they have a complete view of a vertex's neighborhood. We introduce CUTTANA, a streaming graph partitioner that partitions massive graphs (Web/Twitter scale) with superior quality compared to existing streaming solutions. CUTTANA uses a novel buffering technique that prevents the premature assignment of vertices to partitions and a scalable coarsening and refinement technique that enables a complete graph view, improving the intermediate assignment made by a streaming partitioner. We implemented a parallel version for CUTTANA that offers nearly the same partitioning latency as existing streaming partitioners. Our experimental analysis shows that CUTTANA consistently yields better partitioning quality than state-of-the-art streaming vertex partitioners in terms of both edge-cut and communication volume metrics. We also evaluate the workload latencies that result from using CUTTANA and other partitioners in distributed graph analytics and databases. CUTTANA outperforms the other methods in most scenarios (algorithms, datasets). In analytics applications, CUTTANA improves runtime performance by up to 59% compared to various streaming partitioners (i.e., HDRF, Fennel, Ginger, HeiStream). In graph database tasks, CUTTANA results in higher query throughput by up to 23%, without hurting tail latency.
Zitieren
APA
Hajidehi, M. R., Sridhar, S., & Seltzer, M. (2024). CUTTANA: Scalable Graph Partitioning for Faster Distributed Graph Databases and Analytics. Proceedings of the VLDB Endowment, 18(1), 14-27. https://doi.org/10.14778/3696435.3696437
Vancouver
Hajidehi MR, Sridhar S, Seltzer M. CUTTANA: Scalable Graph Partitioning for Faster Distributed Graph Databases and Analytics. Proceedings of the VLDB Endowment. 2024;18(1):14-27. doi:10.14778/3696435.3696437
BibTeX
@article{Hajidehi2024,
author = {Hajidehi, Milad Rezaei and Sridhar, Sraavan and Seltzer, Margo},
title = {CUTTANA: Scalable Graph Partitioning for Faster Distributed Graph Databases and Analytics},
journal = {Proceedings of the VLDB Endowment},
year = {2024},
volume = {18},
number = {1},
pages = {14--27},
doi = {10.14778/3696435.3696437}
}
EUVIMED