The variance of the profile in digital search trees

zbMATH Open1283.68142MaRDI QIDQ5403003FDOQ5403003

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

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

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)

Cited In (21)

• Title not available (Why is that?)
• Asymptotic variance of random symmetric digital search trees
• Distribution of inter-node distances in digital trees
• Further results on digital search trees
• The variance of the height of digital search trees
• Digital Search Trees Again Revisited: The Internal Path Length Perspective
• The expected profile of digital search trees
• Distances in random digital search trees
• Node profiles of symmetric digital search trees: Concentration properties
• External profile of symmetric digital search trees (extended abstract)
• Asymmetric Rényi problem
• Title not available (Why is that?)
• 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
• 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
• A multivariate view of random bucket digital search trees
• Title not available (Why is that?)

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)