Compact data structures for the metric suffix array
Frederico Rosa · 2024
AgradecimentosÀ Capes, CNPq (CNPQ Universal 406418/2021-7) e FAPEMIG que possibilitaram a realização do projeto no qual este trabalho está inserido. ResumoA 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.Realizado os experimentos, conseguimos obter um método que requer menos memória, atingindo 1/3 da mémoria requerida pelo método MSA, ao custo de um aumento no tempo de construção e busca, demandando até 2,7 e 3,5 o tempo do MSA respectivamente no melhor caso.