The variance of the profile in digital search trees

MaRDI QIDQ5403003zbMATH OpenFDO

Authors Ramin. Kazemi, Mohammad Q. Vahidi-Asl

Publication date 25 March 2014

Full work available at URL https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/1808/0.html

zbMATH Keywords

Mellin transformgenerating functionssingularity analysissaddle point methoddigital search treesPoissonizationtree profilesPoisson variance

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Data structures (68P05) Searching and sorting (68P10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Recommendations

• The expected profile of digital search trees
• On the average profile of symmetric digital search trees
• scientific article; zbMATH DE number 7051180
• scientific article; zbMATH DE number 6477191
• Digital Search Trees Again Revisited: The Internal Path Length Perspective

Cited in

(22)

• A multivariate view of random bucket digital search trees
• scientific article; zbMATH DE number 1445303 (Why is no real title available?)
• scientific article; zbMATH DE number 6145140 (Why is no real title available?)
• Asymptotic variance of random symmetric digital search trees
• Further results on digital search trees
• The variance of the height of digital search trees
• Distribution of inter-node distances in digital trees
• Digital Search Trees Again Revisited: The Internal Path Length Perspective
• The expected profile of digital search trees
• Distances in random digital search trees
• External profile of symmetric digital search trees (extended abstract)
• Node profiles of symmetric digital search trees: Concentration properties
• Asymmetric Rényi problem
• scientific article; zbMATH DE number 7051180 (Why is no real title available?)
• Generalized Digital Trees and Their Difference—Differential Equations
• Digital search trees with \(m\) trees: level polynomials and insertion costs
• On the average profile of symmetric digital search trees
• Continuous-time digital search tree and a border aggregation model
• Variance of the internal profile in suffix trees
• Asymptotic expectation of protected node profile in random digital search trees
• Profiles of PATRICIA tries
• Average Profile of the Generalized Digital Search Tree and the Generalized Lempel--Ziv Algorithm

This page was built for publication: The variance of the profile in digital search trees

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