A multivariate view of random bucket digital search trees

DOI10.1016/S0196-6774(02)00210-9MaRDI QIDQ4799525zbMATH OpenOpenAlexFDO

Authors Friedrich Hubalek, Hsien-Kuei Hwang, William Lew, Hosam M. Mahmoud, Helmut Prodinger

Publication date 23 March 2003

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0196-6774(02)00210-9

zbMATH Keywords

asymptotic normalitybucketingEuler transformMellin transformprobabilistic analysis of algorithmsrandom treessearchingsingularity analysis

Mathematics Subject Classification ID

Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The variance of the profile in digital search trees
• The variance of the height of digital search trees
• The variance for partial match retrievals in k-dimensional bucket digital trees
• scientific article; zbMATH DE number 168426
• scientific article; zbMATH DE number 777291
• RANDOM HYPERPLANE SEARCH TREES IN HIGH DIMENSIONS
• Some estimates for the distribution of the height of digital search trees
• Random hyperplane search trees
• scientific article; zbMATH DE number 6145140

Cited in

(6)

• A general limit theorem for recursive algorithms and combinatorial structures
• An analytic approach to the asymptotic variance of trie statistics and related structures
• A general central limit theorem for shape parameters of m-ary tries and PATRICIA tries
• The Joint Distribution of Elastic Buckets in Multiway Search Trees
• The Wiener index of random digital trees
• Asymptotic normality for the size of graph tries built from M-ary tree labelings

Describes a project that uses

Uses Software

• QUADPACK
• Cubpack++

This page was built for publication: A multivariate view of random bucket digital search trees

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