Optimizing BEVA with Two-Level Indexes

Abstract

Query autocompletion is an important component of modern search systems that suggests possible queries at each user keystroke to complete the query based on the prefix already typed in the search box. One of the most adopted and successful data structures for query autocompletion is the TRIE which is used to index the possible query suggestions. The TRIE is traversed based on the search prefix typed by the user in order to select suggestions that match the prefix. The use of TRIEs requires a large amount of extra memory for processing queries, which may increase the cost for processing queries and may limit the number of query suggestions indexed. In this work we propose optimized alternative implementations of BEVA algorithm, currently the state-of-the-art in the literature for autocompletion, in order to achieve a reduction in its memory consumption while keeping it efficient in query processing times. First, we propose a novel strategy to build the TRIE, named level-at-a-time (laat), and compare its performance to the way TRIEs are usually built, the key-ata-time (kaat). In the kaat strategy the index is built in depth-ward direction and in the laat strategy the index is built in breadth-ward direction. We implemented the proposed ideas and experimented them with several datasets, where we show that laat strategy allows a significant speedup in query processing of BEVA, being up to four times faster, with improvements achieved specially in queries with high number of errors, which are the most expensive ones. Second, we study the use of two-level indexing and prefix processing approaches for query autocompletion also in BEVA method. Two-level approaches combine the use of indexes with sequential search in order to reduce memory requirements in search systems. In our study, we insert in the TRIE only part of each query inserted, and the leaf nodes reference to a set of queries where a sequential search is performed. We experimented two alternative ways of selecting the portion of each key that remains indexed in the first level and compare their performance. The two-level approach has shown to significantly reduce the memory requirements for storing the index with just a small variation in query processing times