Optimal information retrieval when queries are not random (Q1061507)

Given query probabilities attached to attributes, a general formula for the average number of buckets to be accessed using the multiple key hashing (MKH) scheme is derived. It is shown that the problem of arranging multiattribute records optimally in a fixed number of buckets is NP-hard and that the optimal integer solution for hashing function ranges can be reduced to finding minimal N-tuples. Based on the general formula, a good and efficient heuristic algorithm for MKH design is proposed and simulation results are presented.