Paper Info
Title
A multivariate view of random bucket digital search trees
Abstract
We take a multivariate view of digital search trees by studying the number of nodes of different types that may coexist in a bucket digital search tree as it grows under an arbitrary memory management system. We obtain the mean of each type of node, as well as the entire covariance matrix between types, whereupon weak laws of large numbers follow from the orders of magnitude (the norming constants include oscillating functions). The result can be easily interpreted for practical systems like paging, heaps and UNIX's buddy system. The covariance results call for developing a Mellin convolution method, where convoluted numerical sequences are handled by convolutions of their Mellin transforms. Furthermore, we use a method of moments to show that the distribution is asymptotically normal. The method of proof is of some generality and is applicable to other parameters like path length and size in random tries and Patricia tries.
Year
DOI
Venue
2002
10.1016/S0196-6774(02)00210-9
J. Algorithms
Keywords
Field
DocType
buddy system,arbitrary memory management system,mellin convolution method,convoluted numerical sequence,covariance result,random bucket digital search,multivariate view,entire covariance matrix,bucket digital search tree,different type,digital search tree,practical system,memory management,oscillations,mellin transform,covariance matrix,law of large numbers,probabilistic analysis of algorithms,asymptotic normality
Mellin transform,Random search,Discrete mathematics,Combinatorics,Convolution,Law of large numbers,Algorithm,Heap (data structure),Covariance matrix,Mathematics,Search tree,Covariance
Journal
Volume
Issue
ISSN
44
1
0196-6774
Citations 
PageRank 
References 
8
0.48
20
Authors
5
Name
Order
Citations
PageRank
Friedrich Hubalek1131.31
Hsien-Kuei Hwang236538.02
William Lew3161.32
Hosam Mahmoud4264.16
Helmut Prodinger5734118.96