Comparação entre Diferentes Implementações de BK-trees para o Problema de Busca por Intervalo

• Andre Luciano Rakowski
• Natan Luiz Paetzhold Berwaldt
• Mauricio Vielmo Schmaedeck
• Sergio Luis Sardi Mergen

Resumo

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.