Incremental Streaming Graph Partitioning
| Autor: | Lisa J. K. Durbeck, Peter Athanas |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Speedup
Computer science Spectral graph theory Graph partition 0102 computer and information sciences Parallel computing LOBPCG 01 natural sciences Partition (database) 010201 computation theory & mathematics 0103 physical sciences Graph (abstract data type) 010306 general physics Cluster analysis Block (data storage) |
| Zdroj: | HPEC |
| DOI: | 10.1109/hpec43674.2020.9286181 |
| Popis: | Graph partitioning is an NP-hard problem whose efficient approximation has long been a subject of interest. The I/O bounds of contemporary computing environments favor incremental or streaming graph partitioning methods. Methods have sought a balance between latency, simplicity, accuracy, and memory size. In this paper, we apply an incremental approach to streaming partitioning that tracks changes with a lightweight proxy to trigger partitioning as the clustering error increases. We evaluate its performance on the DARPA/MIT Graph Challenge streaming stochastic block partition dataset, and find that it can dramatically reduce the invocation of partitioning, which can provide an order of magnitude speedup. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|