Size and path length of Patricia tries: Dynamical sources context

DOI10.1002/rsa.10015zbMath1016.68029MaRDI QIDQ2772922

Jérémie Bourdon

Publication date: 14 May 2002

Published in: Random Structures and Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.10015

zbMATH Keywords

digital trees; Patricia tries

Mathematics Subject Classification ID

68P05: Data structures

Related Items

Renewal theory in the analysis of tries and strings, Management and analysis of DNA microarray data by using weighted trees, A weakly 1-stable distribution for the number of random records and cuttings in split trees

Cites Work

• Unnamed Item
• Unnamed Item
• Mellin transforms and asymptotics: Harmonic sums
• Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees
• On the performance evaluation of extendible hashing and trie searching
• On the balance property of Patricia tries: External path length viewpoint
• Continued fraction algorithms, functional operators, and structure constants
• Analytical depoissonization and its applications
• A study of trie-like structures under the density model
• La théorie de Fredholm
• Patricia tries again revisited
• A complex Ruelle-Perron-Frobenius theorem and two counterexamples
• A universal algorithm for sequential data compression
• Compression of individual sequences via variable-rate coding
• Algorithms on Strings, Trees and Sequences
• Limiting Distribution for the Depth in PATRICIA Tries
• Digits and continuants in Euclidean algorithms. Ergodic versus Tauberian theorems