The Prague Stringology Club Workshop '97

Masami Shishibori, Makoto Okada, Toru Sumitomo and Jun-ichi Aoe

An Efficient Trie Hashing Method Using a Compact Binary Trie

Abstract:
In many applications, information retrieval is a very important research field. In several key strategies, the binary trie is famousas a fast access method to be able to retrieve keys in order. However, if the binary trie structure is implemented, the greater thenumber of the registered keys, the larger storage is required, as aresult, the binary trie can not be stored into the main memory. Inorder to solve this problem, the method to change the binary trie into a compact bit stream have been proposed, however, searching and updating a key takes a lot of time in large key sets. This paper proposes the method to improve the time efficiency of each process by introducing a new hierarchical structure. The theoretical and experimental results show that this method provides faster access than the traditional method.

Download paper: Article in PostScript Article in PDF
 PostScript   PDF