Profiles of PATRICIA tries

DOI10.1007/S00453-016-0261-5MaRDI QIDQ1702132zbMATH OpenOpenAlexFDO

Authors Abram Magner, Wojciech Szpankowski

Publication date 28 February 2018

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-016-0261-5

zbMATH Keywords

Mellin transformanalysis of algorithmsgenerating functionsanalytic combinatoricsrecurrencessaddle point methoddigital treesPoissonizationtree profilesPATRICIA trie

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Exact enumeration problems, generating functions (05A15) Data structures (68P05)

Recommendations

• Expected external profile of PATRICIA tries
• Patricia tries again revisited
• scientific article; zbMATH DE number 1512698
• Profiles of Tries
• Limiting Distribution for the Depth in PATRICIA Tries

Cites work

• scientific article; zbMATH DE number 1099195 (Why is no real title available?)
• scientific article; zbMATH DE number 3273551 (Why is no real title available?)
• A Note on a Problem Posed by D. E. Knuth on a Satisfiability Recurrence
• A note on the probabilistic analysis of patricia trees
• AN EXAMPLE IN THE THEORY OF THE SPECTRUM OF A FUNCTION
• Analysis of an asymmetric leader election algorithm
• Analytic combinatorics
• Analytical depoissonization and its applications
• Asymptotical growth of a class of random trees
• Average case analysis of algorithms on sequences. With a foreword by Philippe Flajolet
• Expected external profile of PATRICIA tries
• How many random questions are necessary to identify \(n\) distinct objects?
• Laws of large numbers and tail inequalities for random tries and PATRICIA trees
• Mellin transforms and asymptotics: Harmonic sums
• New results on the size of tries
• Novel architectures for P2P applications: the continuous-discrete approach
• Patricia tries again revisited
• Profiles of PATRICIA tries
• Profiles of Tries
• The Ubiquitous Digital Tree
• The expected profile of digital search trees
• The variance of the profile in digital search trees
• Universal asymptotics for random tries and PATRICIA trees

Cited in

(10)

• Patricia tries again revisited
• Asymmetric Rényi problem
• Asymptotic expectation of protected node profile in random digital search trees
• On the balance property of Patricia tries: External path length viewpoint
• Expected external profile of PATRICIA tries
• Profiles of Tries
• scientific article; zbMATH DE number 4072401 (Why is no real title available?)
• Asymmetric Rényi problem and PATRICIA tries
• Profiles of PATRICIA tries
• Node profiles of symmetric digital search trees: Concentration properties

This page was built for publication: Profiles of PATRICIA tries

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