Kontinuerlig bearbetning av en strömmande graf upprätthåller ett ungefärligt resultat av den iterativa beräkningen på en ny version av grafen. Vid en användarfråga kan det exakta resultatet på den aktuella grafen snabbt beräknas genom att mata de ungefärliga resultaten till den iterativa beräkningen - en form av inkrementell beräkning som korrigerar (liten mängd) fel i det ungefärliga resultatet. Trots effektiviteten i denna metod vid bearbetning av växande grafer, är det i allmänhet inte tillämpligt när kantradering förekommer - befintliga approximationer kan leda till antingen felaktiga resultat (t.ex. monotona beräkningar avslutas vid en felaktig minima/maxima) eller dålig prestanda (t.ex. med approximationer, konvergens tar längre tid än att utföra beräkningen från grunden). Detta papper presenterar KickStarter, en runtime teknik som kan trimma ungefärliga värden för en delmängd av hörn som påverkas av de borttagna kanterna. Den trimmade approximen är både säker och lönsam, vilket gör det möjligt för beräkningen att producera korrekta resultat och konvergera snabbt. KickStarter fungerar för en klass av monotona grafalgoritmer och kan enkelt införlivas i alla befintliga strömmande grafsystem. Våra experiment med fyra strömmande algoritmer på fem stora grafer visar att trimning inte bara ger korrekta resultat utan också accelererar dessa algoritmer med 8,5-23,7×.
KickStarter REF visar att trimning av ungefärliga värden effektivt kan leda till korrekta resultat också när kantradering sker.
KickStarter: Fast and Accurate Computations on Streaming Graphs via Trimmed Approximations
{'venue': "ASPLOS '17", 'journal': None, 'mag_field_of_study': ['Computer Science']}