Yuri Reznik: On Time/Space Performance of Tries with Adaptive Branching

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 $n$ and the number of digits $r$ processed by a node) in a binary memoryless model, and demonstrate that it attains a maximum when $r = \log n / h_0 + o(\sqrt{\log n})$, where $h_0 = -\frac{1}{2} \log p - \frac{1}{2} \log q$ is a constant depending on the parameters ($p$ and $q$) 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 $r$ and $n$ is about 50

Back to the Index