Abstract
Level-compressed (LC) tries are a popular data structure for high-speed routing and string searching due to their ability to "flatten" standard digital trees. This paper provides the first rigorous theoretical analysis of "partial fillup" in LC tries, where subtrees are compressed even if they are not perfectly full. While previous experimental studies claimed dramatic improvements in search time, we prove that the asymptotic improvement is moderate, shifting only the constants in an $O(\log \log n)$ search time. We employ probabilistic analysis on binary memoryless sources to derive precise formulas for the fillup level and typical search depth.
Introduction
Tries, or digital trees, are fundamental to various computer science applications, including IP address lookup and Lempel-Ziv compression. A significant drawback of standard tries is their potential depth, which leads to increased search times. Level-compressed (LC) tries address this by replacing full subtrees with single high-degree nodes, effectively reducing the tree's height.
In the 1990s, empirical research suggested that compressing subtrees that are only partially full (e.g., 80% density) could yield significant performance gains. However, a theoretical framework to explain these results was missing. This study investigates the "fillup level"—the depth achievable while maintaining a density $\alpha$—and the resulting average search time in these $\alpha$-LC tries.
Methodology
The analysis utilizes a probabilistic framework based on a binary memoryless source model, where strings are generated as i.i.d. Bernoulli trials with probability $p$ for a "1". The mathematical approach involves several key techniques:
- Poissonization and Depoissonization: By assuming the number of strings $n$ follows a Poisson distribution, the authors decouple the dependencies between subtrees. They then apply analytical tools to translate these results back to the fixed-$n$ case.
- Concentration Analysis: The study proves that the $\alpha$-fillup level $F_n(\alpha)$ is highly concentrated, typically residing within two specific integer values for a given $n$.
Key Insights
The theoretical analysis yields several critical insights that challenge or refine previous empirical assumptions:
- Asymptotic vs. Constant Improvement: While practitioners reported "dramatic" speedups, the math reveals that search time for both standard and $\alpha$-LC tries remains $O(\log \log n)$. The partial fillup primarily improves the constant factor.
- The Role of Alpha: The fillup threshold $\alpha$ only influences the lower-order terms of the fillup level. The leading term is dominated by the source's entropy and the total number of strings.
- Two-Point Concentration: The fillup level does not spread significantly as $n$ increases, maintaining a tight lock on just two possible values with high probability.
Results
The authors derived a precise formula for the $\alpha$-fillup level $k_n$: $$k_n \approx \log_{1/\sqrt{pq}} n - \text{correction terms involving } \Phi^{-1}(\alpha)$$
For a symmetric source ($p=1/2$), the typical search depth $D_n(\alpha)$ is characterized as: $$D_n(\alpha) \sim \frac{\log \log n}{-\log(1 - h/h_{\infty})}$$ where $h$ represents the Shannon entropy. The results confirm that $\alpha$-LC tries possess a superior constant compared to original LC tries, justifying their use in high-performance systems.
Conclusion
The discrepancy between "dramatic" experimental gains and "moderate" theoretical improvements is explained by the scale of $n$. In practical scenarios (e.g., millions of IP addresses), $\log \log n$ is very small (approx. 4-5). In this regime, the lower-order terms and constants—which the theory identifies as the primary beneficiaries of partial fillup—actually dominate real-world performance. Future work may extend these findings to non-binary alphabets and more complex Markov sources.
Summary updated