Compressed Tries

This paper presents a new data structure,
called a compressed trie or C-trie, to be used in 
information retrieval systems.  It has the same underlying
m-ary tree structure as a trie, where m is 
a parameter of the trie, but whereas the fields of the
nodes in a trie have to be large enough to hold 
a key or at least a pointer, the fields in a C-trie are
only one bit long.  In the analysis part of the 
paper it will be shown that for a collection of n keys the
retrieval time, measured in terms of bit inspections 
of one key, is of the order logm(n) and the storage
requirement of the order n*(m+log2 n) bits.  This 
improvement in storage requirements and retrieval time
is achieved at the cost of decreasing the flexibility 
of the structure, and therefore updating costs are increased.
 First the C-trie is analyzed as a data 
structure, and then several methods of its use
for relatively static databases are discussed.

CACM July, 1976

Maly, K.

data structure, database, m-ary tree, trie,
retrieval time, storage requirement, keys

3.70 3.74 3.75

CA760707 JB January 4, 1978  12:26 PM

2846	4	2846
849	4	2846
944	4	2846
155	5	2846
2846	5	2846
2846	5	2846
2846	5	2846
3041	5	2846
2846	6	2846
2905	6	2846