Carleton University
Technical Report TR-46
March 1984
A Mapping Function for the Directory of a Multidimensional Extendible Hashing
E.J. Otoo
Abstract
A generalization of the Extendible Hashing scheme of Fagin and others is presented for structuring files of records with d-attribute fields. This generalization reduces to the problem of defining a storage mapping for an extendible array with exponential varying order. We define such a function with element address computation in time 0(d), and we show how the result applies to the design of a multidimensional extendible hashing. Algorithms for searching, inserting and processing partial-match queries are presented and we discuss some peculiar characteristics of the scheme derived primarily by simulation studies done with both uniform and nonuniform distributed data.