Palestra - 24/07/2015 (sexta-feira)

S É R I E   D E   S E M I N Á R I O S   DO  GRUPO  CROSS
 
Sexta-feira, 24/07/2015, às 14:00 horas
Sala MDC1
Paulo Henrique de Oliveira
Mestrando em Ciência da Computação - UEL
 
MELHORANDO O DESEMPENHO DE MÉTODOS DE ACESSO MÉTRICOS DINÂMICOS COM PIVÔS ADICIONAIS LOCAIS E ANTECIPAÇÃO DE INFORMAÇÕES
 
Nos últimos anos, o crescimento do volume de dados complexos tem sido acelerado por constantes avanços tecnológicos em dispositivos eletrônicos. Neste trabalho, são considerados dados complexos quaisquer dados não representáveis por tipos tradicionais, como números, caracteres, datas e textos curtos. Dados multimídia, dados georreferenciados e séries temporais são exemplos dessa categoria de dados. A relação de ordem é uma propriedade que permite identificar qual elemento precede o outro, segundo algum critério, em cada par de elementos do domínio. Visto que estruturas de indexação tradicionais são baseadas nessa propriedade, elas não são adequadas para dados complexos. Entretanto, existem estruturas apropriadas para domínios complexos, como os Métodos de Acesso Métricos (MAMs). Há diversos MAMs relatados na literatura, categorizados de diferentes formas dependendo dos fatores que são levados em conta para estruturar os dados. Os fatores tipo de pivô e dinamicidade da estrutura estão diretamente relacionados um ao outro. Neste trabalho, pivôs são elementos que agem como representantes de certas regiões do espaço de busca e são usados para podar elementos irrelevantes durante a execução de consultas. Diz-se que um pivô é global quando todos os elementos do conjunto de dados são referenciados a ele, enquanto um pivô é local quando somente uma porção do conjunto de dados é referenciada a ele. Porque pivôs globais são referenciados por todo o conjunto de dados, eles têm um alto impacto no processo de poda de elementos irrelevantes, uma vez que um único pivô global pode ser usado para descartar uma grande quantidade de elementos irrelevantes. No entanto, MAMs baseados em pivôs globais podem ter sua dinamicidade comprometida pelo fato de eventuais atualizações relacionadas a pivôs precisarem ser propagadas por toda a estrutura. Pivôs locais, por outro lado, permitem que a manutenção ocorra localmente ao preço de um menor poder de poda. Nesse contexto, esta dissertação teve como alvo melhorar o desempenho de MAMs dinâmicos sem comprometer sua dinamicidade, uma vez que várias aplicações manipulam dados complexos online e, consequentemente, demandam índices dinâmicos e eficientes para serem bem-sucedidas. Este trabalho apresenta duas técnicas para aumentar o poder de poda de MAMs dinâmicos: (i) usar pivôs adicionais locais para reduzir cálculos de distância e (ii) antecipar informações de nós filhos para reduzir acessos a disco desnecessários. Ambas as técnicas foram aplicadas a um MAM dinâmico e extensivamente avaliadas sobre conjuntos de dados reais, reduzindo o tempo de execução em até mais de 50% para consultas por similaridade sobre conjuntos de dados com dimensionalidades e cardinalidades moderadas e altas.