Analysis of bounded disorder file organization
- 1 March 1988
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 117-125
- https://doi.org/10.1145/308386.308424
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.Keywords
This publication has 11 references indexed in Scilit:
- File organization using composite perfect hashingACM Transactions on Database Systems, 1989
- External hashing with limited internal storageJournal of the ACM, 1988
- Partial expansions for file organizations with an indexACM Transactions on Database Systems, 1987
- Computing the probability of hash table/urn overflowCommunications in Statistics - Theory and Methods, 1987
- A probability model for overflow sufficiency in small hash tablesCommunications of the ACM, 1985
- External perfect hashingPublished by Association for Computing Machinery (ACM) ,1985
- File organizationCommunications of the ACM, 1984
- Universal classes of hash functionsJournal of Computer and System Sciences, 1979
- On random 2?3 treesActa Informatica, 1978
- The Double Dixie Cup ProblemThe American Mathematical Monthly, 1960