Analysis of bounded disorder file organization

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.

REFERENCES

• BD59: Barton, DE. and Dawd, F N Combmatoru~l extreme value dtsmbutlons Mathematd~ 6(1959), 63-76
• BZ86: Baeza-Yates, R A The expected behavzor of B+- trees Deparunent of Computer Science, Umvers~ty of Waterloo, Research report CS-86-68(1986)
• CW79: Carter, L J and Wegman, M.L Umversal classes of hash funcnons. Journal of Computer and System Sciences, 18, 2(1979), 143-145
• DB62: Dav~ F N and Barton, D E Combmatorml Chance. London: Griffin, (1962)
• GL88: Gaston H. Gonnet , Per-Åke Larson, External hashing with limited internal storage, Journal of the ACM (JACM), v.35 n.1, p.161-184, Jan. 1988 [doi>10.1145/42267.42274]
• GM84: Gaston H. Gonnet , J. Ian Munro, A linear probing sort and its analysis(Preliminary Draft), Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.90-95, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802461]
• JK77: Johnson, N L and Kotz, S Urn Models and Their Apphcanon John Wdey and Sons, New York, (1977)
• KS78: Kolchm, V F, Sevast'yanov, B A and Cl~styakov, V P. Random allocations John Wdey and Sons, New York, (1978)
• LK84: Per-Åke Larson , Ajay Kajla, File organization: implementation of a method guaranteeing retrieval in one access, Communications of the ACM, v.27 n.7, p.670-677, July 1984 [doi>10.1145/358105.358193]
• LL86: Witold Litwin , David B. Lomet, The Bounded Disorder Access Method, Proceedings of the Second International Conference on Data Engineering, p.38-48, February 05-07, 1986
• LM86: Lomet, D B A Simple Bounded Disorder Fde Orgamzat~on Wuh Good Performance Wang Institute of Graduate Stuches, Techmcal report TR-86- 13(1986)
• LM87: David B. Lomet, Partial expansions for file organizations with an index, ACM Transactions on Database Systems (TODS), v.12 n.1, p.65-84, March 1987 [doi>10.1145/12047.12049]
• LR80: Larson, P A Linear Hashing wzth Parnal Expanston Proc 6th Conf. on VLDB, Montreal Canada, (1980), 224-232
• LR84: Larson, P A Linear hashing with separators - a dynamzc hashmg scheme ach:evmg one access retrteval Umvers~ty of Waterloo, Techmcal report CS-84-23(1984)
• LR85: Per-Ake Larson , M. V. Ramakrishna, External perfect hashing, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.190-200, May 1985, Austin, Texas, United States
• LT78: Lltwm, W Virtual Hashmg a dynamtcally changmg hashtng Proc 4th Conf on VLDB, Berhn, (1978), 517-523
• LT80: ~twm, W Linear haslung a new tool for file and table addressing Proe 6th Conf on VLDB, Montreal Canada, (1980), 212-223
• LT81: Lltwm, W Trte haslung Proe ACM-SIGMOD Conf on Management of Data, Ann Arbor, (1981), 19-29
• MR83: Mawson, H G The program comple.xJty of searchmga table. Proe 24th Syrup on Foundauon of Computer Science, IEEE Computer Society, (1983), 40-47.
• MR84: Matrson, H G The program complexaty of searchmga table Ph D thes~s, Department of Computer Scaence, Stanford Umverslty, Report number STAN-CS-83-988(1984).
• NS60: Newman, D J and Shepp, L The double dtme cup problem Amer Math Monthly, 67(1960), 58-61.
• NY85: R. M. Norton , D. P. Yeager, A probability model for overflow sufficiency in small hash tables, Communications of the ACM, v.28 n.10, p.1068-1075, Oct. 1985 [doi>10.1145/4372.4377]
• RL88: Ramalmshna M V and ~n P A Fde or&amzatton using composite perfect haslung (To appear) ACM Trans on Database Systems
• RM86: M V Ramakrishna, Perfect hashing for external files, University of Waterloo, Waterloo, Ont., Canada, 1986
• RM87: Ramaknshna M V Computing the probab~hty of hash table~urn overflow Commumcauons m Stausues - Theory and Methods, 16, 11(1987), 3343- 3353
• RM88: M. V. Ramakrishna, An Exact Probability Model for Finite Hash Tables, Proceedings of the Fourth International Conference on Data Engineering, p.362-368, February 01-05, 1988
• YA78: Yao, C C On Random 2-3 Trees Acta Informauca, 9, (1978), 159-170p117-ramakrishna