'Desenvolver' é a palavra importante aqui, já que a pesquisa cobre o aprimoramento de algoritmos em conjuntos de dados sintéticos, em vez de em big data reais.
“Os gráficos são amplamente usados para representar e analisar objetos do mundo real em muitos domínios, como redes sociais, business intelligence, biologia e neurociência”, disse Kaist. “Ao desenvolver e testar algoritmos para um gráfico em grande escala, um gráfico sintético é geralmente usado em vez de um gráfico real. Isso ocorre porque o compartilhamento e a utilização de gráficos reais em grande escala são muito limitados devido ao fato de serem proprietários ou praticamente impossíveis de coletar. ”
Convencionalmente, de acordo com Kaist, desenvolver e testar algoritmos de gráfico é feito por meio da seguinte abordagem de duas etapas:
A primeira etapa gera um gráfico sintético e o armazena em discos. O gráfico é geralmente gerado por geração baseada em parâmetros ou aumento de escala do gráfico - o primeiro extrai um pequeno número de parâmetros que podem capturar algumas propriedades de um dado gráfico real e gera o gráfico sintético com os parâmetros, o último aumenta a escala de um dado um gráfico real para um maior, de modo a preservar as propriedades do gráfico real original tanto quanto possível.
A etapa dois carrega o gráfico armazenado na memória principal de um mecanismo de processamento de gráfico, como o Apache GraphX, e executa um determinado algoritmo de gráfico no mecanismo. “Como o gráfico é muito grande para caber na memória principal de um único computador, o motor gráfico normalmente é executado em um cluster de várias dezenas ou centenas de computadores”, disse Kaist, “portanto, o custo da abordagem convencional de duas etapas é alto . ”
A equipe coreana não gera e armazena um gráfico sintético em grande escala.
Em vez disso, ele carrega o pequeno gráfico real inicial na memória principal. Então, usando uma técnica batizada de T-GPS (simulação de processamento de gráfico em escala de trilhões), o algoritmo de gráfico confrontado com o pequeno gráfico real como se o gráfico sintético de grande escala que deveria ser gerado a partir do gráfico real existisse na memória principal, disse Kaist. , acrescentando que, após a conclusão do algoritmo, o T-GPS retorna o mesmo resultado que a abordagem convencional de duas etapas.
“A ideia principal do T-GPS é gerar apenas a parte do gráfico sintético que o algoritmo precisa acessar em tempo real e modificar o mecanismo de processamento de gráfico para reconhecer a parte gerada instantaneamente como a parte do gráfico sintético realmente gerado, ”Disse Kaist.
O T-GPS processou um gráfico de um trilhão de arestas em um computador, enquanto a abordagem convencional de duas etapas precisava de um cluster de onze computadores com a mesma especificação para processar um gráfico de um bilhão de arestas. Não necessitando de acesso à rede, o T-GPS foi até 43 vezes mais rápido do que a abordagem convencional, que possui uma sobrecarga de comunicação significativa.
O trabalho foi apresentado na conferência IEEE ICDE 2021 como 'Simulação de processamento de gráfico em escala trilhões baseada em aumento de escala de gráfico de cima para baixo'.