O cientista da computação Julian Shun estuda esses tipos de conexões multifacetadas, porém muitas vezes invisíveis, usando grafos, nos quais objetos são representados como pontos, ou vértices, e as relações entre eles são modeladas por segmentos de linha, ou arestas.
Shun, um novo professor associado titular no Departamento de Engenharia Elétrica e Ciência da Computação, desenvolve algoritmos de grafos que podem ser usados para encontrar o caminho mais curto entre as casas na rota do motorista de entrega ou detectar transações fraudulentas feitas por agentes maliciosos em uma rede financeira.
Com o aumento do volume de dados, essas redes passaram a incluir bilhões ou até trilhões de objetos e conexões. Para encontrar soluções eficientes, Shun constrói algoritmos de alto desempenho que utilizam a computação paralela para analisar rapidamente até mesmo os grafos mais enormes. Como a programação paralela é notoriamente difícil, ele também desenvolve frameworks de programação amigáveis que facilitam para outros escreverem seus próprios algoritmos de grafos eficientes.
“Se você está procurando algo em um mecanismo de busca ou em uma rede social, você quer obter seus resultados muito rapidamente. Se você está tentando identificar transações financeiras fraudulentas em um banco, você quer fazer isso em tempo real para minimizar os danos. Algoritmos paralelos podem acelerar as coisas usando mais recursos computacionais”, explica Shun, que também é investigador principal no Laboratório de Ciência da Computação e Inteligência Artificial (CSAIL).
Esses algoritmos são frequentemente usados em sistemas de recomendação online. Procure por um produto em um site de e-commerce e é provável que você rapidamente veja uma lista de itens relacionados que também poderia adicionar ao seu carrinho. Essa lista é gerada com a ajuda de algoritmos de grafos que aproveitam o paralelismo para encontrar rapidamente itens relacionados em uma rede massiva de usuários e produtos disponíveis.
Conexões no Campus
Quando adolescente, a única experiência de Shun com computadores foi uma aula de ensino médio sobre construção de sites. Mais interessado em matemática e ciências naturais do que em tecnologia, ele pretendia se formar em uma dessas áreas quando se matriculou como graduando na Universidade da Califórnia em Berkeley.
Mas durante seu primeiro ano, um amigo recomendou que ele fizesse uma aula de introdução à ciência da computação. Embora não soubesse o que esperar, ele decidiu se inscrever.
“Me apaixonei pela programação e pelo design de algoritmos. Mudei para ciência da computação e nunca mais olhei para trás”, lembra.
Essa aula inicial de ciência da computação era autodidata, então Shun aprendeu a maior parte do material sozinho. Ele gostava dos aspectos lógicos de desenvolver algoritmos e do ciclo curto de feedback dos problemas de ciência da computação. Shun podia inserir suas soluções no computador e imediatamente ver se estava certo ou errado. E os erros nas soluções erradas o guiariam para a resposta certa.
“Sempre achei divertido construir coisas, e na programação, você está construindo soluções que fazem algo útil. Isso me atraiu”, acrescenta.
Depois de se formar, Shun passou um tempo na indústria, mas logo percebeu que queria seguir uma carreira acadêmica. Em uma universidade, ele sabia que teria a liberdade de estudar problemas que o interessavam.
Adentrando nos Grafos
Ele se matriculou como estudante de pós-graduação na Universidade Carnegie Mellon, onde focou sua pesquisa em algoritmos aplicados e computação paralela.
Como graduando, Shun havia feito aulas de algoritmos teóricos e cursos práticos de programação, mas os dois mundos não se conectavam. Ele queria conduzir pesquisas que combinassem teoria e aplicação. Algoritmos paralelos eram o encaixe perfeito.
“Na computação paralela, você precisa se importar com aplicações práticas. O objetivo da computação paralela é acelerar as coisas na vida real, então, se seus algoritmos não são rápidos na prática, eles não são tão úteis”, diz.
Em Carnegie Mellon, ele foi apresentado a conjuntos de dados de grafos, nos quais objetos em uma rede são modelados como vértices conectados por arestas. Ele se sentiu atraído pelas muitas aplicações desses tipos de conjuntos de dados e pelo desafiador problema de desenvolver algoritmos eficientes para lidar com eles.
Após concluir um estágio pós-doutoral em Berkeley, Shun buscou uma posição docente e decidiu se juntar ao MIT. Ele havia colaborado com vários membros do corpo docente do MIT em pesquisas de computação paralela e estava entusiasmado em se juntar a um instituto com tamanha amplitude de expertise.
Em um de seus primeiros projetos após ingressar no MIT, Shun uniu forças com o professor do Departamento de Engenharia Elétrica e Ciência da Computação e membro do CSAIL Saman Amarasinghe, especialista em linguagens de programação e compiladores, para desenvolver um framework de programação para processamento de grafos conhecido como GraphIt. O framework fácil de usar, que gera código eficiente a partir de especificações em alto nível, teve um desempenho cerca de cinco vezes mais rápido do que a abordagem seguinte mais eficaz.
“Foi uma colaboração muito frutífera. Eu não teria criado uma solução tão poderosa se tivesse trabalhado sozinho”, diz.
Shun também expandiu seu foco de pesquisa para incluir algoritmos de clusterização, que buscam agrupar pontos de dados relacionados. Ele e seus alunos desenvolvem algoritmos paralelos e frameworks para resolver rapidamente problemas de clusterização complexos, que podem ser usados para aplicações como detecção de anomalias e detecção de comunidades.
Problemas Dinâmicos
Recentemente, ele e seus colaboradores têm se concentrado em problemas dinâmicos nos quais os dados em uma rede de grafos mudam ao longo do tempo.
Quando um conjunto de dados tem bilhões ou trilhões de pontos de dados, executar um algoritmo do zero para fazer uma pequena mudança pode ser extremamente caro do ponto de vista computacional. Ele e seus alunos projetam algoritmos paralelos que processam muitas atualizações ao mesmo tempo, melhorando a eficiência ao mesmo tempo que preservam a precisão.
Mas esses problemas dinâmicos também representam um dos maiores desafios que Shun e sua equipe precisam superar. Como não há muitos conjuntos de dados dinâmicos disponíveis para testar algoritmos, a equipe muitas vezes precisa gerar dados sintéticos que podem não ser realistas e podem prejudicar o desempenho de seus algoritmos no mundo real.
No final, seu objetivo é desenvolver algoritmos de grafos dinâmicos que funcionem de forma eficiente na prática, ao mesmo tempo que mantêm garantias teóricas. Isso garante que eles serão aplicáveis em uma ampla gama de contextos, diz ele.
Shun espera que os algoritmos paralelos dinâmicos tenham um foco ainda maior de pesquisa no futuro. À medida que os conjuntos de dados continuam a se tornar maiores, mais complexos e mais rapidamente mutantes, os pesquisadores precisarão desenvolver algoritmos mais eficientes para acompanhar.
Ele também espera que novos desafios surjam a partir dos avanços na tecnologia da computação, uma vez que os pesquisadores precisarão projetar novos algoritmos para aproveitar as propriedades de hardware inovador.
“Essa é a beleza da pesquisa – eu posso tentar resolver problemas que outras pessoas não resolveram antes e contribuir com algo útil para a sociedade”, diz.
Redação Confraria Tech.
Referências:
Modeling relationships to solve complex problems efficiently
