Abstract
We study a modification of digital trees (or tries) with adaptive multi-digit branching. Such tries can dynamically adjust degrees of their nodes by choosing the number of digits to be processed per each lookup. While we do not specify any particular method for selecting the degrees of nodes, we assume that such selection can be accomplished by examining the number of strings remaining in each sub-tree, and/or estimating parameters of the input distribution. We call this class of digital trees adaptive multi-digit tries (or AMD-tries) and provide a preliminary analysis of their expected behavior in a memoryless model. We establish the following results: 1) there exist AMD-tries attaining a constant (O(1)) expected time of a successful search; 2) there exist AMD-tries consuming a linear (O(n), n is the number of strings inserted) amount of space; 3) both constant search time and linear space usage can be attained if the (memoryless) source is symmetric. We accompany our analysis with a brief survey of several known types of adaptive trie structures, and show how our analysis extends (and/or complements) the previous results.
The author is also on leave from the Institute of Mathematical Machines and Systems of National Academy of Sciences of Ukraine.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
M. Abramowitz, and I. Stegun, Handbook of Mathematical Functions, Dover, NY (1972)
Andersson, and S. Nilsson, Improved Behaviour of Tries by Adaptive Branching, Information Processing Letters, 46 (1993) 295–300.
T. M. Cover and J. M. Thomas, Elements of Information Theory, John Wiley & Sons, New York (1991)
R. M. Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey, and D. E. Knuth, On the Lambert W Function, Advances in Computational Mathematics, 5 (1996) 329–359
L. Devroye, A Note on the Average Depths in Tries, Computing, 28 (1982) 367–371
W. Dobosiewitz, Sorting by Distributive Partitioning, Information Processing Letters, 7,1, (1978) 1–6
W. Dobosiewitz, The Practical Significance of DP Sort Revisited, Information Processing Letters, 8,4 (1979) 170–172
G. Ehrlich, Searching and Sorting Real Numbers, J. Algorithms, 2 (1981) 1–14
P. Flajolet and R. Sedgewick, Digital Search Trees Revisited, SIAM J. Computing, 15, (1986) 748–767
P. Jacquet and W. Szpankowski, Analysis of Digital Trees with Markovian Dependency, IEEE Trans. Information Theory, 37 (1991) 1470–1475
D. Knuth, The Art of Computer Programming. Sorting and Searching. Vol. 3., Addison-Wesley (1973)
G. Louchard, The Brownian Motion: A Neglected Tool for the Complexity Analysis of Sorted Tables Manipulations, RAIRO Theoretical Informatics, 17 (1983) 365–385
G. Louchard, Digital Search Trees Revisited, Cahiers du CERO, 36 (1995) 259–27
G. Louchard and W. Szpankowski, An Exercise in Asymptotic Analysis, reprint (1995)
S. Nilsson, Radix Sorting and Searching, Ph.D. thesis, Department of Computer Science, Lund University (1996)
Pittel, Paths in a Random Digital Tree: Limiting Distributions. Advances in Applied Probability, 18 (1986) 139–155
R. Sedgewick, and P. Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, Reading, MA (1996)
W. Szpankowski, Techniques for the Average Case Analysis of Algorithms on Words, John Wiley & Sons, to be published
W. Szpankowski, Some results on V-ary asymmetric tries, Journal of Algorithms, 9 (1988) 224–244
M. Tamminen, Analysis of N-Trees, Information Processing Letters, 16,3 (1983) 131–137
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Reznik, Y.A. (2000). Some Results on Tries with Adaptive Branching. In: Du, DZ., Eades, P., Estivill-Castro, V., Lin, X., Sharma, A. (eds) Computing and Combinatorics. COCOON 2000. Lecture Notes in Computer Science, vol 1858. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44968-X_15
Download citation
DOI: https://doi.org/10.1007/3-540-44968-X_15
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67787-1
Online ISBN: 978-3-540-44968-3
eBook Packages: Springer Book Archive