We study a class of tries that adaptively choose degrees of their nodes by processing multiple digits of input keys at a time. We demonstrate that the size (total number of pointers) of such tries depends on the strategy used for selecting the degrees of their nodes, and propose a local space-efficiency criterion that can be used to guide a dynamic construction of tries minimizing their size. We study the expected behavior of this criterion (as a function of the number of keys and the number of digits processed by a node) in a binary memoryless model, and demonstrate that it attains a maximum when , where is a constant depending on the parameters ( and ) of the source. Surprisingly enough, we also find that under asymmetric memoryless sources, the expected number of empty pointers in nodes with such a relation between and is about 50

Please send comments and corrections to Thomas Klausner.