Maximum size of a dynamic data structure: hashing with lazy deletion revisited (1992).

Content Provider	CiteSeerX
Author	Aldous, David Hofri, Micha Szpankowski, Wojciech
Abstract	We study the dynamic data structure management technique called Hashing with Lazy Deletion (HwLD). A table managed under HwLD is built via a sequence of insertions and deletions of items. When hashing with lazy deletions, one does not delete items as soon as possible, but keeps more items in the data structure than immediate-deletion strategies would. This deferral allows the use of a simpler deletion algorithm, leading to a lower overhead---in space and time---for the HwLD implementation. It is of interest to know how much extra space is used by HwLD. We investigate the maximum size and the excess space used by HwLD, under general probabilistic assumptions, using the methodology of queueing theory. In particular, we find that for the Poisson arrivals and general life-time distribution of items, the excess space does not exceed the number of buckets in HwLD. As a by-product of our analysis, we also derive the limiting distribution of the maximum queue length in an M jGj1 queueing syst...
File Format	PDF
Publisher Date	1992-01-01
Access Restriction	Open
Subject Keyword	Lazy Deletion Maximum Size Dynamic Data Structure Excess Space Hwld Implementation Immediate-deletion Strategy Dynamic Data Structure Management Technique Data Structure Much Extra Space General Life-time Distribution Poisson Arrival Maximum Queue Length General Probabilistic Assumption Simpler Deletion Algorithm
Content Type	Text