Distribution of the size of random hash trees, pebbled hash trees and \(N\)-trees (Q5952094)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1687669
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Distribution of the size of random hash trees, pebbled hash trees and \(N\)-trees |
scientific article; zbMATH DE number 1687669 |
Statements
Distribution of the size of random hash trees, pebbled hash trees and \(N\)-trees (English)
0 references
16 September 2002
0 references
The present mathematical note starts from the results of \textit{L. Devroye} [SIAM J. Comput. 28, No. 4, 1215--1224 (1999; Zbl 0939.68048)], that provide a computational analysis of the mean and size of random hash trees, pebbled hash trees, and \(N\)-trees. The aim of the article is to extend Devroye's results by deriving the limiting distribution of the (normed) size by using analytic techniques based on saddle-point approximations. The proposed approach has been successfully applied in hashing, and in bucket selection and sorting.
0 references
random trees
0 references
random hash trees
0 references
pebbled trees
0 references
saddle-point approximations
0 references
central limit theorem
0 references
hashing
0 references
bucket selection and sorting
0 references
0.8706785440444946
0 references
0.7435611486434937
0 references
0.7293574810028076
0 references
0.7281379699707031
0 references
