@PHDTHESIS{ 2024:2124335514,
 	title = {Implementing Efficient Error-Tolerant Query Autocompletion Systems},
 	year = {2024},
 	url = "https://tede.ufam.edu.br/handle/tede/10568",
 	abstract = "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%.",
 	publisher = {Universidade Federal do Amazonas},
 	scholl = {Programa de Pós-graduação em Informática},
 	note = {Instituto de Computação}
}