Combinando busca binária exata e busca aproximada em sistemas de complementação automática de consultas
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 e...
| Autor principal: | Belém, Rúben Jozafá Silva |
|---|---|
| Outros Autores: | http://lattes.cnpq.br/8324372844739136 |
| Grau: | Dissertação |
| Idioma: | por |
| Publicado em: |
Universidade Federal do Amazonas
2022
|
| Assuntos: | |
| Acesso em linha: |
https://tede.ufam.edu.br/handle/tede/8854 |
| id |
oai:https:--tede.ufam.edu.br-handle-:tede-8854 |
|---|---|
| recordtype |
dspace |
| spelling |
oai:https:--tede.ufam.edu.br-handle-:tede-88542022-05-05T05:03:42Z Combinando busca binária exata e busca aproximada em sistemas de complementação automática de consultas Combining exact binary search and approximate search in autocompletion systems Belém, Rúben Jozafá Silva Moura, Edleno Silva de http://lattes.cnpq.br/8324372844739136 http://lattes.cnpq.br/4737852130924504 Silva, Altigran Soares da http://lattes.cnpq.br/3405503472010994 Cavalcanti, João Marcos Bastos http://lattes.cnpq.br/3537707069694606 Recuperação de dados (Computação) CIENCIAS EXATAS E DA TERRA: CIENCIA DA COMPUTACAO: TEORIA DA COMPUTACAO: RECUPERAÇÃO DE INFORMAÇÃO Processamento de consultas Preenchimento automático Complementação automática de consultas Tolerante a erros Dois níveis Trie Busca binária 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. 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. O email de cadastro demorou para ser enviado, e quando chegou, veio como spam. . 2022-05-04T18:07:35Z 2022-03-25 Dissertação 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. https://tede.ufam.edu.br/handle/tede/8854 por Acesso Aberto http://creativecommons.org/licenses/by/4.0/ application/pdf Universidade Federal do Amazonas Instituto de Computação Brasil UFAM Programa de Pós-graduação em Informática |
| institution |
TEDE - Universidade Federal do Amazonas |
| collection |
TEDE-UFAM |
| language |
por |
| topic |
Recuperação de dados (Computação) CIENCIAS EXATAS E DA TERRA: CIENCIA DA COMPUTACAO: TEORIA DA COMPUTACAO: RECUPERAÇÃO DE INFORMAÇÃO Processamento de consultas Preenchimento automático Complementação automática de consultas Tolerante a erros Dois níveis Trie Busca binária |
| spellingShingle |
Recuperação de dados (Computação) CIENCIAS EXATAS E DA TERRA: CIENCIA DA COMPUTACAO: TEORIA DA COMPUTACAO: RECUPERAÇÃO DE INFORMAÇÃO Processamento de consultas Preenchimento automático Complementação automática de consultas Tolerante a erros Dois níveis Trie Busca binária Belém, Rúben Jozafá Silva Combinando busca binária exata e busca aproximada em sistemas de complementação automática de consultas |
| topic_facet |
Recuperação de dados (Computação) CIENCIAS EXATAS E DA TERRA: CIENCIA DA COMPUTACAO: TEORIA DA COMPUTACAO: RECUPERAÇÃO DE INFORMAÇÃO Processamento de consultas Preenchimento automático Complementação automática de consultas Tolerante a erros Dois níveis Trie Busca binária |
| description |
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. |
| author_additional |
Moura, Edleno Silva de |
| author_additionalStr |
Moura, Edleno Silva de |
| format |
Dissertação |
| author |
Belém, Rúben Jozafá Silva |
| author2 |
http://lattes.cnpq.br/8324372844739136 |
| author2Str |
http://lattes.cnpq.br/8324372844739136 |
| title |
Combinando busca binária exata e busca aproximada em sistemas de complementação automática de consultas |
| title_short |
Combinando busca binária exata e busca aproximada em sistemas de complementação automática de consultas |
| title_full |
Combinando busca binária exata e busca aproximada em sistemas de complementação automática de consultas |
| title_fullStr |
Combinando busca binária exata e busca aproximada em sistemas de complementação automática de consultas |
| title_full_unstemmed |
Combinando busca binária exata e busca aproximada em sistemas de complementação automática de consultas |
| title_sort |
combinando busca binária exata e busca aproximada em sistemas de complementação automática de consultas |
| publisher |
Universidade Federal do Amazonas |
| publishDate |
2022 |
| url |
https://tede.ufam.edu.br/handle/tede/8854 |
| _version_ |
1831970068988166144 |
| score |
11.753735 |