CRACS/INESC TEC com artigo premiado

Pedro Ribeiro e Fernando Silva, colaboradores do Centro de Investigação em Sistemas Computacionais Avançados (CRACS) do INESC TEC, viram um artigo da sua autoria a ser premiado com o Best Paper Award no âmbito do DBSocial 2012 - ACM SIGMOD Workshop on Databases and Social Networks, que se realizou no passado mês de maio.

O artigo, intitulado “Querying Subgraph Sets with G-Tries”, explora a utilização de uma estrutura de dados criada originalmente no âmbito do doutoramento de Pedro Ribeiro, as G-Tries, na busca de padrões em redes complexas. Em particular, este artigo mostra como as ‘g-tries’ podem ser usadas para, de forma muito eficiente, procurar um conjunto geral de padrões de qualquer tamanho (subgrafos) numa qualquer outra rede (um grafo "grande" que pode conter muitas ocorrências dos subgrafos desejados).

A procura de padrões tem aplicações diversificadas, nomeadamente na comparação de redes. Por exemplo, se imaginarmos dois grupos de redes biológicas cerebrais, uma descrevendo um cérebro são e outra descrevendo um cérebro doente (por exemplo com epilepsia ou com Alzheimer), esta procura permite identificar os padrões que melhor distinguem e caracterizam estes dois grupos.

Os resultados experimentais obtidos mostram que o algoritmo desenvolvido tem uma performance substancialmente melhor que todos os algoritmos existentes atualmente para o efeito, obtendo tempos de uma a duas ordens de magnitude mais rápidos que os algoritmos concorrentes.