???item.export.label??? ???item.export.type.endnote??? ???item.export.type.bibtex???

Please use this identifier to cite or link to this item: https://tede.ufam.edu.br/handle/tede/8854
???metadata.dc.type???: Dissertação
Title: Combinando busca binária exata e busca aproximada em sistemas de complementação automática de consultas
Other Titles: Combining exact binary search and approximate search in autocompletion systems
???metadata.dc.creator???: Belém, Rúben Jozafá Silva 
???metadata.dc.contributor.advisor1???: Moura, Edleno Silva de
???metadata.dc.contributor.referee1???: Silva, Altigran Soares da
???metadata.dc.contributor.referee2???: Cavalcanti, João Marcos Bastos
???metadata.dc.description.resumo???: A complementação automática de consultas é uma funcionalidade importante para sistemas de busca modernos, e consiste em sugerir consultas a cada tecla digitada pelo usuário. As soluções mais eficientes dos últimos anos têm utilizado índices de árvore Trie para indexar as sugestões de consultas. No entanto, essa estrutura pode acabar consumindo uma grande quantidade de memória, que é um recurso caro e limitado. Este trabalho apresenta uma abordagem em dois níveis que utiliza o algoritmo ICPAN de busca tolerante a erros em um índice de árvore Trie no primeiro nível e combina busca sequencial com binária no segundo, tendo o objetivo de averiguar se essa combinação possibilita tornar o segundo nível mais eficiente sem que a acurácia dos resultados seja prejudicada. A hipótese inicial era a de que é possível realizar busca binária em vez de sequencial quando todos os erros de digitação tolerados já estiverem sido “esgotados” no primeiro nível. No entanto, concluímos no decorrer desta pesquisa que utilizar busca binária no segundo nível impede o método de recuperar algumas sugestões de consulta que deveria, e também o faz trazer outras que ultrapassam a quantidade 𝜏 de erros de digitação tolerados. Diante desse problema, também propusemos uma heurística de ativação seletiva da busca binária. Experimentamos três versões de métodos em dois níveis, cada uma com determinada modificação no segundo nível e comparamos seus ní- veis de acurácia, seus desempenhos, e utilização de memória. Ambas as versões que utilizam busca binária com e sem heurística demonstram-se imprecisas para 𝜏 ≤ 2, porém com uma boa precisão para 𝜏 = 3. Nesse caso em específico o modelo que utiliza busca binária sem heurística obteve o melhor desempenho em comparação às outras versões, e também desempenhou melhor que outros métodos encontrados na literatura em alguns casos. Além disso, todos os três modelos propostos demonstraram redução significativa da quantidade de memória necessária para realizar a complementação automática de consultas.
Abstract: Query autocompletion is an important feature for moderen search engines that stands for suggesting queries at each user keystroke. The most efficient solutions in the past years have been using Tries to index the query suggestions. However, this structure may lead to more memory usage, which is a costly and limited resource. In this work, we introduce a two-level structure that uses the ICPAN error-tolerant search algorithm at the first level and combines sequential and binary search at the second level, with the aim of verify whether this combination can increase the efficiency of the second level without affecting the results accuracy. Our initial hypothesis was that it was possible to perform a binary search instead of a sequential when all the typing errors had already “ran out” at the first level. Nonetheless, we conclude in our research that using binary search at the second level prevents the method of retrieving some query suggestions, and also makes it retrieve some suggestions that exceed the limit 𝜏 of typing errors tolerated. Facing this problem, we also proposed a heuristic to selectively activate the binary search. We have experimented with three versions of two-level structure, with each one having a modification at the second level. We compared their accuracy levels, their performances, and their memory usage. Both versions that use the binary search with and without the heuristic showed some lack of accuracy for 𝜏 ≤ 2. However, they had good accuracy for 𝜏 = 3. In this specific case the model that uses binary search without the heuristic had the best performance when compared with other versions, and also had performed better than other methods found in the literature in some scenarios. Besides that, all the three proposed models have shown a significant reduction of memory needed to run error-tolerant query autocompletion.
Keywords: Recuperação de dados (Computação)
???metadata.dc.subject.cnpq???: CIENCIAS EXATAS E DA TERRA: CIENCIA DA COMPUTACAO: TEORIA DA COMPUTACAO: RECUPERAÇÃO DE INFORMAÇÃO
???metadata.dc.subject.user???: Processamento de consultas
Preenchimento automático
Complementação automática de consultas
Tolerante a erros
Dois níveis
Trie
Busca binária
Language: por
???metadata.dc.publisher.country???: Brasil
Publisher: Universidade Federal do Amazonas
???metadata.dc.publisher.initials???: UFAM
???metadata.dc.publisher.department???: Instituto de Computação
???metadata.dc.publisher.program???: Programa de Pós-graduação em Informática
Citation: BELÉM, Ruben Jozafá Silva. Combinando busca binária exata e busca aproximada em sistemas de complementação automática de consultas. 2022. 94 f. Dissertação (Mestrado em Informática) - Universidade Federal do Amazonas, Manaus (AM), 2022.
???metadata.dc.rights???: Acesso Aberto
???metadata.dc.rights.uri???: http://creativecommons.org/licenses/by/4.0/
URI: https://tede.ufam.edu.br/handle/tede/8854
Issue Date: 25-Mar-2022
Appears in Collections:Mestrado em Informática

Files in This Item:
File Description SizeFormat 
Dissertação_RubenBelem_PGGI.pdf2.69 MBAdobe PDFThumbnail

Download/Open Preview


This item is licensed under a Creative Commons License Creative Commons