Optimal Retrieval Algorithms for Small Region Queries
Azad Bolour · SIAM Journal on Computing · 1981
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.