Maskininlärningsalgoritmer används i stor utsträckning idag för analytiska uppgifter som datarengöring, datakategorisering eller datafiltrering. Samtidigt motiverar ökningen av sociala medier den senaste tidens införande i storskalig grafbearbetning. Båda algoritmkategorierna domineras av iterativa deluppgifter, dvs. bearbetningssteg som utförs repetitivt tills ett konvergensvillkor är uppfyllt. Optimering kluster resurstilldelningar bland flera arbetsbelastningar av iterativa algoritmer motiverar behovet av att uppskatta sin körtid, vilket i sin tur kräver: i) förutsäga antalet iterationer, och ii) förutsäga bearbetningstiden för varje iteration. Eftersom båda parametrarna är beroende av datauppsättningens egenskaper och konvergensfunktionen är det svårt att uppskatta deras värden innan de genomförs. I detta dokument föreslås PRIDICT, en experimentell metod för att förutsäga drifttiden för iterativa algoritmer. PRIDICT använder provkörningar för att fånga algoritmens konvergenstrend och per-itering viktiga indatafunktioner som är väl korrelerade med de faktiska bearbetningskraven för den fullständiga indatauppsättningen. Med hjälp av denna kombination av egenskaper förutsäger vi körtiden för iterativa algoritmer, inklusive algoritmer med mycket olika runtime mönster bland efterföljande iterationer. Vår experimentella utvärdering av flera algoritmer på skalfria grafer visar en relativ förutsägelse fel på 10%-30% för att förutsäga körtid, inklusive algoritmer med upp till 100x runtime variabilitet bland på varandra följande iterationer.
Popescu m.fl. I REF föreslogs en metod för att förutsäga körtiden för en klass av storskaliga iterativa algoritmer.
PREDIcT: Towards Predicting the Runtime of Large Scale Iterative Analytics
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}