Loading...
The Maximum Size of Dynamic Data Structures
Kenyon-Mathieu, Claire M. Vitter, Jeffrey Scott
Kenyon-Mathieu, Claire M.
Vitter, Jeffrey Scott
Citations
Altmetric:
Abstract
This paper develops two probabilistic methods that allow the analysis of the maximum data
structure size encountered during a sequence of insertions and deletions in data structures such as priority queues, dictionaries, linear lists, and symbol tables, and in sweepline structures for geometry and Very-Large-Scale-Integration (VLSI) applications. The notion of the "maximum" is basic to issues of resource preallocation. The methods here are applied to combinatorial models of file histories and probabilistic models, as well as to a non-Markovian process (algorithm) for processing sweepline information in an efficient way, called "hashing with lazy deletion" (HwLD). Expressions are derived for the expected maximum data
structure size that are asymptotically exact, that is, correct up to lower-order terms; in several cases of interest the expected value of the maximum size is asymptotically equal to the maximum expected size. This solves several open problems, including longstanding questions in queueing theory. Both of these approaches are robust and rely upon novel applications of techniques from the analysis of algorithms. At a high level, the first method isolates the primary contribution to the maximum and bounds the lesser effects. In the second technique the continuous-time probabilistic model is related to its discrete analog--the maximum slot occupancy in hashing.
Description
Date
1991-10
Journal Title
Journal ISSN
Volume Title
Publisher
Society for Industrial and Applied Mathematics
Research Projects
Organizational Units
Journal Issue
Keywords
Algorithm analysis, Hashing, Lazy deletion, Maximum, Queueing theory, Markov process, Occupancy distribution, Data structures, File histories, Priority queues, Dictionaries, Lists, Symbol tables, Sweepline, Computational geometry, VLSI
Citation
C. M. Kenyon-Mathieu and J. S. Vitter. “The Maximum Size of Dynamic Data Structures,” SIAM Journal on Computing, 20(5), October 1991, 807–823. An extended abstract appears in “General Methods for the Analysis of the Maximum Size of Dynamic Data Structures,” Proceedings of the 16th Annual International Colloquium on Automata, Languages, and Programming (ICALP ’89), Stresa, Italy, July 1989, published in Lecture Notes in Computer Science, 372, Springer, Berlin, Germany, 473–487. http://dx.doi.org/10.1137/0220050