Order-Preserving Hashing Using Positional Character Transition Frequencies
Original Publication Date: 1987-May-01
Included in the Prior Art Database: 2005-Feb-01
This invention describes an order-preserving uniform hash function so that in addition to the usual benefits of hashing, i.e., direct access to records by key without searching, sequential access is also efficient. Given a collection of N records with keys, where N is large, in order to construct a hash function that efficiently maps these records into buckets stored on a direct access storage device (DASD), a function f must be found to map the keys onto some interval, say [0,1], in such a fashion that it is expected that the keys will be distributed uniformly. If there are b buckets B0B1,...,Bb-1, the hash function H can then be defined as H(K) = bf(K) , where K is a key. Due to the possible randomness of keys, it is usually not possible to use exactly N buckets with each bucket containing a single record.