Publicação: Compact data structures for the metric suffix array
Carregando...
Tipo do documento
Data
Direito de acesso
Área do conhecimento
CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Título da Revista
ISSN da Revista
Título de Volume
Autores
Orientador
Coorientador
Louza, Felipe Alves da
Resumo
Approximate similarity searching has been used in several disciplines such as pattern recognition and machine learning, and applications such as image, strings and genome searches. Generally, these activities deal with a large volume of high-dimensional data, with both the execution time of the searches and the size of the memory allocated by the data structure that responds to these searches being relevant. The approximate similarity searching is carried out using reference elements, which establish a compromise between the level of precision of the searches and the time required and allocated memory. Using this technique, we propose a structure that operates approximate similarity searching with a compact data structure that still presents a linear cost for construction and search, and that is not limited to 32-bit data. With the experiments executed, we managed to obtain a method that requires less memory, achieving 1/3 of the memory required for the MSA, at the cost of an increase in construction and search time, demanding 2.7 and 3.5 the time required for the MSA respectively in the best case.
Abstract
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. 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.
Palavras-chave
Busca por similaridade, Similarity searching, Estrutura de dados compacta, Compact data structures, Vetor de sufixos métrico, Metric Suffix Array
Citação
ROSA, Frederico Rezende. Compact data structures for the Metric Suffix Array. 2024. 54 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Uberlândia, Uberlândia, 2024. DOI 10.14393/ufu.di.2023.656.
Avaliação
Revisão
Suplementado Por
Referenciado Por
Licença Creative Commons
Exceto quando indicado de outra forma, a licença deste item é descrita como Acesso Aberto