Method and system for data set storage by iteratively searching for perfect hashing functions

A method in a computer system for storing data in storage of the computer system, the data organized into records, each record having a key, the storage organized into slots, each slot for storing a record, the method comprising the computer-implemented steps of:

• repeating the following steps until each record is stored in a slot,
• selecting a number of slots and designating the selected slots as a level, the slots within a level being organized into bins;
• and
• for each bin of the level,
• iteratively selecting records to store in the slots of the bin and searching for a slot assignment function for assigning the selected records to the slots of the bin based on the keys;
• assigning the selected records to the slots of the bin in accordance with the selected slot assignment function;
• storing the selected record in its assigned slot;
• and
• storing an indication of the selected slot assignment function.

A method in a computer system for assigning a plurality of keys to slots in storage of the computer system, the method comprising repeating the following computer-implemented steps until each key is assigned to a slot:

• selecting a number of bins, each bin having a plurality of slots;
• tentatively assigning each of the keys not yet assigned to a slot to one of the selected bins;
• and
• for each of the selected bins,
• selecting a subset of the keys tentatively assigned to the selected bin;
• attempting to generate a perfect hashing function for assigning the selected subset of keys to slots of the selected bin;
• repeating the steps of selecting a subset and attempting to generate a perfect hashing function until a perfect hashing function is generated for a selected subset of the keys;
• and
• assigning the subset of keys to slots of the selected bin in accordance with the generated perfect hashing function.

A computer system for storing records in storage, each record having a key, the storage having slots, each slot for containing a record, the slots being organized into bins, the bins being organized into levels, the computer system comprising:

• means for selecting a next level when all the keys have not yet been assigned to a slot;
• means for tentatively assigning each key not yet assign to a slot to a bin within the selected level;
• means for selecting a subset of the keys tentatively assigned to a bin;
• means for selecting a hashing function for the bin;
• means for determining whether the selected hashing function is a perfect hashing function for assignment of the selected subset of the keys to slots within the bin;
• and
• means for storing the records associated with the selected subset of the keys into the slots of the bin in accordance with the determined perfect hashing function.

A method in a computer system for encrypting associations between secure keys and associated records, the method comprising the steps of:

• tentatively assigning each secure key not yet assigned to a slot to one of a plurality of bins within a level, each bin having a plurality of slots for storing records;
• for each bin within the level, selecting a slot assignment function for assigning a subset of the tentatively assigned secure keys to slots within the bin, assigning each secure key of the subset to a slot within the bin, storing within each assigned slot the associated record, and storing an indication of the selected slot assignment function;
• and
• repeating the above steps for subsequent levels until each secure key is assigned to a slot.

A method in a computer system for storing prefixes for words in a dictionary into storage of the computer system, the words having elements of an alphabet, the method comprising the steps of:

• generating successor data structure corresponding to each prefix of a word in the dictionary, each successor data structure indicating the elements of the alphabet such that the corresponding prefix combined with each of the indicated elements are also a prefix of a word in the dictionary;
• and
• repeating the following steps until all the generated successor data structures are stored in storage,
• selecting a number of slots in storage and designating the selected slots as a level;
• selecting prefixes to assign to slots of the level and a slot assignment function for assigning the selected prefixes to slots with the level;
• and
• storing the generated successor data structure associated with a prefix into the slot assigned by the slot assignment function.

A method in a computer system for determining whether an element is a successor element of a designated prefix of a word in a dictionary, the computer system having storage containing a successor data structure for each prefix of a word in the dictionary, the storage being organized into levels, each level having bins, each bin having a slot for containing a successor data structure, the storage having indications of a bin assignment function and a slot assignment function for each bin within each level, the successor data structures being stored in slots in accordance with the indicated bin assignment and slot assignment functions, the method comprising the steps of:

• repeating the following steps for each level until the successor data structure of the designated prefix is retrieved from storage,
• determining to which bin within the level the successor data structure for the designated prefix may be stored;
• retrieving the indication of the bin assignment function for the determined bin;
• performing the bin assignment function as indicated to determine whether the successor data structure for the designated prefix is stored within the determined bin;
• and
• when the bin assignment function indicates that the successor data structure for the designated prefix is stored in the determined bin,
• retrieving the indication of the slot assignment function for the determined bin;
• performing the slot assignment function as indicated to determine the slot in which the successor data structure is stored;
• and
• retrieving the successor data structure from the determined slot.

A method in a computer system for retrieving a record from a data structure stored in storage, each record having a key, the storage being organized into levels, each level having bins, each bin having slots, each slot for containing a record, the storage having indications of a bin assignment function and a slot assignment function for each bin within each level, the records being assigned to slots in accordance with the indicated bin assignment and slot assignment functions, the bin assignment functions and slot assignment function assigning slots based on the keys, the method comprising the steps of:

• receiving the key for the record to be retrieved;
• and
• repeating the following steps for each level until the record is retrieved from storage,
• determining to which bin within the level the record for the received key may be stored;
• retrieving the indication of the bin assignment function for the determined bin;
• performing bin assignment function as indicated to determine whether the record to be retrieved is stored in the bin;
• and
• when the bin assignment function indicates that the record to be retrieved is stored in the determined bin,
• retrieving the indication of the slot assignment function for the determined bin;
• performing the slot assignment function as indicated to determine the slot in which the record to be retrieved is stored;
• and
• retrieving the record from the determined slot.

A computer-readable medium containing computer instructions for causing a computer system to store data in storage of the computer system, the data organized into records, each record having a key, the storage organized into slots, each slot for storing a record, by the steps of:

• selecting a number of slots and designating the selected slots as a level;
• iteratively selecting from among the records not yet assigned to slots different sets of records to store into the selected slots of the level and searching for a perfect hashing function for assigning the selected records to the slots of the level based on the keys of the selected records until a perfect hashing function is found and selected;
• assigning the selected records to the selected slots in accordance with the selected perfect hashing function;
• storing each selected record in its assigned slot;
• and
• repeating the above steps for records not yet assigned to a slot until all the records are assigned to a slot.

A computer-readable medium containing computer instructions for causing a computer system to store dam in storage of the computer system, the data organized into records, each record having a key, the storage organized into slots, each slot for storing a record, by the steps of:

• repeating the following steps until each record is stored in a slot,
• selecting a number of slots and designating the selected slots as a level, the slots within a level being organized into bins;
• and
• for each bin of the level,
• iteratively selecting records to store in the slots of the bin and searching for a slot assignment function for assigning the selected records to the slots of the bin based on the keys;
• assigning the selected records to the slots of the bin in accordance with the selected slot assignment function;
• storing the selected record in its assigned slot;
• and
• storing an indication of the selected slot assignment function.

A computer-readable medium containing computer instructions for causing a computer system to assign a plurality of keys to slots in storage of the computer system by repeating the following steps until each key is assigned to a slot:

• selecting a number of bins, each bin having a plurality of slots;
• tentatively assigning each of the keys not yet assigned to a slot to one of the selected bins;
• and
• for each of the selected bins,
• selecting a subset of the keys tentatively assigned to the selected bin;
• attempting to generate a perfect hashing function for assigning the selected subset of keys to slots of the selected bin;
• repeating the steps of selecting a subset and attempting to generate a perfect hashing function until a perfect hashing function is generated for a selected subset of the keys;
• and
• assigning the subset of keys to slots of the selected bin in accordance with the generated perfect hashing function.