Dynamic File Structure for Partial Match Retrieval Based on Overflow Bucket Sharing

This paper introduces a hashing-based dynamic file structure for partial match retrieval using overflow bucket sharing. The sharing of overflow buckets is dynamic in the sense than an overflow bucket is shared by a varying number of primary buckets according to the local conditions of the file. Compared to previously published results, this file organization is space efficient and is time efficient for queries in which the number of specified attributes are small. These are exactly the types of queries which require substantial amount of retrieval times.