Estruturas de Dados Compactas para o Vetor de Sufixos Métrico
Publicado: 21/12/2023 - 16:06
Última modificação: 18/01/2024 - 10:25
Linha de pesquisa: Ciência de Dados
Resumo: A busca por similaridade aproximada tem sido usada em diversas disciplinas, como reconhecimento de padrões e aprendizado de máquina, e em aplicações como buscas de imagens, strings e genoma. Geralmente, essas atividades lidam com um grande volume de dados de alta dimensão, sendo relevantes tanto o tempo de execução das buscas quanto o tamanho da memória alocada pela estrutura de dados que responde a essas buscas. A busca por similaridade aproximada é realizada por meio de elementos de referência, que estabelecem um compromisso entre o nível de precisão das buscas e o tempo necessário e memória alocada. Utilizando esta técnica, propomos uma estrutura que opera busca por similaridade aproximada com uma estrutura de dados compacta que ainda apresenta um custo linear para construção e busca, e que não se limita a dados de 32 bits. Após vários experimentos, conseguimos obter um método que requer menos memória ao custo de um aumento no tempo de construção e busca.
Defesa híbrida, parte será realizada no bloco 1B, sala 1B132