LINEARITY IN DIRECTORY GROWTH OF THE MULTILEVEL GRID FILE

The multilevel grid file (MLGF) is a multidimensional dynamic hashed f ile organization. Asymptotic directory growth, defined as the growth o f the directory as the data file expands, is an important factor for e valuating storage overhead of a multidimensional dynamic file organiza tion. In this article we implement the MLGF and examine the growth of its directory. The concepts and the architecture of the MLGF were intr oduced in refs [1,2]. We argue that the asymptotic directory growth of the MLGF is linearly dependent on the growth of the data file regardl ess of data distributions, data skew, or correlation among different o rganizing attributes. To justify this argument, we perform extensive e xperiments with various distributions of data: uniform, normal, and ex ponential distributions. We further perform experiments for more compl icated cases where the distributions are highly-skewed or highly-corre lated. The results show that the directory size of the MLGF increases linearly in the number of records independently of data distributions, data skew, or correlation, and the rates of increase are nearly const ant in all cases. The results also show that both of the blocking fact or and number of dimensions do not affect the linearity in directory g rowth of the MLGF. Such characteristics are important advantages of th e MLGF in comparison with other multidimensional file organizations in that storage requirement for the directory is minimized, and splittin g, merging, and hyperplane search operations are made easier. (C) 1997 Elsevier Science B.V.