2026-09-21T21:31:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26009 2026-09-05T19:34:18Z ddc:004 open_access

BuffCut: Prioritized Buffered Streaming Graph Partitioning Baumgärtner, Linus Chhabra, Adil Faraj, Marcelo Fonseca Schulz, Christian graph partitioning streaming online buffered prioritized partitioning Streaming graph partitioners enable resource-efficient and massively scalable partitioning, but one-pass assignment heuristics are highly sensitive to stream order and often yield substantially higher edge cuts than in-memory methods. We present BuffCut, a buffered streaming partitioner that narrows this quality gap, particularly when stream ordering is adversarial, by combining prioritized buffering with batch-wise multilevel assignment. BuffCut maintains a bounded priority buffer to delay poorly informed decisions and regulate the order in which nodes are considered for assignment. It incrementally constructs high-locality batches of configurable size by iteratively inserting the highest-priority nodes from the buffer into the batch, effectively recovering locality structure from the stream. Each batch is then assigned via a multilevel partitioning algorithm. Experiments on diverse real-world and synthetic graphs show that BuffCut consistently outperforms state-of-the-art buffered streaming methods. Compared to the strongest prioritized buffering baseline, BuffCut achieves 20.8% fewer edge cuts while running 2.9× faster and using 11.3× less memory. Against the next-best batched method, it reduces edge cut by 15.8% with only modest overheads of 1.8× runtime and 1.09× memory. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Linus Baumgärtner and Adil Chhabra and Marcelo Fonseca Faraj and Christian Schulz 2026 Is Part Of LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2026.5 urn:nbn:de:0030-drops-260097 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.5 eng https://creativecommons.org/licenses/by/4.0/legalcode