Publicação: Exploração do uso de short-term memory na construção de métodos de acesso métricos dinâmicos sobre a perspectiva de diferentes políticas de divisão de nós
Carregando...
Arquivos
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
Orientador
Coorientador
Resumo
Este trabalho propõe o desenvolvimento de uma nova abordagem utilizando uma estrutura
denominada short-term memory, para a construção de Métodos de Acesso Métricos
dinâmicos derivados da Slim-Tree. Deste modo, o objetivo é minimizar a sobreposição
das estruturas e, consequentemente, otimizar as operações de consulta por similaridade.
A estratégia para alcançar este objetivo, fundamenta-se em adiar o processo da indexação
para contabilizar no índice novos objetos com distâncias próximas. Além disso, foram
empregadas distintas políticas de divisão de nós, o que permitiu mensurar os impactos
destas no que refere-se a qualidade das estruturas resultantes, principalmente com relação
ao grau de sobreposição. Os novos métodos propostos foram avaliados por conjunto de
dados reais e sintéticos e comparados com MAM Slim-tree original. Os resultados dos
experimentos foram significativos com relação à qualidade das árvores resultantes o que,
consequentemente, impactou em melhor eficiência nas operações de consulta por similaridade,
ao reduzir significativamente o número de cálculos de distância, a quantidade de
acessos a páginas de disco e, consequentemente, o tempo de execução de consultas aos
k-vizinhos mais próximos.
Abstract
This work proposes the development of a new approach using a structure called shortterm
memory for the construction of dynamic MAMs derived from Slim-Tree. The goal is
to minimize the overlap of nodes in the structure and, consequently, to optimize similarity
queries. The strategy is based on postponing the indexing process to allow inserting, in
the same index entry, new objects with closer distances. In addition, different node split
policies were employed, which allowed to measure the impacts of these in what refers to
the quality of the resulting structures, mainly with respect to the degree of overlap. The
proposed new methods were evaluated by real and synthetic datasets and compared with
the original MAM Slim-tree. The results of the experiments were significant with respect
to the quality of the resulting trees, which consequently impacted on better efficiency in
similarity query operations, significantly reducing the number of distance calculations,
the number of disk page accesses and the execution time of k-nearest neighbors.
Palavras-chave
Computação, Recuperação da informação, Indexação, MAM dinâmicos, Busca por similaridade, Short-term memory, Dados Complexos, Políticas de divisão de nós, Dinamics MAMs, Similarity Search, Complex data, Policies of Division of Nodes
Citação
SOUSA, Régis Michel dos Santos. Exploração do uso de short-term memory na construção de métodos
de acesso métricos dinâmicos sobre a perspectiva de diferentes políticas
de divisão de nós. 2017. 98 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Uberlândia, Uberlândia, 2017. DOI http://doi.org/10.14393/ufu.di.2017.295