The paper first shows that the bucket allocation problem of an MKH (multiple key hashing) file for partial match retrieval can be reduced to that of a smaller sized subfile, called the remainder of the file. And it is pointed out that the remainder type MKH file is the hardest MKH file for which to design an optimal allocation scheme. The authors then particularly concentrate on the allocation of an important remainder type MKH file; namely, the k-ary MKH file. They present various sufficient conditions on the number of available disks and the number of attributes for a k-ary MKH file to have a perfectly optimal allocation among the disks for partial match queries. Based upon these perfectly optimal allocations, they further present a heuristic method, called the CH (cyclic hashing) method, to produce near optimal allocations for the general k-ary MKH files. Finally, a comparison, by experiment, between the performances of the proposed method and an "ideal" perfectly optimal method, shows that the CH method is indeed satisfactorily good for the general k-ary MKH files.

Multiple key hashing files have been shown to exhibit attractive properties for partial match retrieval. The Disc Modulo (DM) allocation method has recently been shown to facilitate partial match retrieval for multiple key hashing files on multiple discs. In this paper, it is shown that the DM allocation method is optimal for k-ary multiple key hashing files under the condition that k ≡ (0 or 1 or m−1) (modm) where m is the number of available discs.