Applying burst-tries for error-tolerant prefix search

Author(s)

Ferreira, Berg ; de Moura, Edleno Silva ; da Silva, Altigran

• Document type: Journal article
• Source: INFORMATION RETRIEVAL JOURNAL; v. 25, n. 4, p. 38-pg., 2022-10-18.

Abstract

In this work we address the problem of performing an error-tolerant prefix search on a set of string keys. While the ideas presented here could be adopted in other applications, our primary target application is error-tolerant query autocompletion. Tries and their variations have been adopted as the basic data structure to implement recently proposed error-tolerant prefix search methods. However, they must require a lot of extra memory to process queries. Burst tries are alternative compact tries proposed to reduce storage costs and maintain a close performance when compared to the use of tries. Here we discuss alternatives for adapting burst tries as error-tolerant prefix search data structures. We show how to adapt state-of-the-art trie-based methods for use with burst tries. We studied the trade-off between memory usage and time performance while varying the parameters to build the burst trie index. As an example, when indexing the JusBrasil dataset, one of the datasets adopted in the experiments, the use of burst tries reduces the memory required by a full trie to 26% and increases the time performance to 116%. The possibility of balancing memory usage and time performance constitutes an advantage of the burst trie when compared to the full trie when adopted as an index for the task of performing error-tolerant prefix search. (AU)

• FAPESP's process: 20/05173-4 - A multimodal approach to identify bias in digital social media
• Grantee: Altigran Soares da Silva
• Support Opportunities: Regular Research Grants