Skip to Main content Skip to Navigation
Journal articles

Distributional Analysis of the Parking Problem and Robin Hood Linear Probing Hashing with Buckets

Abstract : 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [47 references]  Display  Hide  Download

https://hal.inria.fr/hal-00990469
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Tuesday, May 13, 2014 - 3:37:55 PM
Last modification on : Friday, February 22, 2019 - 11:16:45 AM
Long-term archiving on: : Monday, April 10, 2017 - 10:15:10 PM

File

1359-5102-2-PB.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00990469, version 1

Collections

Citation

Alfredo Viola. Distributional Analysis of the Parking Problem and Robin Hood Linear Probing Hashing with Buckets. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, 12 (2), pp.307-332. ⟨hal-00990469⟩

Share

Metrics

Record views

117

Files downloads

1837