Implementing Efficient Error-Tolerant Query Autocompletion Systems
| Ano de defesa: | 2024 |
|---|---|
| Autor(a) principal: | |
| Outros Autores: | , |
| Orientador(a): | |
| Banca de defesa: | |
| Tipo de documento: | Tese |
| Tipo de acesso: | Acesso aberto |
| Idioma: | eng |
| Instituição de defesa: |
Universidade Federal do Amazonas
Instituto de Computação Brasil UFAM Programa de Pós-graduação em Informática |
| Programa de Pós-Graduação: |
Não Informado pela instituição
|
| Departamento: |
Não Informado pela instituição
|
| País: |
Não Informado pela instituição
|
| Palavras-chave em Português: | |
| Link de acesso: | https://tede.ufam.edu.br/handle/tede/10568 |
| Resumo: | Nesta tese, desenvolvemos algoritmos e estruturas de dados eficazes e eficientes para sistemas de autocompletar consultas tolerantes a erros (ETQAC). Esses sistemas sugerem consultas classificadas com base em um prefixo digitado, passando por duas fases principais: correspondência e classificação. A fase de correspondência seleciona sugestões que combinam com o prefixo, enquanto a fase de classificação organiza os resultados de acordo com uma função de pontuação que busca as sugestões mais relevantes. Discutimos o uso de uma abordagem de paralelismo de bits para calcular a distância de edição entre strings, adaptando-a para métodos de busca aproximada por prefixo. Propomos um método baseado em tries chamado BWBEV, que utiliza uma representação unária de vetores de edição e operações de bits para atualizá-los ao calcular distâncias de edição. Demonstramos também como aplicar essa técnica para computar distâncias de edição online sem uma estrutura de índice. Nossos experimentos mostram que o BWBEV melhora a velocidade de processamento em mais de 36% em comparação com métodos de ponta. Além disso, investigamos a otimização do cálculo dos resultados principais, combinando as fases de correspondência e classificação para eliminar resultados irrelevantes durante a correspondência, acelerando assim o processamento. Como ETQACs precisam apresentar apenas algumas das melhores sugestões, essa limitação é explorada para reduzir custos computacionais. Em relação à fase de correspondência, estudos anteriores utilizaram tries e variações como estruturas em memória. No entanto, esses métodos podem exigir muita memória. Exploramos o uso de burst tries, uma versão compacta de tries, como estrutura subjacente para métodos de busca de prefixo tolerante a erros. Burst tries constroem contêineres leves nos nós folha do índice, reduzindo custos de armazenamento sem comprometer o desempenho. Ao indexar o conjunto de dados JusBrasil, o uso de burst tries reduziu o consumo de memória para 26% de uma trie completa e aumentou o desempenho de tempo em 16%. |
