Implementing Efficient Error-Tolerant Query Autocompletion Systems

Abstract

In this thesis, we focus on developing effective and efficient algorithms and data structures for implementing error-tolerant query autocompletion (ETQAC) systems. An ETQAC system suggests fully ranked queries based on a typed prefix and consists of two main phases: matching and ranking. The matching phase involves selecting query suggestions that match a given prefix, while the ranking phase involves sorting the matched results according to a score function that attempts to select the most relevant suggestions.

We discuss the use of a bit-parallel approach to compute the edit distance between two strings and demonstrate how it can be adapted for approximate prefix search methods. We propose a trie-based method, called BWBEV, that uses a unary representation of edit vectors and bitwise operations to update them when computing edit distances. We also show how to apply our new bit-parallelism technique strategy to online edit distance computation between strings without index structure. Our experimental results with BWBEV indicate that it can significantly improve processing speed by more than 36% compared to state-of-the-art methods. In addition, we also study how to optimize the computation of top results when performing the ranking by combining the match and ranking phases to prune results while computing the matches, consequently accelerating the query processing. ETQAC systems usually need to present just a few top-ranked suggestions to their users and we can take advantage of this limit in the number of answers to reduce the computational costs when implementing an ETQAC system.

Regarding methods for computing matching results, several previous studies in the literature have utilized tries and their variations as in-memory data structures to implement the matching phase of ETQAC systems. However, these methods may require a significant amount of memory to process queries. We explore the use of burst tries, a compact version of tries, as the underlying data structure to implement state-of-the-art trie-based error-tolerant prefix search methods. Burst tries are an alternative compact trie implementation that builds lightweight containers in the leaf nodes of the index based on a criterion or parameter to reduce storage costs while maintaining close performance to tries. We examine the trade-off between memory usage and time performance while varying the parameters used to build the burst trie index. For instance, when indexing the JusBrasil dataset, one of the datasets utilized in our experiments, the use of burst tries reduces the memory required by a full trie to 26% and increases time performance to 16%.