Patricia tries again revisited

DOI10.1145/96559.214080MaRDI QIDQ3495658zbMATH OpenOpenAlexWikidataFDO

Authors Wojciech Szpankowski

Publication date 1990

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1542&context=cstech

zbMATH Keywords

balanced treesdata structuresdigital search treesPatricia trieprobabilistic analysis of algorithmssuccessful searchunsuccessful search

Mathematics Subject Classification ID

Data structures (68P05) Information storage and retrieval of data (68P20) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05)

Recommendations

• scientific article; zbMATH DE number 4072401
• On the balance property of Patricia tries: External path length viewpoint
• Profiles of PATRICIA tries
• Limiting Distribution for the Depth in PATRICIA Tries
• scientific article; zbMATH DE number 1512698

Cited in

(27)

• On the balance property of Patricia tries: External path length viewpoint
• Analytical depoissonization and its applications
• A characterization of digital search trees from the successful search viewpoint
• Probabilistic modeling of data structures on words. A reply to Professor Andersson's letter
• A dynamic construction algorithm for the compact Patricia trie using the hierarchical structure.
• Laws of large numbers and tail inequalities for random tries and PATRICIA trees
• Profiles of PATRICIA tries
• Optimizing registration based encryption
• Size and path length of Patricia tries: Dynamical sources context
• Analysis of random LC tries
• On the smoothed heights of trie and patricia index trees
• On unary nodes in tries
• Julia and John revisited
• A Note on a Problem Posed by D. E. Knuth on a Satisfiability Recurrence
• scientific article; zbMATH DE number 4072401 (Why is no real title available?)
• A note on the probabilistic analysis of patricia trees
• Multidimensional digital searching—alternative data structures
• scientific article; zbMATH DE number 1512698 (Why is no real title available?)
• PATRICIA bridges
• Analytic analysis of algorithms
• How to count quickly and accurately: a unified analysis of probabilistic counting and other related problems
• Asymmetric Rényi problem
• Mellin transforms and asymptotics: Harmonic sums
• Mellin transforms and asymptotics: Finite differences and Rice's integrals
• A note on binomial recurrences arising in the analysis of algorithms
• Central limit theorems for additive functionals of patricia tries
• Renewal theory in the analysis of tries and strings

This page was built for publication: Patricia tries again revisited

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3495658)