The Diagonal Poisson Transform and its application to the analysis of a hashing scheme

DOI<221::AID-RSA12>3.0.CO;2-B 10.1002/(SICI)1098-2418(199701/03)10:1/2<221::AID-RSA12>3.0.CO;2-BzbMath0870.68076OpenAlexW1984102833MaRDI QIDQ3122915

Alfredo Viola, J. Ian Munro, Patricio V. Poblete

Publication date: 6 May 1997

Full work available at URL: https://doi.org/10.1002/(sici)1098-2418(199701/03)10:1/2<221::aid-rsa12>3.0.co;2-b

zbMATH Keywords

diagonal Poisson transformlinear probing hash tableRobin Hood heuristic

Mathematics Subject Classification ID

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

Related Items (2)

A unified approach to linear probing hashing with buckets ⋮ Analytical depoissonization and its applications

Uses Software

• Maple

Cites Work

• Unnamed Item
• Mellin transforms and asymptotics: Harmonic sums
• Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees
• The first cycles in an evolving graph
• Approximating functions by their Poisson transform
• Periodic oscillations of coefficients of power series that satisfy functional equations
• The average height of binary trees and other simple trees
• The expected linearity of a simple equivalence algorithm
• On Ramanujan's \(Q\)-function
• Singularity Analysis of Generating Functions
• An analysis of optimum caching
• The analysis of linear probing sort by the use of a new mathematical transform
• A Recurrence Related to Trees
• Efficient Ordering of Hash Tables
• Last-come-first-served hashing
• Expected deadlock time in a multiprocessing system
• Ultimate Characterizations of the Burst Response of an Interval Searching Algorithm: A Study of a Functional Equation
• Ordered hash tables
• Average profile and limiting distribution for a phrase size in the Lempel-Ziv parsing algorithm
• Bounds on the worst case probability of undetected error
• On asymptotics of certain sums arising in coding theory
• The birth of the giant component
• Reducing the retrieval time of scatter storage techniques

This page was built for publication: The Diagonal Poisson Transform and its application to the analysis of a hashing scheme