Viola, Alfredo - Distributional Analysis of the Parking Problem and Robin Hood Linear Probing Hashing with Buckets

dmtcs:519 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, Vol. 12 no. 2
Distributional Analysis of the Parking Problem and Robin Hood Linear Probing Hashing with Buckets

Authors: Viola, Alfredo

This paper presents the first distributional analysis of both, a parking problem and a linear probing hashing scheme with buckets of size b. The exact distribution of the cost of successful searches for a b alpha-full table is obtained, and moments and asymptotic results are derived. With the use of the Poisson transform distributional results are also obtained for tables of size m and n elements. A key element in the analysis is the use of a new family of numbers, called Tuba Numbers, that satisfies a recurrence resembling that of the Bernoulli numbers. These numbers may prove helpful in studying recurrences involving truncated generating functions, as well as in other problems related with buckets.


Source : oai:HAL:hal-00990469v1
Volume: Vol. 12 no. 2
Published on: January 1, 2010
Submitted on: March 26, 2015
Keywords: Distributional Analysis,Hashing,Linear Probing,Buckets,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Consultation statistics

This page has been seen 52 times.
This article's PDF has been downloaded 221 times.