Premium
The Diagonal Poisson Transform and its application to the analysis of a hashing scheme
Author(s) -
Poblete Patricio V.,
Viola Alfredo,
Munro J. Ian
Publication year - 1997
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199701/03)10:1/2<221::aid-rsa12>3.0.co;2-b
Subject(s) - diagonal , poisson distribution , heuristic , mathematics , hash function , algorithm , computer science , mathematical optimization , statistics , geometry , computer security
We present an analysis of the effect of the last‐come‐first‐served heuristic on a linear probing hash table. We study the behavior of successful searches, assuming searches for all elements of the table are equally likely. It is known that the Robin Hood heuristic achieves minimum variance over all linear probing algorithms. We show that the last‐come‐first‐served heuristic achieves this minimum up to lower‐order terms. An accurate analysis of this algorithm is made by introducing a new transform which we call the Diagonal Poisson Transform as it resembles the Poisson Transform. We present important properties of this transform, as well as its application to solve some classes of recurrences, find inverse relations, find asymptotics, and obtain several generalizations of Abel's summation formula. We feel the introduction of this transform is the main contribution of the paper. © 1997 John Wiley & Sons, Inc. Random Struct. Alg. , 10 , 221–255 (1997)