Vi studerar problemet med att implementera grafalgoritmer effektivt på Pregel-liknande system, vilket kan vara förvånansvärt utmanande. Standardgrafikalgoritmer i denna inställning kan medföra onödiga ineffektiviteter såsom långsam konvergens eller höga kommunikations- eller beräkningskostnader, vanligtvis på grund av strukturella egenskaper hos indatagrafik såsom stora diametrar eller skev i komponentstorlekar. Vi beskriver flera optimeringstekniker för att ta itu med dessa ineffektiviteter. Vår mest generella teknik är baserad på idén att utföra en serieberäkning på en liten del av indatagrafen, vilket kompletterar Pregels vertex-centrerade parallellism. Vi baserar vår studie på grundliga implementationer av flera grundläggande grafalgoritmer, varav några, såvitt vi vet, inte har implementerats på Pregelliknande system tidigare. Algoritmerna och optimeringarna som vi beskriver är helt implementerade i vår implementering av Pregel med öppen källkod. Vi presenterar detaljerade experiment som visar att våra optimeringsmetoder förbättrar körtiden avsevärt på en mängd mycket stora grafdataset.
Baserat på Pregel, Frequent Subgraph Mining Baserat på Pregel 3 algoritmiska optimeringar undersöks REF.
Optimizing Graph Algorithms on Pregel-like Systems
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}