EUVIMEDEUVIMED entdecken
Crossref

Triparts: Scalable Streaming Graph Partitioning to Enhance Community Structure

Ruchi Bhoot, Tuhin Khare, Manoj Agarwal, Siddharth Jaiswal, Yogesh Simmhan

Proceedings of the VLDB Endowment · 2025-05 · 18 (9) · 2992-3006

DOI: 10.14778/3746405.3746423 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 03.09.2025. Verfasst von Ruchi Bhoot und 4 weiteren Autor:innen. Die Arbeit wurde bisher 5-mal zitiert (Crossref) und nennt 93 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

k-way edge based partitioning algorithms for processing large streaming graphs, such as social networks and web crawls, assign each arriving edge to one of the k partitions. This can result in vertices being replicated on multiple partitions. Typically, such partitioning algorithms aim to balance the edge counts across partitions while minimizing the vertex replication. However, such objectives ignore the community structure inherently embedded in the graph, which is an important quality metric for clustering and graph mining applications that subsequently operate on the partitions. To address this gap, we propose a novel optimization goal to maximize the number of local triangles in the partitions as an additional objective. Triangle count is an effective metric to measure the conservation of community structure. Further, we propose TriParts a family of heuristics for online partitioning over an edge stream. They use three complementary state data structures: Bloom Filters, Triangle Map and High degree Map. Each state adds tangible value to meet our objectives. We validate TriParts on six diverse real world graphs with up to 1.6B edges and varying triangle densities. Our best heuristic outperforms the state-of-the-art DBH and HDRF streaming graph partitioners on the triangle-count metric by up to 4–8.3x while maintaining competitive vertex replication factor and edge-balancing. We achieve an ingest rate of 500k edges/sec on a 16 node cluster. We also offer detailed results on the configuration parameters, scalability and overheads of TriParts, and its practical benefits for distributed graph analytics.

Zitieren

APA

Bhoot, R., Khare, T., Agarwal, M., Jaiswal, S., & Simmhan, Y. (2025). Triparts: Scalable Streaming Graph Partitioning to Enhance Community Structure. Proceedings of the VLDB Endowment, 18(9), 2992-3006. https://doi.org/10.14778/3746405.3746423

Vancouver

Bhoot R, Khare T, Agarwal M, Jaiswal S, Simmhan Y. Triparts: Scalable Streaming Graph Partitioning to Enhance Community Structure. Proceedings of the VLDB Endowment. 2025;18(9):2992-3006. doi:10.14778/3746405.3746423

BibTeX
@article{Bhoot2025,
  author = {Bhoot, Ruchi and Khare, Tuhin and Agarwal, Manoj and Jaiswal, Siddharth and Simmhan, Yogesh},
  title = {Triparts: Scalable Streaming Graph Partitioning to Enhance Community Structure},
  journal = {Proceedings of the VLDB Endowment},
  year = {2025},
  volume = {18},
  number = {9},
  pages = {2992--3006},
  doi = {10.14778/3746405.3746423}
}
Kostenlos starten →