Geodesic
Distributional Analysis of the Parking Problem and Robin Hood Linear Probing Hashing with Buckets
Discrete mathematics & theoretical computer science, Tome 12 (2010) no. 2.

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2010_12_2_a14,
     author = {Viola, Alfredo},
     title = {Distributional {Analysis} of the {Parking} {Problem} and {Robin} {Hood} {Linear} {Probing} {Hashing} with {Buckets}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {12},
     number = {2},
     year = {2010},
     doi = {10.46298/dmtcs.519},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.519/}
}
TY  - JOUR
AU  - Viola, Alfredo
TI  - Distributional Analysis of the Parking Problem and Robin Hood Linear Probing Hashing with Buckets
JO  - Discrete mathematics & theoretical computer science
PY  - 2010
VL  - 12
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.519/
DO  - 10.46298/dmtcs.519
LA  - en
ID  - DMTCS_2010_12_2_a14
ER  - 
%0 Journal Article
%A Viola, Alfredo
%T Distributional Analysis of the Parking Problem and Robin Hood Linear Probing Hashing with Buckets
%J Discrete mathematics & theoretical computer science
%D 2010
%V 12
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.519/
%R 10.46298/dmtcs.519
%G en
%F DMTCS_2010_12_2_a14
Viola, Alfredo. Distributional Analysis of the Parking Problem and Robin Hood Linear Probing Hashing with Buckets. Discrete mathematics & theoretical computer science, Tome 12 (2010) no. 2. doi : 10.46298/dmtcs.519. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.519/

Cité par Sources :