The Grid File: An Adaptable, Symmetric Multikey File Structure

ABSTRACT

Traditional file structures that provide multikey access to records, for example, inverted files, are extensions of file structures originally designed for single-key access. They manifest various deficiencies in particular for multikey access to highly dynamic files. We study the dynamic aspects of file structures that treat all keys symmetrically, that is, file structures which avoid the distinction between primary and secondary keys. We start from a bitmap approach and treat the problem of file design as one of data compression of a large sparse matrix. This leads to the notions of a grid partition of the search space and of a grid directory, which are the keys to a dynamic file structure called the grid file. This file system adapts gracefully to its contents under insertions and deletions, and thus achieves an upper bound of two disk accesses for single record retrieval; it also handles range queries and partially specified queries efficiently. We discuss in detail the design decisions that led to the grid file, present simulation results of its behavior, and compare it to other multikey access file structures.

REFERENCES

• 1: D. S. Batory, On searching transposed files, ACM Transactions on Database Systems (TODS), v.4 n.4, p.531-544, Dec. 1979 [doi>10.1145/320107.320125]
• 2: Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
• 3: BENTLEY, J.L. Multidimensional binary search trees in database applications. IEEE Trans. Softw. Eng. SE-5, 4 (July 1979), 333-340.
• 4: Walter A. Burkhard, Interpolation-based index maintenance, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia [doi>10.1145/588058.588070]
• 5: R. G. Casey, Design of tree structures for efficient querying, Communications of the ACM, v.16 n.9, p.549-556, Sept. 1973 [doi>10.1145/362342.362353]
• 6: Ronald Fagin , Jurg Nievergelt , Nicholas Pippenger , H. Raymond Strong, Extendible hashing—a fast access method for dynamic files, ACM Transactions on Database Systems (TODS), v.4 n.3, p.315-344, Sept. 1979 [doi>10.1145/320083.320092]
• 7: FINKEL, R.A., AND BENTLEY, J.L. Quad trees--a data structure for retrieval on composite keys. Acta Inf. 4 {1974), 1-9.
• 8: Gaston H. Gonnet , Per Åke Larson, External hasing with limited internal storage, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588153]
• 9: GUETING, H., AND KRIEGEL, H.P. Multidimensional B-tree: an efficient dynamic file structure for exact match queries. Forschungsbericht Nr. 105, Informatik, Univ. Dortmund, Dortmund, West Germany, 1980.
• 10: H{NRICHS, K., AND NIEVERGELT, J. The grid file: a data structure designed to support proximity queries on spatial objects. In Proc. Workshop on Graph Theoretic Concepts in Computer Science (Osnabruck, 1983).
• 11: H{NTERBERGER, H., AND NIEVERGELT, J. Concurrency control in two-level file structures. Working paper, Informatik, ETH Zurich, 1983.
• 12: J0SHI, S.M., SANYAL, S., BANERJEE, S., AND SRIKUMAR, S. Using grid files for a relational database management system. Speech and Digital Systems Group, Tata Institute of Fundamental Research, Homi Bhabha Road, Bombay 400 005, India.
• 13: KASHYAP, R.L., SUBAS, S.K.C., AND YAO, S.B. Analysis of the multiattribute tree database organization. IEEE Trans. Softw. Eng. 2, 6 (Nov. 1977).
• 14: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 15: D. T. Lee , C. K. Wong, Quintary trees: a file structure for multidimensional datbase sytems, ACM Transactions on Database Systems (TODS), v.5 n.3, p.339-353, Sept. 1980 [doi>10.1145/320613.320618]
• 16: L}TWXN, W. Linear hashing: a new tool for file and table addressing. In Proc. 6th international Conference on Very Large Data Bases, 1980, pp. 212-223.
• 17: LIOU, J.H., AND YAO, S.S. Multidimensional clustering for database organizations. Inf. Syst. 2 (1977), 187-198.
• 18: V. Y. Lum, Multi-attribute retrieval with combined indexes, Communications of the ACM, v.13 n.11, p.660-665, Nov 1970 [doi>10.1145/362790.362794]
• 19: BARNES, M.C., COLLENS, D.S. Storing hierarchic database structures in transposed form. Datafair, 1973.
• 20: MERRETT, T.H. Multidimensional paging for efficient database querying. In Proc. ICMOD (Milano, Italy, June 1978), pp. 277-289.
• 21: MERRETT, T.H., AND OTOO, E.J. Dynamic multipaging: a storage structure for large shared data banks. Rep. SOCS-81-26, McGill Univ., 1981.
• 22: James K. Mullin, Retrieval—Update speed tradeoffs using combined indices, Communications of the ACM, v.14 n.12, p.775-776, Dec. 1971 [doi>10.1145/362919.362933]
• 23: Jürg Nievergelt, Trees as Data and File Structures, Proceedings of the 6th Colloquium on Trees in Algebra and Programming, p.35-45, March 05-07, 1981
• 24: Jürg Nievergelt , Hans Hinterberger , Kenneth C. Sevcik, The Grid File: An Adaptable, Symmetric Multi-Key File Structure, Proceedings of the 3rd Conference of the European Cooperation in Informatics on Trends in Information Processing Systems, p.236-251, October 20-22, 1981
• 25: ORENSTEIN J.A. Multidimensional TRIEs used for associative searching. Inf. Process. Left. 14, 4 (June 1982), 150-157.
• 26: John L. Pfaltz , William J. Berman , Edgar M. Cagley, Partial-match retrieval using indexed descriptor files, Communications of the ACM, v.23 n.9, p.522-528, Sept. 1980 [doi>10.1145/359007.359013]
• 27: RIVEST, R.L. Partial-match retrieval algorithms. SIAM J. Comput. 5, 1 (1976), 19-50.
• 28: John T. Robinson, The K-D-B-tree: a search structure for large multidimensional dynamic indexes, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582321]
• 29: James B. Rothnie, Jr. , Tomas Lozano, Attribute based file organization in a paged memory environment, Communications of the ACM, v.17 n.2, p.63-69, Feb. 1974 [doi>10.1145/360827.360831]
• 30: SCHEUERMANN, P., AND OUKSEL, M. Multidimensional B-trees for associative searching in database systems, Inf. Syst. 7, 2 (1982), 123-137.
• 31: TAMMINEN, M. The extendible cell method for closest point problems. BIT 22 (1982), 27-41.
• 32: VALLARINO, O. On the use of bit maps for multiple key retrieval. ACM SIGPLAN Notices 11, (Mar. 1976), 108-114.