×

The diagonal Poisson transform and its application to the analysis of a hashing scheme. (English) Zbl 0870.68076

Summary: 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.

MSC:

68W10 Parallel algorithms in computer science
68P10 Searching and sorting

Software:

Maple
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abramowitz, Handbook of Mathematical Functions (1972)
[2] Amble, Ordered hash tables, Comput. J. 17 (2) pp 135– (1974) · Zbl 0282.68009
[3] Brent, Reducing the retrieval time of scatter storage techniques, Commun. ACM 16 (2) pp 105– (1973) · Zbl 0251.68019
[4] Broder, NATO Advance Science Institute Series. Series F: Computer and System Sciences 12, in: Combinatorial Algorithms on Words pp 229– (1985) · doi:10.1007/978-3-642-82456-2_15
[5] S. Carlsson J. I. Munro P. V. Poblete On linear probing hashing 1987
[6] A. Cauchy Exercises de mathématiques 1826 62 73
[7] P. Celis 1986
[8] J. P. Celis P.-Å. Larson J. I. Munro Robin Hood hashing 26th IEEE Symposium on the Foundations of Computer Science 1985 281 288
[9] Char, MAPLE V Reference Manual (1991)
[10] Compton, Excepted deadlock time in a multiprocessing system, J. ACM 42 (3) pp 562– (1995) · Zbl 0885.68040
[11] Comtet, Advanced Combinatorics (1974) · doi:10.1007/978-94-010-2196-8
[12] Consul, Generalized Poisson Distributions. Properties and Applications (1989)
[13] Evgrafov, Analytic Functions (1978)
[14] Fagin, Extendible hashing–a fast access method for dynamic files, ACM Trans. Database Syst. 4 (3) pp 315– (1979)
[15] P. Flajolet 1995
[16] Flajolet, Mellin transforms and asymptotics; harmonic sums, Theor. Comput. Sci. 144 pp 1– (1995) · Zbl 0869.68057
[17] Flajolet, On Ramanujan’s Q-function, J. Comput. Appl. Math. 58 (1) pp 103– (1995) · Zbl 0826.33001
[18] Flajolet, The first cycles in an evolving graph, Discrete Math. 75 pp 167– (1989) · Zbl 0696.05045
[19] Flajolet, The average height of binary trees and other simple trees, J. Comput. Syst. Sci. 25 pp 171– (1982) · Zbl 0499.68027
[20] Flajolet, Lecture Notes in Computer Science 434, in: Advances in Cryptology pp 329– (1989)
[21] Flajolet, Singularity analysis of generating functions, SIAM J. Discrete Math. 3 (2) pp 216– (1990) · Zbl 0712.05004
[22] P. Flajolet R. Sedgewick The average case analysis of algorithms: complex asymptotics and generating functions 1993
[23] P. Flajolet R. Sedgewick The average case analysis of algorithms: counting and generating function 1993
[24] Gonnet, Handbook of Algorithms and Data Structure (1991)
[25] Gonnet, Efficient ordering of hash tables, SIAM J. Comput. 8 (3) pp 463– (1979) · Zbl 0412.68058
[26] Gonnet, The analysis of linear probing sort by the use of a new mathematical transform, J. Alg. 5 pp 451– (1984) · Zbl 0606.68058
[27] Goulden, Combinatorial Enumeration (1983)
[28] Graham, Concrete Mathematics (1989)
[29] Hardy, An Introduction to the Theory of Numbers (1979) · Zbl 0423.10001
[30] Jacquet, LNCS Vol. 214, in: CAAP’86, Proc. 11th Colloquium on Trees in Algebra and Programming pp 196– (1986)
[31] Jacquet, Ultimate characterizations of the burst response of an interval searching algorithm: a study of a functional equation, SIAM J. Comput. 8 pp 777– (1989) · Zbl 0679.68052
[32] P. Jacquet W. Szpankowski A functional equation arising in the analysis of algorithms STOC 780 789 1994
[33] Jacquet, Asymptotic behaviour of the Lempel-Ziv parsing scheme and digital search trees, Theor. Comput. Sci. 144 pp 161– (1995) · Zbl 0874.68179
[34] Kløve, Bounds for the worst case probability of undetected error, IEEE Inf. Theory 41 pp 298– (1995) · Zbl 0828.94019
[35] Knuth, Fundamental Algorithms 1 (1968)
[36] Knuth, Seminumerical Algorithms 2 (1969)
[37] Knuth, Sorting and Searching 3 (1973)
[38] Knuth, Analysis of optimum caching, J. Alg. 6 pp 181– (1985) · Zbl 0594.68016
[39] Knuth, T. Łuczak, and B. Pittel, The birth of the giant component, Random Struct. Alg. 4 pp 233– (1993) · Zbl 0795.05127
[40] Knuth, A recurrence related to trees, Proc. Amer. Math. Soc. 105 pp 335– (1989) · Zbl 0672.41024 · doi:10.1090/S0002-9939-1989-0949878-9
[41] Knuth, Activity in an interleaved memory, IEEE Trans. Comput. C-24 pp 943– (1975)
[42] Knuth, The expected linearity of a simple equivalence algorithm, Theor. Comput. Sci. 6 pp 281– (1978) · Zbl 0377.68024
[43] Louchard, Average profile and limiting distribution for a phrase size in the Lempel-Ziv parsing algorithm, IEEE Inf. Theory 41 pp 478– (1995) · Zbl 0832.68068
[44] J. W. Moon Counting Labelled Trees 1970
[45] Odlyzko, Periodic oscillations of coefficients of power series that satisfy functional equations, Adv. Math. 44 pp 180– (1982) · Zbl 0484.30002
[46] Olver, Asymptotics and Special Functions (1974)
[47] Poblete, Approximating functions by their Poisson transform, Inf. Process. Lett. 23 pp 127– (1986) · Zbl 0654.65012
[48] Poblete, Last-come-first-served hashing, J. Alg. 10 pp 228– (1989) · Zbl 0685.68025
[49] P. V. Poblete A. Viola J. I. Munro The analysis of a hashing scheme by a new transform 2nd European Symposium on Algorithms 1994 94 105
[50] Ramanujan, Question 294, J. Ind. Math. Soc. 3 pp 128– (1911)
[51] Ramanujan, On question 294, J. Ind. Math. Soc. 4 pp 151– (1912)
[52] Riordan, Combinatorial Identities (1968)
[53] Szpankowski, On asymptotics of certain sums arising in coding theory, IEEE Trans. Inf. Theory 41 pp 2087– (1995) · Zbl 0849.94025
[54] van Lint, Introduction to Coding Theory (1982) · doi:10.1007/978-3-662-07998-0
[55] A. Viola Analysis of hashing algorithms and a new mathematical transform 1995
[56] Wilf, Generating functionology (1994)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.