The Maximum Size of Dynamic Data Structures

DOI10.1137/0220050MaRDI QIDQ3982711zbMATH OpenOpenAlexFDO

Authors Claire Kenyon-Mathieu, Jeffrey Scott Vitter

Publication date 26 June 1992

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

Full work available at URL http://hdl.handle.net/1808/7172

zbMATH Keywords

dictionariesfile historieshashinglazy deletionslistsMarkov processoccupancy distributionpriority queuesqueueing theorysweeplinesymbol tablesVLSI

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Maximum queue size and hashing with lazy deletion
• Data Structures' Maxima
• Dynamic algorithms in D. E. Knuth's model: A probabilistic analysis
• Data structures with dynamical random transitions

Cited in

(6)

• Experiments on the practical I/O efficiency of geometric algorithms: Distribution sweep versus plane sweep
• Data Structures' Maxima
• Experiments on the practical I/O efficiency of geometric algorithms: Distribution sweep vs. plane sweep
• The exhaustion of shared memory: Stochastic results
• Random trees in queueing systems with deadlines
• Maximum queue size and hashing with lazy deletion

This page was built for publication: The Maximum Size of Dynamic Data Structures

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