Deviation results for sparse tables in hashing with linear probing

DOI10.1007/S00440-021-01100-1zbMATH Open1493.60055arXiv1603.02235OpenAlexW3124151833MaRDI QIDQ2159253FDOQ2159253

Authors: Thierry Klein, Agnès Lagnoux, Pierre Petit 

Publication date: 28 July 2022

Published in: Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Abstract: We consider the model of hashing with linear probing and we establish the moderate and large deviations for the total displacement in sparse tables. In this context, Weibull-like-tailed random variables appear. Deviations for sums of such heavy-tailed random variables are studied in cite{Nagaev69-1,Nagaev69-2}. Here we adapt the proofs therein to deal with conditioned sums of such variables and solve the open question in cite{TFC12}. By the way, we establish the deviations of the total displacement in full tables, which can be derived from the deviations of empirical processes of i.i.d. random variables established in cite{Wu94}..

Full work available at URL: https://arxiv.org/abs/1603.02235

Recommendations

• The maximum displacement for linear probing hashing
• scientific article; zbMATH DE number 7703264
• On the analysis of linear probing hashing
• Individual Displacements in Hashing with Coalesced Chains
• Exact distribution of individual displacements in linear probing hashing

zbMATH Keywords

large deviationsBrownian motionempirical processesparking problemAiry distributionconditioned sums of i.i.d. random variableshashing with linear probingtriangular arrays and Weibull-like distributionŁukasiewicz random walk

Mathematics Subject Classification ID

Large deviations (60F10) Analysis of algorithms (68W40) Sums of independent random variables; random walks (60G50) Combinatorial probability (60C05)

Cites Work

• Asymptotic Statistics
• Analytic combinatorics
• Functional analysis, calculus of variations and optimal control
• Title not available (Why is that?)
• Large deviations of heavy-tailed sums with applications in insurance
• On the analysis of linear probing hashing
• Asymptotic distribution for the cost of linear probing hashing
• Individual displacements for linear probing hashing with different insertion policies
• Large deviations of sums of independent random variables
• Phase transition for Parking blocks, Brownian excursion and coalescence
• Title not available (Why is that?)
• Large-deviation results for triangular arrays of semiexponential random variables
• Integral Limit Theorems Taking Large Deviations Into Account When Cramér’s Condition Does Not Hold. II
• A simple proof of Sanov's theorem
• Integral Limit Theorems Taking Large Deviations into Account when Cramér’s Condition Does Not Hold. I
• Moment convergence in conditional limit theorems
• Title not available (Why is that?)
• A theorem about probabilities of large deviations with an application to queuing theory
• Large deviations, moderate deviations and LIL for empirical processes
• Title not available (Why is that?)
• Computer Science and Its Relation to Mathematics
• A conditional Berry-Esseen inequality
• Title not available (Why is that?)
• Parking functions, empirical processes, and the width of rooted labeled trees
• Conditional large and moderate deviations for sums of discrete random variables. Combinatoric applications
• A minmax theorem for concave-convex mappings with no regularity assumptions
• Parking with density

Cited In (2)

• Title not available (Why is that?)
• The maximum displacement for linear probing hashing

This page was built for publication: Deviation results for sparse tables in hashing with linear probing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2159253)