Comparação entre Diferentes Implementações de BK-trees para o Problema de Busca por Intervalo - Rakowski, Andre Luciano; Berwaldt, Natan Luiz Paetzhold; Schmaedeck, Mauricio Vielmo; Mergen, Sergio Luis Sardi (Anais da Escola Regional de Banco de Dados (ERBD), 2018)
In the context of information retrieval, similarity search for range queries is the problem of finding words whose edit distance to a query are smaller than a determined distance. BK-trees is a pivot based indexing mechanism that achieves good results for this kind of query. Experiments show that, despite its simplicity, the efficiency is superior to other approaches when it comes to text searching. However, no information is provided concerning the underlying structure of the tree. In this paper, we analyze different ways of implementing this indexing structure. Our experiments compare the investigated variations in terms of space cost, indexing time and search time.