Method of searching for a data element in a data structure

• US 6,173,384 B1
• Filed: 02/11/1998
• Issued: 01/09/2001
• Est. Priority Date: 02/11/1998
• Status: Expired due to Fees

• Current Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Weaver, Jeff
• Primary Examiner(s): Chan, Eddie P.
• Assistant Examiner(s): MCLEAN MAYO, KIMBERLY N
• Application Number:
  US09/021,970
• Time in Patent Office: 1,063 Days
• Field of Search: 711/216, 711/202, 711/217, 711/221, 711/220, 711/200, 370/389, 370/392, 370/60, 370/229, 707/2
• US Class Current: 711/216
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

Abstract

A method for searching for a record in a table in a memory of a computer system. A table of records is organized into a group of arrays. A hashing algorithm locates a record in the table. Multiple hashing functions are executed concurrently, according to the number of arrays in the group, such that the record can be located relatively quickly in one of the arrays in the group. The table is analyzed to determine the information content of each bit in a string of bits comprising an index value associated with the table, according to Shannon'"'"'s formula for information-theoretic entropy. The entropy associated with each bit in the string of bits provides a basis for selecting a subset of bits in the string of bits from which to obtain the seed values utilized in the hashing functions. A rotating mask, based on Neumann'"'"'s code, is applied to the subset of bits to obtain different seed values for each of the hashing functions, thereby minimizing the correlation of the keys provided by the hashing functions.

Claims

1. 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; and

i) 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.

2. The method of claim 1, wherein 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 includes applying a mask based on Neumann'"'"'s code 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.

12. The method of claim 1, wherein measuring the information content for each logical column comprises measuring the entropic value of each logical column.

13. The method of claim 12, wherein measuring the entropic value of each logical column comprises measuring the entropic value of each logical column in accordance with an information-theoretic entropy algorithm.

14. The method of claim 13, wherein measuring the entropic value of each logical column in accordance with an information-theoretic entropy algorithm comprises measuring the entropic value of each logical column in accordance with a well known information-theoretic entropy algorithm.

15. The method of claim 14, wherein measuring the entropic value of each logical column in accordance with a well known information-theoretic entropy algorithm comprises measuring the entropic value of each logical column in accordance with Claude Shannon'"'"'s information-theoretic entropy algorithm.

3. A method for providing a seed value for input to a hashing function, the hashing function providing a key for searching for a data element in a table of data elements, comprising:

a. identifying a subset of bit positions in an index field associated with each of the data elements in the table;

b. receiving a data element for which to search in the table of data elements;

c. selecting a subset of bits in the received data element corresponding to the identified subset of bit positions in the index field;

d. applying a mask to reduce the selected subset of bits in the received data element; and

e. providing the reduced subset of bits from the received data element as the seed value input to the hashing function.

4. The method of claim 3, wherein applying a mask to reduce the selected subset of bits in the received data element comprises applying a mask based on Neumann'"'"'s code to reduce the selected subset of bits in the received data element.

5. The method of claim 4, further comprising compressing the reduced subset of bits obtained from applying a mask to reduce the selected subset of bit positions in the received data element.

6. The method of claim 5, wherein providing the reduced subset of bits from the received data element as the seed value input to the hashing function comprises providing the compressed, reduced subset of bits from the received data element as the seed value input to the hashing function.

7. The method of claim 5, further comprising folding the compressed, reduced subset of bits from the received data element.

8. The method of claim 7, wherein providing the reduced subset of bits from the received data element as the seed value input to the hashing function comprises providing the folded, compressed, reduced subset of bits from the received data element as the seed value input to the hashing function.

16. The method of claim 3, wherein identifying a subset of bit positions in an index field associated with each of the data elements in the table comprises identifying a subset of bit positions in an index field associated with each of the data elements in the table, wherein the value for each bit position in the identified subset of bit positions varies more among the data elements than the value for each bit position in the bit positions in the index field not identified.

17. The method of claim 16, wherein identifying a subset of bit positions in an index field associated with each of the data elements in the table, wherein the value for each bit position in the identified subset of bit positions varies more among the data elements than the value for each bit position in the bit positions in the index field not identified, comprises:

a) measuring the information content of each of the bit positions in the index field; and

b) ranking the bit positions in the index field based on the measure of information content of each of the bit positions in the index field; and

b) identifying a subset of bit positions in the index field having a higher relative measure of information content.

18. The method of claim 17, wherein measuring the information content of each of the bit positions in the index field comprises measuring the entropic value of each of the bit positions in the index field.

19. The method of claim 18, wherein measuring the entropic value of each of the bit positions in the index field comprises measuring the entropic value of each of the bit positions in the index field in accordance with an information-theoretic entropy algorithm.

20. The method of claim 19, wherein measuring the entropic value of each of the bit positions in the index field in accordance with an information-theoretic entropy algorithm comprises measuring the entropic value of each of the bit positions in the index field in accordance with Claude Shannon'"'"'s information-theoretic entropy algorithm.

9. A method for providing a seed value for input to a hashing function, the hashing function providing a key for searching for a data element in a table of data elements, comprising:

a. identifying a subset of bit positions in an index value associated with each of the data elements in the table;

b. receiving a data element for which to search in the table of data elements;

c. selecting a subset of bits in that portion of the received data element corresponding to the identified subset of bit positions in the index value; and

d. repeating, to provide as many seed values as desired for input to a like number of iterations of the hashing function;

i. applying a mask to reduce the subset of bits in the received data element corresponding to the identified subset of bit positions in the index value;

ii. providing the reduced subset of bits from the received data element as the seed value input to the hashing function; and

ii. rotating the mask.

10. The method of claim 9, wherein rotating the mask comprises rotating the mask according to Neumann'"'"'s code to provide differentiation between the seed values.

11. The method of claim 10, further comprising performing the hashing function to provide a key for each iteration of d.

21. The method of claim 9, wherein identifying a subset of bit positions in an index value associated with each of the data elements in the table comprises identifying a subset of bit positions in an index value associated with each of the data elements in the table that have a higher relative information content than the bit positions in the index value not so identified.

22. The method of claim 21, wherein identifying a subset of bit positions in an index value associated with each of the data elements in the table that have a higher relative information content than the bit positions in the index value not so identified comprises identifying a subset of bit positions in an index value associated with each of the data elements in the table that have a higher entropic value than the bit positions in the index value not so identified.

23. In an information handling device having a table of data elements, a means for searching for a received data element in the table of data elements, comprising:

means for selecting a portion of each data element as an index value for differentiating between the data elements in the table, the portion comprising a string of bits located at bit positions in each data element in the table such that the bit positions from each data element form a logical column in the table;

means for measuring the information content for each logical column;

means for ranking each logical column according to the information content associated with each logical column;

means for selecting a set of logical columns in the portion based on their ranking;

means for receiving a data element at the information handling device;

means for identifying a set of bit positions in a portion of the received data element corresponding to the selected set of columns;

means for 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;

means for 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; and

means for performing the hashing function to obtain an index value utilizing the one of the plurality of keys;

means for searching the table for the index value to locate the received data element.

24. An article of manufacture comprising a machine readable medium having a plurality of machine readable instructions stored thereon, wherein the instructions, when executed by a processor, cause the processor to:

identify a subset of bit positions in an index field associated with each of the data elements in the table;

receive a data element for which to search in the table of data elements;

select a subset of bits in the received data element corresponding to the identified subset of bit positions in the index field;

apply a mask to reduce the selected subset of bits in the received data element; and

provide the reduced subset of bits from the received data element as the seed value input to the hashing function.

25. The article of manufacture of claim 24, wherein the instructions that cause the processor to identify a subset of bit positions in an index field associated with each of the data elements in the table comprises instructions that cause the processor to identify a subset of bit positions in an index field associated with each of the data elements in the table, wherein the value for each bit position in the identified subset of bit positions varies more among the data elements than the value for each bit position in the bit positions in the index field not identified.