A Queueing Analysis of Hashing with Lazy Deletion

DOI10.1137/0216073zbMATH Open0626.60101DBLPjournals/siamcomp/MorrisonSW87OpenAlexW2060392318WikidataQ56559673 ScholiaQ56559673MaRDI QIDQ3029974FDOQ3029974

Authors: Larry Shepp, Christopher J. Van Wyk, John A. Morrison 

Publication date: 1987

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://repository.upenn.edu/statistics_papers/409

Recommendations

• The complexity of hashing with lazy deletion
• Maximum queue size and hashing with lazy deletion
• The effect of deletions on different insertion disciplines for hash tables
• On deletions in open addressing hashing
• Deletion Algorithms for Coalesced Hashing

zbMATH Keywords

storagedynamic dictionaryfirst passge timeslazy deletion

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Queueing theory (aspects of probability theory) (60K25) Applications of queueing theory (congestion, allocation, storage, traffic, etc.) (60K30)

Cited In (8)

• Busy periods in a system with heterogeneous servers or channels
• Maximum queue size and hashing with lazy deletion
• Exact results for the distribution of the partial busy period for a multi-server queue
• An approximate analysis of the performance of extendible hashing with elastic buckets
• Hashing lazy numbers
• Busy periods in M/M/\(\infty\) systems with heterogeneous servers
• Analysis of Robin Hood and Other Hashing Algorithms Under the Random Probing Model, With and Without Deletions
• The complexity of hashing with lazy deletion

This page was built for publication: A Queueing Analysis of Hashing with Lazy Deletion

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