Nordic Journal of Computing Bibliography

C.-H. Ang and H. Samet. Approximate Average Storage Utilization of Bucket Methods with Arbitrary Fanout. Nordic Journal of Computing, 3(3):280-291, Fall 1996.
Abstract

The approximate average storage utilization of bucket methods with fanout of n, assuming a uniform distribution of data, is shown to depend only on the fanout and not on any other factors such as the directory structure. It obeys the formula (ln n)/(n-1). The analysis makes use of a generalization of previously published methods for n=2 and n=4 and its predictions match these results. The formula is applicable to methods that are based on digital searching (e.g., tries) or balancing rather than comparison-based methods. The formula is also used to detect an erroneous statement about the average storage utilization of a ternary system in Nievergelt, J., Hinterberger, H., and Sevcik, K. C. 1984. The grid file: an adaptable, symmetric multikey file structure. ACM Transactions on Database Systems 9, 1 (March), 38-71.

Categories and Subject Descriptors: D.4.3 [Operating Systems]: File Systems Management; E.1 [Data Structures]; E.2 [Data Storage Representations]; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; H.2.2 [Database Management]: Physical Design

Additional Key Words and Phrases: data structures, analysis of algorithms, bucket methods, average storage utilization, B-tree, Grid file, EXHASH, EXCELL, quadtries, ternary system

Selected references


Shortcuts:

  • Nordic Journal of Computing homepage
  • Bibliography top level
  • Nordic Journal of Computing Author Index
  • Search the HBP database