Title :
A partitioning method for grid file directories
Author :
Chun, Sei H. ; Hedrick, G.E. ; Lu, Huizhu ; Fisher, D.D.
Author_Institution :
Dept. of Comput. & Inf. Sci., Oklahoma State Univ., Stillwater, OK, USA
Abstract :
The grid file can be used for the implementation of a database to handle range queries and partially specified queries. Although an upper bound of two disc accesses for a single record retrieval is guaranteed, the number of directory entries is an exponential function of the number of data buckets if the data distribution is heavily non uniform. A new method is presented for partitioning the search space for constructing a grid directory. It improves the ratio of the number of directory entries to the number of data buckets. The directory expansion appears to have a quadratic or cubic rate when the data distribution is non uniform. An implementation of the method is presented. Simulation results are given for both the traditional grid file partitioning method and the new method
Keywords :
database management systems; information retrieval; records management; cubic rate; data buckets; data distribution; directory entries; directory expansion; disc accesses; exponential function; grid file directories; grid file partitioning method; partially specified queries; range queries; search space; single record retrieval; upper bound; Grid computing; Information retrieval; Query processing; Spatial databases; Upper bound;
Conference_Titel :
Computer Software and Applications Conference, 1989. COMPSAC 89., Proceedings of the 13th Annual International
Conference_Location :
Orlando, FL
Print_ISBN :
0-8186-1964-3
DOI :
10.1109/CMPSAC.1989.65095
