English

CIn - Centro de Informática UFPE




Eventos Relacionados

Defesa de Dissertação de Mestrado Nº1.673 "Representações Cache Eficientes para Índices baseados em Wavelet Trees"

O aluno Israel Batista Freitas da Silva irá defender sua pesquisa no dia 12 de dezembro às 9h, no Auditório Início: 12/12/2016 às 09:00 Término: 12/12/2016 às 00:00 Local: Auditório do CIn

 Pós-Graduação em Ciência da Computação – UFPE
Defesa de Dissertação de Mestrado Nº 1.673   
 
Aluno: Israel Batista Freitas da Silva
Orientador: Prof. Paulo Gustavo Soares da Fonseca
Título: Representações Cache Eficientes para Índices baseados em Wavelet Trees
Data:  12/12/2016
Hora/Local:  9h – Centro de Informática - Auditório
Banca Examinadora:
Prof.  Katia Silva Guimarães (CIn / UFPE)
Prof. Marco Cesar Goldbarg  (Deptº de Informática e Matemática Aplicada – UFRN)
Prof.  Paulo Gustavo Soares da Fonseca (CIn / UFPE)
 
 
RESUMO:
 
Hoje em dia, há um exponencial crescimento do volume de informação no mundo. Esta
explosão cria uma demanda por técnicas mais eficientes de indexação e consulta de dados, uma vez que, para serem úteis, eles precisarão ser manipuláveis. Casamento de padrões se refere à busca de um texto menor (padrão) em um texto muito maior (texto), reportando a quantidade de ocorrências e/ou as localizações das ocorrências. Para tal, pode-se construir uma estrutura chamada índice que pré-processará o texto e permitirá que consultas sejam feitas eficientemente. A eficiência prática de um índice, além da sua eficiência teórica, pode definir o quão utilizado ele será, e isto está diretamente ligado a como ele se comporta nas arquiteturas dos computadores atuais. O principal objetivo deste estudo é analisar o uso da estrutura Wavelet Tree como índice avaliando o impacto da reorganização interna dos seus dados quanto à localidade espacial e, assim propor formas de organização que reduzam efetivamente a quantidade de cache misses ocorridos na execução de operações neste índice. Através de análises empíricas com dados simulados e dados textuais obtidos de dois repositórios públicos, avaliou-se alguns aspectos de cinco tipos de organizações para os dados da estrutura com o objetivo de compará-las quanto ao tempo de execução e quantidade de cache misses ocorridos. Adicionalmente, uma análise teórica da complexidade da quantidade de cache misses ocorridos para operação de consulta de um padrão é descrita para uma das organizações propostas. Dois experimentos realizados sugerem comportamentos assintóticos para duas das organizações analisadas. Um terceiro experimento executado mostra que, para quatro das cinco organizações apresentadas, houve uma sistemática redução na quantidade de cache misses ocorridos para a cache de menor nível. Entretanto a redução de cache misses para cache de menor nível não se refletiu integralmente numa diferença no tempo de execução das operações, tendo sido esta menos significativa, nem na quantidade de cache misses ocorridos na cache de maior nível, onde houveram variações positivas e negativas. Os resultados obtidos permitem concluir que a escolha de uma representação adequada pode acarretar numa melhora significativa de utilização da cache. Diferentemente do modelo teórico, o custo de acesso à memória responde apenas por uma fração do tempo de computação das operações sobre as Wavelet Trees, pelo que a diminuição no número de cache misses não se traduziu integralmente no tempo de execução. No entanto, este fator pode ser crítico em situações mais extremas de utilização de memória.
 
PALAVRAS-CHAVE: Algoritmos, Análise de Algoritmos, Casamento de Padrões, Entropia, Estrutura
de Dados, Indexação de Textos, Índices de Texto Completo, Wavelet Tree.
  • © Centro de Informática UFPE - Todos os direitos reservados
    Tel +55 81 2126.8430 - Cidade Universitária - 50740-560 - Recife/PE
Plano4 Consultoria Web