The Average Time Until Bucket Overflow.

Robert B. Cooper, Martin K. Solomon: The Average Time Until Bucket Overflow. ACM Trans. Database Syst. 9(3): 392-408(1984)

@article{DBLP:journals/tods/CooperS84,
  author    = {Robert B. Cooper and
               Martin K. Solomon},
  title     = {The Average Time Until Bucket Overflow},
  journal   = {ACM Trans. Database Syst.},
  volume    = {9},
  number    = {3},
  year      = {1984},
  pages     = {392-408},
  ee        = {http://doi.acm.org/10.1145/1270.318575, db/journals/tods/CooperS84.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

It is common for file structures to be divided into equal-length partitions, called buckets, into which records arrive for insertion and from which records are physically deleted. We give a simple algorithm which permits calculation of the average time until overflow for a bucket of capacity n records, assuming that record insertions and deletions can be modeled as a stochastic process in the usual manner of queueing theory. We present some numerical examples, from which we make some general observations about the relationships among insertion and deletion rates, bucket capacity, initial fill, and average time until overflow. In particular, we observe that it makes sense to define the stable point as the product of the arrival rate and the average residence time of the records; then a bucket tends to fill up to its stable point quickly, in an amount of time almost independent of the stable point, but the average time until overflow increases rapidly with the difference between the bucket capacity and the stable point.

Copyright © 1984 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/An3-1 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD2 or /dvd

BibTeX

References

[1]: Don S. Batory: Optimal File Designs and Reorganization Points. ACM Trans. Database Syst. 7(1): 60-81(1982) BibTeX
[2]: ...
[3]: Daniel P. Heyman: Mathematical Models of Database Degradation. ACM Trans. Database Syst. 7(4): 615-631(1982) BibTeX
[4]: ...
[5]: Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
[6]: Per-Åke Larson: Analysis of Index-Sequential Files with Overflow Chaining. ACM Trans. Database Syst. 6(4): 671-680(1981) BibTeX
[7]: ...
[8]: Páe Quittner, S. Csóka, S. Halász, D. Kotsis, K. Várnai: Comparison of Synonym Handling and Bucket Organization Methods. Commun. ACM 24(9): 579-583(1981) BibTeX
[9]: Michael Stonebraker, Eugene Wong, Peter Kreps, Gerald Held: The Design and Implementation of INGRES. ACM Trans. Database Syst. 1(3): 189-222(1976) BibTeX
[10]: ...

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]