Patent ID: 6173384
Filing Date: 2001-01-09
Classification: G06F,Y10S

Abstract:
In an information handling device having a table of data elements, a method for searching for a received data element in the table of data elements:a) selecting a like portion of each data element as an index value for differentiating between the data elements in the table, the portion comprising a contiguous string of bits located at like bit positions in each data element in the table such that the same bit positions from each data element form a logical column in the table;b) measuring the information content for each logical column;c) ranking each logical column according to the amount of information content associated with each logical column;d) selecting a set of logical columns in the portion having a rank at or above a desired rank;e) receiving a data element at the information handling device;f) identifying a set of bit positions in a portion of the received data element corresponding to the selected set of columns;g) applying a mask to the set of bit positions in the portion of the received data element to create a reduced set of bit positions in the portion of the received data element;h) providing the content of each bit position in the reduced set of bit positions in the portion of the received data element as one of a plurality of keys to be input to a hashing function, the hashing function providing the index value for a data element to be searched for in the table corresponding to the received data element; andi) rotating the mask;j) repeating steps g) through i) according to the plurality of keys desired, the mask being rotated in such a manner as to minimize correlation among the plurality of keys;k) performing hashing functions to obtain a plurality of index values, each hashing function utilizing a unique one of the plurality of keys;l) searching the table for the index value to locate the received data element.