ISSN:
1432-0541
Schlagwort(e):
Queues
;
Maximum
;
Hashing with lazy deletion
;
Data structures
;
File histories
;
Stacks
;
Priority queues
;
Linear lists
;
Symbol tables
;
Continued fractions
;
Orthogonal polynomials
;
Birth-and-death process
;
M/M/∞
;
M/G/∞
;
Transforms
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Informatik
,
Mathematik
Notizen:
Abstract We answer questions about the distribution of the maximum size of queues and data structures as a function of time. The concept of “maximum” occurs in many issues of resource allocation. We consider several models of growth, including general birth-and-death processes, the M/G/∞ model, and a non-Markovian process (data structure) for processing plane-sweep information in computational geometry, called “hashing with lazy deletion” (HwLD). It has been shown that HwLD is optimal in terms of expected time and dynamic space; our results show that it is also optimal in terms of expectedpreallocated space, up to a constant factor. We take two independent and complementary approaches: first, in Section 2, we use a variety of algebraic and analytical techniques to derive exact formulas for the distribution of the maximum queue size in stationary birth-and-death processes and in a nonstationary model related to file histories. The formulas allow numerical evaluation and some asymptotics. In our second approach, in Section 3, we consider the M/G/∞ model (which includes M/M/∞ as a special case) and use techniques from the analysis of algorithms to get optimal big-oh bounds on the expected maximum queue size and on the expected maximum amount of storage used by HwLD in excess of the optimal amount. The techniques appear extendible to other models, such as M/M/1.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF01759063
Permalink
