Distribution of the size of random hash trees, pebbled hash trees and \(N\)-trees (Q5952094): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Height and Size of Random Hash Trees and Random Pebbled Hash Trees / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Searching and sorting real numbers / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the analysis of linear probing hashing / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4519900 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Analytic variations on bucket selection and sorting / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Analysis of N-trees / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3993278 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 22:07, 3 June 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