TY - GEN
T1 - The asymptotic evolution of data structures
AU - Maier, Robert S.
N1 - Funding Information:
*This work was supportedi n part by AFOSR grant 88-0189.
Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1990.
PY - 1990
Y1 - 1990
N2 - The evolution of certain pointer-based implementations of dictionaries, linear lists and priority queues is studied. Under the assumption of equiprobability of histories, i.e., of paths through the internal state space of the implementation, the n → ∞ asymptotics of the space and time costs of a sequence of n supported operations are computed. For list implementations the mean integrated spatial cost is asymptotically proportional to n2, and its standard deviation to n3/2. For d-heap implementations of priority queues the mean integrated space cost grows only as n2/√log n, i.e. more slowly than the worst-case integrated cost. The standard deviation grows as n3/2. These asymptotics reflect the convergence as n → ∞ of the normalized structure sizes to datatype-dependent deterministic functions of time, as earlier discovered by Louchard. This phenomenon is clarified with the aid of large deviation theory, and path integral techniques.
AB - The evolution of certain pointer-based implementations of dictionaries, linear lists and priority queues is studied. Under the assumption of equiprobability of histories, i.e., of paths through the internal state space of the implementation, the n → ∞ asymptotics of the space and time costs of a sequence of n supported operations are computed. For list implementations the mean integrated spatial cost is asymptotically proportional to n2, and its standard deviation to n3/2. For d-heap implementations of priority queues the mean integrated space cost grows only as n2/√log n, i.e. more slowly than the worst-case integrated cost. The standard deviation grows as n3/2. These asymptotics reflect the convergence as n → ∞ of the normalized structure sizes to datatype-dependent deterministic functions of time, as earlier discovered by Louchard. This phenomenon is clarified with the aid of large deviation theory, and path integral techniques.
KW - Dynamic data structures
KW - Expected costs
KW - Large deviations
KW - Stochastic modelling
UR - http://www.scopus.com/inward/record.url?scp=85032205081&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85032205081&partnerID=8YFLogxK
U2 - 10.1007/3-540-53504-7_57
DO - 10.1007/3-540-53504-7_57
M3 - Conference contribution
AN - SCOPUS:85032205081
SN - 9783540535041
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 13
EP - 23
BT - Advances in Computing and Information – ICCI 1990 - International Conference on Computing and Information, Proceedings
A2 - Koczkodaj, Waldemar W.
A2 - Akl, Selim G.
A2 - Fiala, Frantisek
PB - Springer-Verlag
T2 - International Conference on Computing and Information, ICCI 1990
Y2 - 23 May 1990 through 26 May 1990
ER -