"Sviluppare" è la parola importante qui, poiché la ricerca copre gli algoritmi di affinamento su set di dati sintetici piuttosto che su big data reali.
"I grafici sono ampiamente utilizzati per rappresentare e analizzare oggetti del mondo reale in molti domini come i social network, la business intelligence, la biologia e le neuroscienze", ha affermato Kaist. “Quando si sviluppano e si testano algoritmi per un grafico su larga scala, di solito viene utilizzato un grafico sintetico invece di un grafico reale. Questo perché la condivisione e l'utilizzo di grafici reali su larga scala è molto limitato perché sono proprietari o sono praticamente impossibili da raccogliere ".
Convenzionalmente, secondo Kaist, lo sviluppo e il test di algoritmi di grafi avviene tramite il seguente approccio in due fasi:
Il primo passo genera un grafico sintetico e lo memorizza su dischi. Il grafico è solitamente generato dalla generazione basata su parametri o dall'up-scaling del grafico: il primo estrae un piccolo numero di parametri che possono catturare alcune proprietà di un dato grafico reale e genera il grafico sintetico con i parametri, il secondo ingrandisce un dato grafico reale a uno più grande in modo da preservare il più possibile le proprietà del grafico reale originale.
Il secondo passaggio carica il grafico memorizzato nella memoria principale di un motore di elaborazione di grafici, come Apache GraphX, ed esegue un determinato algoritmo di grafico sul motore. "Poiché il grafico è troppo grande per essere contenuto nella memoria principale di un singolo computer, il motore grafico in genere viene eseguito su un cluster di diverse decine o centinaia di computer", ha affermato Kaist, "pertanto il costo dell'approccio convenzionale a due fasi è elevato . "
Il team coreano non genera e memorizza un grafico sintetico su larga scala.
Invece, carica il piccolo grafico reale iniziale nella memoria principale. Quindi, utilizzando una tecnica denominata T-GPS (simulazione di elaborazione del grafico su scala trilioni), l'algoritmo del grafico confrontato con il piccolo grafico reale come se il grafico sintetico su larga scala che dovrebbe essere generato dal grafico reale esistesse nella memoria principale, ha detto Kaist , aggiungendo che dopo aver eseguito l'algoritmo, T-GPS restituisce lo stesso risultato dell'approccio convenzionale in due fasi.
"L'idea chiave di T-GPS è generare solo la parte del grafico sintetico a cui l'algoritmo deve accedere al volo e modificare il motore di elaborazione del grafico per riconoscere la parte generata al volo come la parte del grafico sintetico effettivamente generata, "Disse Kaist.
T-GPS ha elaborato un grafico di un trilione di bordi su un computer, mentre l'approccio convenzionale in due fasi richiedeva un cluster di undici computer con le stesse specifiche per elaborare un grafico di un miliardo di bordi. Non avendo bisogno dell'accesso alla rete, il T-GPS era fino a 43 volte più veloce dell'approccio convenzionale che ha un notevole sovraccarico di comunicazione.
Il lavoro è stato presentato alla conferenza IEEE ICDE 2021 come "Simulazione di elaborazione di grafici su scala trilioni basata sull'upscaling del grafico dall'alto verso il basso".