Skip navigation
Please use this identifier to cite or link to this item: https://repositorio.ufpe.br/handle/123456789/21050
Title: Representações cache eficientes para índices baseados em Wavelet trees
Authors: SILVA, Israel Batista Freitas da
Keywords: Algoritmos. Análise de Algoritmos. Casamento de Padrões. Entropia. Estrutura de Dados. Indexação de Textos. Índices de Texto Completo. WaveletTree.;Algorithms. Analysis of Algorithms. Pattern Matching. Entropy. Data Structures. Text Indexing. Full Text Indexes. WaveletTree.
Issue Date: 12-Dec-2016
Publisher: Universidade Federal de Pernambuco
Abstract: Hojeemdia,háumexponencialcrescimentodovolumedeinformaçãonomundo. Estaexplosão cria uma demanda por técnicas mais eficientes de indexação e consulta de dados, uma vez que, paraseremúteis,elesprecisarãosermanipuláveis. Casamentodepadrõesserefereàbuscadeum 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. OprincipalobjetivodesteestudoéanalisarousodaestruturaWaveletTreecomoíndiceavaliando 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 decachemisses 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 decachemisses 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. Diferentementedomodeloteórico,ocustodeacessoàmemóriarespondeapenasporumafração dotempodecomputaçãodasoperaçõessobreasWaveletTrees,peloqueadiminuiçãononú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.
URI: https://repositorio.ufpe.br/handle/123456789/21050
Appears in Collections:Dissertações de Mestrado - Ciência da Computação

Files in This Item:
File Description SizeFormat 
Israel Batista Freitas da Silva.pdf1.4 MBAdobe PDFView/Open


This item is protected by original copyright



This item is licensed under a Creative Commons License Creative Commons