Distribution of the size of random hash trees, pebbled hash trees and \(N\)-trees (Q5952094): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Revision as of 00:48, 5 March 2024
scientific article; zbMATH DE number 1687669
| Language | Label | Description | Also known as |
|---|---|---|---|
| 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
