ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Analysis of Bounded Disorder File Organization.

M. V. Ramakrishna, P. Mukhopadhyay: Analysis of Bounded Disorder File Organization. PODS 1988: 117-125
@inproceedings{DBLP:conf/pods/RamakrishnaM88,
  author    = {M. V. Ramakrishna and
               P. Mukhopadhyay},
  title     = {Analysis of Bounded Disorder File Organization},
  booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, March 21-23, 1988, Austin,
               Texas},
  publisher = {ACM},
  year      = {1988},
  isbn      = {0-89791-263-2},
  pages     = {117-125},
  ee        = {http://doi.acm.org/10.1145/308386.308424, db/conf/pods/RamakrishnaM88.html},
  crossref  = {DBLP:conf/pods/88},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Recently Litwin and Lomet proposed the Bounded Disorder (BD) file organization which uses a combination of hashing and tree indexing. Lomet provided an approximate analysis with a mention of the difficulty involved in exact modeling and analysis. The performance analysis of the method involves solving a classical sequential occupancy problem. We encountered this problem in our attempt to obtain a general model for single access and almost single access retrieval methods developed in the recent years. In this paper, we develop a probability model and present some preliminary results of the exact analysis.

Copyright © 1988 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.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 21-23, 1988, Austin, Texas. ACM 1988, ISBN 0-89791-263-2
Contents BibTeX

Online Edition: ACM Digital Library

References

[BD59]
...
[BZ86]
...
[CW79]
Larry Carter, Mark N. Wegman: Universal Classes of Hash Functions. J. Comput. Syst. Sci. 18(2): 143-154(1979) BibTeX
[DB62]
...
[GL88]
Gaston H. Gonnet, Per-Åke Larson: External hashing with limited internal storage. J. ACM 35(1): 161-184(1988) BibTeX
[GM84]
Gaston H. Gonnet, J. Ian Munro: The Analysis of Linear Probing Sort by the Use of a New Mathematical Transform. J. Algorithms 5(4): 451-470(1984) BibTeX
[JK77]
...
[KS78]
...
[LK84]
Per-Åke Larson, Ajay Kajla: File Organization: Implementation of a Method Guaranteeing Retrieval in One Access. Commun. ACM 27(7): 670-677(1984) BibTeX
[LL86]
Witold Litwin, David B. Lomet: The Bounded Disorder Access Method. ICDE 1986: 38-48 BibTeX
[LM86]
...
[LM87]
David B. Lomet: Partial Expansions for File Organizations with an Index. ACM Trans. Database Syst. 12(1): 65-84(1987) BibTeX
[LR80]
Per-Åke Larson: Linear Hashing with Partial Expansions. VLDB 1980: 224-232 BibTeX
[LR84]
...
[LR85]
Per-Åke Larson, M. V. Ramakrishna: External Perfect Hashing. SIGMOD Conference 1985: 190-200 BibTeX
[LT78]
Witold Litwin: Virtual Hashing: A Dynamically Changing Hashing. VLDB 1978: 517-523 BibTeX
[LT80]
Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223 BibTeX
[LT81]
Witold Litwin: Trie Hashing. SIGMOD Conference 1981: 19-29 BibTeX
[MR83]
Harry G. Mairson: The Program Complexity of Searching a Table. FOCS 1983: 40-47 BibTeX
[MR84]
...
[NS60]
...
[NY85]
R. M. Norton, D. P. Yeager: A Probability Model for Overflow Sufficiency in Small Hash Tables. Commun. ACM 28(10): 1068-1075(1985) BibTeX
[RL88]
M. V. Ramakrishna, Per-Åke Larson: File Organization Using Composite Perfect Hashing. ACM Trans. Database Syst. 14(2): 231-263(1989) BibTeX
[RM86]
...
[RM87]
...
[RM88]
M. V. Ramakrishna: An Exact Probability Model for Finite Hash Tables. ICDE 1988: 362-368 BibTeX
[YA78]
Andrew Chi-Chih Yao: On Random 2-3 Trees. Acta Inf. 9: 159-170(1978) BibTeX

Referenced by

  1. M. V. Ramakrishna: Bounded Disorder File Organization. IEEE Trans. Knowl. Data Eng. 6(1): 79-85(1994)
  2. Gabriel Matsliach: Performance Analysis of File Organizations that Use Multibucket Data Leaves with Partial Expansions. ACM Trans. Database Syst. 18(1): 157-180(1993)
  3. Gabriel Matsliach: Performance Analysis of File Organizations that Use Multi-Bucket Data Leaves with Partial Expansions. PODS 1991: 164-180
  4. Gabriel Matsliach, Oded Shmueli: Maintaining Bounded Disorder Files in Multiprocessor Multi-Disk Environments. ICDT 1990: 109-125
  5. M. V. Ramakrishna, Per-Åke Larson: File Organization Using Composite Perfect Hashing. ACM Trans. Database Syst. 14(2): 231-263(1989)
  6. M. V. Ramakrishna: Hashing in Practive, Analysis of Hashing and Universal Hashing. SIGMOD Conference 1988: 191-199
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:33:53 2009