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

Abstract

A storage and retrieval system for storage and retrieval of records in a computer system. In a preferred embodiment, the storage system generates various hashing functions, hashes the keys of the records to identify storage locations, and stores the records in the identified storage locations. The retrieval system retrieves a record for a key by using the hashing functions to identify a storage location and retrieving the data from the identified storage location. The storage system logically organizes storage (e.g., memory) into levels. Each level is further organized into bins, and each bin contains a fixed number of slots. Each slot contains storage for storing one record. The storage system preferably stores about half the records at the first level, a quarter of the records at the second level, and so on. The storage system uses hashing functions and hashes the keys to determine at which level, bin, and slot to store the record associated with the key. The storage system uses a tentative bin assignment hashing function to tentatively assign keys to bins. The storage system then searches for a perfect hashing function for assigning a subset of the tentatively assigned keys to slots within the bin. The storage system generates a definite bin assignment hashing function to identify the subset. The storage system generates a definite bin assignment hashing function and a perfect hashing function for each bin within each level. The retrieval system uses the tentative bin assignment hashing function, the definite bin assignment hashing functions, and the perfect hashing functions to locate records.

I claim: 
     
       1. 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: 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 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.   
     
     
       2. The method of claim 1 wherein the keys are variable length and including the step of mapping the variable length keys to fixed length keys using a perfect hashing function. 
     
     
       3. The method of claim 2 wherein the fixed length key has a number of bits that is approximately equal to   2* log(number of keys)/log(2).     
     
     
       4. The method of claim 1 wherein the number of slots in a level is a power of two. 
     
     
       5. The method of claim 1 including the step of storing an indication of each perfect hashing function selected. 
     
     
       6. The method of claim 1 wherein each record contains one of two values and each level contains two slots, wherein the step of selecting a perfect hashing function for assigning the selected records to the selected slots includes the step of selecting a perfect hashing function such that all selected records of one value are assigned to one slot and all selected records of the other value are assigned to the other slot, and including the step of suppressing storing each selected record in an assigned slot. 
     
     
       7. The method of claim 1 including the step of selecting a perfect hashing function for assigning the selected records to the selected slots includes the step of selecting a non-perfect hashing function when records with the same data hash to the same slot. 
     
     
       8. The method of claim 1 wherein the records are variable length, and before repeating the steps logically dividing each record into fixed length sub-records and generating a sub-key for each key and repeating the steps using the sub-keys and sub-records. 
     
     
       9. The method of claim 1 wherein the step of selecting records to store in the slots of the level and a perfect hashing function further includes the steps of: logically dividing the level into bins, each bin having a plurality of slots;   assigning each of the selected records to a bin; and   for each bin, selecting a perfect hashing function for assigning the records assigned to the bin to slots within the bin.   
     
     
       10. The method of claim 1 wherein the step of selecting records to store in the slots of the level includes the step of searching for a selection function for selecting the records. 
     
     
       11. 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.     
     
     
       12. The method of claim 11 wherein the step of selecting records and a slot assignment function includes the steps of iteratively selecting various sets of records to store into the slots of the bin until a perfect hashing function for the selected set of records is found. 
     
     
       13. The method of claim 12 wherein the step of selecting various sets of records includes selecting a generally decreasing number of records to facilitate the selecting of a perfect hashing function. 
     
     
       14. The method of claim 11 including the step of for each bin of the level, tentatively assigning each record not yet stored in an assigned slot to a bin and wherein the step of selecting records to store in the slots of the bin selects records from the records tentatively assigned to the bin. 
     
     
       15. The method of claim 14 wherein the step of selecting records to store in the slots of the bin includes the step of searching for a selection function for selecting the records. 
     
     
       16. The method of claim 15 wherein the step of selecting records and a slot assignment function includes the steps of iteratively selecting various sets of records to store into the slots of the bin until a perfect hashing function for the selected set of records is found. 
     
     
       17. The method of claim 11 wherein the keys are variable length and including the step of mapping the variable length keys to fixed length keys using a perfect hashing function. 
     
     
       18. The method of claim 17 wherein the fixed length key has a number of bits that is approximately equal to   2* log(number of keys)/log(2).     
     
     
       19. The method of claim 11 wherein the number of bins in a level is a power of two and the number of slots in a bin is a power of two. 
     
     
       20. The method of claim 11 wherein each record contains one of two values and each bin contains two slots, wherein the step of selecting a slot assignment function for assigning the selected records to slots of the bin includes the step of selecting a perfect hashing function such that all selected records of one value are assigned to one slot and all selected records of the other value are assigned to the other slot, and including the step of suppressing storing the selected record in its assigned slot. 
     
     
       21. The method of claim 11 including the step of selecting a slot assignment function for assigning the selected records to the slots includes the step of selecting a non-perfect hashing function so that records with the same data hash to the same slot. 
     
     
       22. The method of claim 11 wherein the records are variable length, and before repeating the steps logically dividing each record into fixed length sub-records and generating a sub-key for each key and repeating the steps using the sub-keys and sub-records. 
     
     
       23. The method of claim 11 wherein the step of selecting records to store in the slots of the bin includes the step of searching for a selection function for selecting the records. 
     
     
       24. 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.     
     
     
       25. The method of claim 24 wherein the step of selecting a subset of keys includes the step of generating a bin assignment function for indicating the selected subset of the keys. 
     
     
       26. The method of claim 25 wherein each key has an associated record and including the step of storing the record associated with a key into the slot assigned to the key. 
     
     
       27. The method of claim 26 including the step of storing an indication of each bin assignment function and perfect hashing function so that the record for a key can be retrieved using the bin assignment functions and perfect hashing functions. 
     
     
       28. The method of claim 24 wherein each key has an associated record and wherein each record contains one of two values and each bin contains two slots, wherein the step of attempting to generate a perfect hashing function includes the step of selecting a perfect hashing function such that all the keys of the selected subset with records of one value are assigned to one slot and all the keys of the selected subset with records of the other value are assigned to the other slot, so that when retrieving records, the value of a record is the result of the selected perfect hashing function. 
     
     
       29. The method of claim 24 wherein each key has an associate record and including the step of attempting to generate a perfect hashing function includes the step of selecting a non-perfect hashing function when records with the same data hash to the same slot. 
     
     
       30. 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.   
     
     
       31. The computer system of claim 30 wherein the means for selecting a subset of the keys includes means for selecting a bin assignment function for indicating the selection. 
     
     
       32. A computer-readable medium encoded with a data structure containing a plurality of records, each record having a key, the data structure comprising: a slot table having plurality of levels, each level having a plurality of bins, each bin having a plurality of slots, each slot for containing a record;   a seed table, the seed table containing an indication of a bin assignment function and a slot assignment function for each bin in each level, the bin assignment functions for indicating which records are assigned to a bin, and the slot assignment function for assigning each record that is assigned to a bin to a slot within the bin.   
     
     
       33. The computer-readable medium of claim 32 wherein the data structure further includes a count of bins table having an entry for each level, each entry indicating the number of bins in the level. 
     
     
       34. The computer-readable medium of claim 32 wherein the indications of the bin assignment functions and the slot assignment functions are interleaved within the slot table. 
     
     
       35. 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.   
     
     
       36. The method of claim 35 wherein the step of selecting a slot assignment for a subset further includes the step of iteratively selecting a bin assignment function for selecting a subset of the tentatively assigned secure keys, and determining whether a potential slot assignment function is to be selected and storing an indication of the bin assignment function corresponding to the selected slot assignment function. 
     
     
       37. The method of claim 36 including the step of retrieving the record associated with a designated secure key by repeating the steps of: for each level until the record is retrieved, determining the bin within the level to which the designated secure key was tentatively assigned;   retrieving the indication of the bin assignment function;   using the indicated bin assignment function, determining whether the designated secure key was assigned to a slot within the determined bin; and   when the designated secure key was assigned to a slot within the determined bin, retrieving the indication of the slot assignment function;   using the indicated slot assignment function, determining to which slot the designated secure key was assigned; and   retrieving the stored record from the determined slot.       
     
     
       38. 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.     
     
     
       39. The method of claim 38 wherein the step of selecting prefixes and a slot assignment function includes the steps of iteratively selecting various sets of prefixes to assign to the slots of the level until a slot assignment function that is a perfect hashing function for the selected prefixes is found. 
     
     
       40. The method of claim 38 wherein each successor data structure is an array with an entry for each element in the alphabet. 
     
     
       41. The method of claim 40 including the step of encoding the successor data structures in a variable length code based on frequency and wherein the step of storing the generated successor data structure stores the encoding. 
     
     
       42. The method of claim 38 wherein the step of selecting prefixes to assign to the slots of the level and a slot assignment function further includes the steps of: logically dividing the level into bins, each bin having a plurality of slots;   assigning each of the selected prefixes to a bin; and   for each bin, selecting a slot assignment function for assigning the prefixes assigned to the bin to slots within the bin.   
     
     
       43. The method of claim 38 wherein the step of selecting prefixes to assign to the slots of the level includes the step of searching for a selection function for selecting the prefixes. 
     
     
       44. 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.       
     
     
       45. The method of claim 44 wherein the storage contains a count of bins indicating the number of bins in each level, and wherein the step of determining to which bin within the level the successor data structure for the designated prefix may be stored includes the step of using the count of bins to determine the number of bins in a level. 
     
     
       46. 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.       
     
     
       47. 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.   
     
     
       48. The computer-readable medium of claim 47 wherein the step of selecting records and a perfect hashing function includes the steps of iteratively selecting various sets of records to store into the slots of the level until a perfect hashing function for the selected set of records is found. 
     
     
       49. The computer-readable medium of claim 47 wherein the keys are variable length and including the step of mapping the variable length keys to fixed length keys using a perfect hashing function. 
     
     
       50. The computer-readable medium of claim 49 wherein the fixed length key has a number of bits that is approximately equal to   2* log(number of keys)/log(2).     
     
     
       51. The computer-readable medium of claim 47 wherein the number of slots in a level is a power of two. 
     
     
       52. The computer-readable medium of claim 47 including the step of storing an indication of each perfect hashing function selected. 
     
     
       53. The computer-readable medium of claim 47 wherein each record contains one of two values and each level contains two slots, wherein the step of selecting a perfect hashing function for assigning the selected records to the selected slots includes the step of selecting a perfect hashing function such that all selected records of one value are assigned to one slot and all selected records of the other value are assigned to the other slot, and including the step of suppressing storing each selected record in an assigned slot. 
     
     
       54. The computer-readable medium of claim 47 including the step of selecting a perfect hashing function for assigning the selected records to the selected slots includes the step of selecting a non-perfect hashing function when records with the same data hash to the same slot. 
     
     
       55. The computer-readable medium of claim 47 wherein the records are variable length, and before repeating the steps logically dividing each record into fixed length sub-records and generating a sub-key for each key and repeating the steps using the sub-keys and sub-records. 
     
     
       56. The computer-readable medium of claim 47 wherein the step of selecting records to store in the slots of the level and a perfect hashing function further includes the steps of: logically dividing the level into bins, each bin having a plurality of slots;   assigning each of the selected records to a bin; and   for each bin, selecting a perfect hashing function for assigning the records assigned to the bin to slots within the bin.   
     
     
       57. The computer-readable medium of claim 47 wherein the step of selecting records to store in the slots of the level includes the step of searching for a selection function for selecting the records. 
     
     
       58. 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.       
     
     
       59. The computer-readable medium of claim 58 wherein the step of selecting records and a slot assignment function includes the steps of iteratively selecting various sets of records to store into the slots of the bin until a perfect hashing function for the selected set of records is found. 
     
     
       60. The computer-readable medium of claim 58 including the step of for each bin of the level, tentatively assigning each record not yet stored in an assigned slot to a bin and wherein the step of selecting records to store in the slots of the bin selects records from the records tentatively assigned to the bin. 
     
     
       61. The computer-readable medium of claim 58 wherein the keys are variable length and including the step of mapping of the variable length keys to fixed length keys using a perfect hashing function. 
     
     
       62. The computer-readable medium of claim 58 wherein the number of bins in a level is a power of two and the number of slots in a bin is a power of two. 
     
     
       63. The computer-readable medium of claim 58 wherein each record contains one of two values and each bin contains two slots, wherein the step of selecting a slot assignment function for assigning the selected records to slots of the bin includes the step of selecting a perfect hashing function such that all selected records of one value are assigned to one slot and all selected records of the other value are assigned to the other slot, and including the step of suppressing storing the selected record in its assigned slot. 
     
     
       64. The computer-readable medium of claim 58 including the step of selecting a slot assignment function for assigning the selected records to the slots includes the step of selecting a non-perfect hashing function so that records with the same data hash to the same slot. 
     
     
       65. The computer-readable medium of claim 58 wherein the records are variable length, and before repeating the steps logically dividing each record into fixed length sub-records and generating a sub-key for each key and repeating the steps using the sub-keys and sub-records. 
     
     
       66. The computer-readable medium of claim 58 wherein the step of selecting records to store in the slots of the bin includes file step of searching for a selection function for selecting the records. 
     
     
       67. 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.     
     
     
       68. The computer-readable medium of claim 67 wherein the step of selecting a subset of keys includes the step of generating a bin assignment function for indicating the selected subset of the keys. 
     
     
       69. The computer-readable medium of claim 67 wherein each key has an associated record and including the step of storing the record associated with a key into the slot assigned to the key. 
     
     
       70. The computer-readable medium of claim 67 including the step of storing an indication of each bin assignment function and perfect hashing function so that the record for a key can be retrieved using the bin assignment functions and perfect hashing functions.