Analysis of grid file algorithms
type: Item
instance of: scholarly article
title: Analysis of grid file algorithms
zbMATH Open document ID: 0568.68076
DOI: 10.1007/BF01934379
published in: BIT
publication date: 1985-01-01T00:00:00Z
review text: Grid file algorithms were suggested by \textit{J. Nievergelt, H. Hinterberger} and \textit{K. C. Sevcik} [ACM Trans. Database Syst. 9, 38-71 (1984)] to provide multi-key access to records in a dynamically growing file. We specify here two algorithms and derive the average sizes of the corresponding directories. We provide an asymptotic analysis. The growth of the indexes appears to be non-linear for uniform distributions: \(O(v^ c)\) or \(O(v^{\xi})\), where \(c=1+b^{-1}\), \(\xi =1+(s- 1)/(sb+1)\), s is the number of attributes being used, v the file size, and b the page capacity of the system. Finally we give corresponding results for biased distributions and compare transient phases.
Mathematics Subject Classification ID: 68P20
Mathematics Subject Classification ID: 68P05
zbMATH DE Number: 3907813
zbMATH Keywords: dynamic data structures
zbMATH Keywords: data bases
zbMATH Keywords: hashing
zbMATH Keywords: multi-key access
zbMATH Keywords: dynamically growing file
author: Mireille Régnier
MaRDI profile type: Publication
cites work: Interpolation-based index maintenance
cites work: Q5799604
cites work: Q3241504
cites work: Q3704890
cites work: Q4137395
cites work: Partial-match retrieval for dynamic files
cites work: Dynamic hashing
cites work: Analysis of Extendible Hashing
cites work: A storage scheme for extendible arrays
cites work: On the average height of trees in digital search and dynamic hashing
cites work: Q3217585
cites work: The extendible cell method for closest point problems
cites work: A note on the analysis of extendible hashing
description: scientific article; zbMATH DE number 3907813