Detta papper introducerar en dynamisk graf partitionering algoritm, utformad för stora, ständigt ändra grafer. Vi föreslår ett partitioneringsramverk som anpassar sig i farten när grafstrukturen ändras. Vi introducerar också en replikalgoritm som är tätt integrerad med partitioneringsalgoritmen, vilket ytterligare minskar antalet kanter som skärs av partitioneringsalgoritmen. Även om det föreslagna tillvägagångssättet är handikappat genom att endast ta hänsyn till lokala delar av grafen vid omfördelningen av hörn, visar en omfattande utvärdering att det föreslagna tillvägagångssättet upprätthåller en kvalitetspartitionering över tid, vilket är jämförbart när som helst med att utföra en fullständig partitionering från grunden med hjälp av en toppmodern statisk grafpartitioneringsalgoritm som METIS. Dessutom, när vertex replikation är påslagen, kan kant-cut förbättras genom en storleksordning.
Leopard REF föreslår en partitioneringsalgoritm och en tätt integrerad replikeringsalgoritm för storskaliga, ständigt föränderliga grafer.
LEOPARD: Lightweight Edge-Oriented Partitioning and Replication for Dynamic Graphs
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}