Hashing, or address calculation, has traditionally been associated with the scattering of close records, and therefore with inefficiency for retrieval of range queries. But for answering small range queries it is possible to compromise between randomization and the togetherness of close records by hashing many intervals of keys—rather than many isolated keys—into each hash value. And for answering small region queries, i.e., conjunctions of small range queries, such “interval hashing” may be applied to each attribute of a record in a multiple-key hashing procedure. The resulting technique is called “box-array hashing,” since it maps an orthogonal array of boxes from the space of all possible records into each hash value. This paper analyzes the achievable efficiency of hashing techniques for answering small region queries, and presents strong analytic evidence suggesting that box-array hashing provides about the most efficient procedure for answering small region queries, among all hashing procedures of comparable randomization power.

All analysis of the achievable effictency of retrieval algorithms based on hashing for answermg partial-match queries is presented The remarkable power of hashing m hmmng the search of a given key value m a file is well known SLmilarly, R is possible to avoid searchmg major portions of a file m answering partialmatch or multlattnbute queries by hashing a multiattrlbute file into a number of buckets Multiple-key hashmg is a simple procedure for doing so and works by combining the effects of a number of hashing functions, one for each attribute m a record By usmg a measure of retrieval efficiency m which queries speofymg the same set of attributes are given equal weight, R is shown that mulUple-key hashmg often prowdes about the most efficient means of partmonmg a file for the purpose of answelrmg partial-match queries.