Profiles of PATRICIA tries

DOI10.1007/s00453-016-0261-5zbMath1386.68041OpenAlexW2472067340MaRDI QIDQ1702132

Wojciech Szpankowski, Abram Magner

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 transformgenerating functionsanalysis of algorithmssaddle point methodanalytic combinatoricsdigital treesrecurrencesPoissonizationtree profilesPATRICIA trie

Mathematics Subject Classification ID

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

Related Items (4)

Node profiles of symmetric digital search trees: Concentration properties ⋮ Asymptotic expectation of protected node profile in random digital search trees ⋮ Profiles of PATRICIA tries ⋮ Asymmetric Rényi Problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The expected profile of digital search trees
• Mellin transforms and asymptotics: Harmonic sums
• Asymptotical growth of a class of random trees
• Analytical depoissonization and its applications
• Analysis of an asymmetric leader election algorithm
• Laws of large numbers and tail inequalities for random tries and PATRICIA trees
• Profiles of PATRICIA tries
• Universal asymptotics for random tries and PATRICIA trees
• How many random questions are necessary to identify \(n\) distinct objects?
• A Note on a Problem Posed by D. E. Knuth on a Satisfiability Recurrence
• Patricia tries again revisited
• Novel architectures for P2P applications
• Profiles of Tries
• A note on the probabilistic analysis of patricia trees
• New results on the size of tries
• Expected External Profile of PATRICIA Tries
• The Ubiquitous Digital Tree
• AN EXAMPLE IN THE THEORY OF THE SPECTRUM OF A FUNCTION

This page was built for publication: Profiles of PATRICIA tries