Electrical computers and digital processing systems: memory – Address formation – Hashing
Reexamination Certificate
1998-02-11
2001-01-09
Chan, Eddie P. (Department: 2751)
Electrical computers and digital processing systems: memory
Address formation
Hashing
C711S202000, C711S217000, C711S200000, C711S221000, C711S220000, C707S793000, C370S389000, C370S392000, C370S902000, C370S229000
Reexamination Certificate
active
06173384
ABSTRACT:
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
Not applicable.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention is related to the field of data structures stored in a memory of a computer system. More specifically, the present invention is related to a method for obtaining a seed value to be used as input to a hashing algorithm, the hashing algorithm providing a key for efficiently and quickly accessing records of a table in a memory of a computer system.
2. Description of the Related Art
There are numerous well known methods for searching for data in a data structure stored in a memory of a computer system to find a particular item of information. Certainly, it is appropriate to implement methods for organizing and searching for data in the data structure in a way that reduces the amount of memory required to store the data and perform the search in a more efficient manner. Before discussing such methods and the present invention, a brief mention of terms commonly used in the description of data structures and search techniques performed thereon is in order.
A table, or a file, comprises a group of data elements, each of which may be called an entry, or a record, in the table. Generally, an index value is associated with each record. The index value is used to identify the different records. The index value associated with a particular record may or may not need to be unique, depending on the search method utilized in accessing the table. Furthermore, the index value may be embedded within the record itself, or otherwise associated with the record.
A search method accepts one or more keys as input and attempts to locate a record within a table stored in the memory of a computer system whose associated index value matches the key. The search method may return the contents of the record, or a pointer to the record. The contents of the record may be data, program code, or a pointer to either data or program code, for example. If the search of a table is unsuccessful in finding the index value, then there is no record in the table associated with the index value. Typically, if the search is unsuccessful, a new record is added to the table with the key as its index value.
A table is stored in a data structure in the memory or an external storage, e.g., magnetic disk, of a computer system. The form of the data structure may be an array of records, a tree, a linked list, etc. Certain search methods are generally more applicable to one form and location of a data structure than another. Thus, the type and location of the data structure in which a table is stored is compatible with the search method used to access information within the table. For example, the present invention is related to search operations on a file or table that is organized as an array or group of arrays in a memory of an information handling device.
The efficiency and speed with which an algorithm searches for and identifies a record in a table is, understandably, a very important consideration in many fields of data computing. In particular, often utilized lookup routines benefit from and commonly rely on sophisticated techniques and schemes for accessing information in a data structure, particularly when accessing large databases of information. For example, optimized lookup routines are used in data communication networks to identify data packets, identify the destination for such data packets, and determine whether a data packet forwarding device should receive, forward, or filter such data packets. As data communication networks become larger and handle greater amounts of data traffic, the ability of data packet forwarding devices such as a bridge, switch, or router, or the like, to quickly identify addresses in data packets for purposes of determining whether and where to forward such data packets is paramount. To that end, what is needed is an improved method for searching for a record in a table, for example, searching for an entry in a forwarding database, indexed by a destination address, that indicates the port of a data packet forwarding device out of which data packets having the destination address should be forwarded by the data packet forwarding device. In particular, what is needed is a hashing algorithm in which the seed values input to the hashing algorithm are selected to achieve the best results in terms of reducing collisions and/or rehashing to find the desired record.
BRIEF SUMMARY OF THE INVENTION
The present invention relates to a computer implemented method for providing a seed value to be used as input to a hashing algorithm, which provides a key as output. The key generated by the hashing algorithm is utilized in searching for a record in a table in a memory of a computer system. The table of records is organized into an array in the memory. The table, or data of the kind stored in the table, is analyzed to determine and measure the information content of each bit in a string of bits comprising an index value associated with the records in the table, according to the well-known formula for determining information-theoretic entropy developed by Claude Shannon. The measurement of the amount of information content, or entropy, associated with each bit in the string of bits provides a basis for choosing a subset of the bits in the string of bits comprising the index value from which to obtain the seed values utilized in the hashing function. A rotating mask is iteratively applied to the subset of bits to obtain a number of different seed values for use in multiple iterations of the hashing function. The hashing function receives the seed values and produces a like number of alternate keys for use in searching the table, wherein if a collision occurs in a search utilizing a key, a different key is selected and the search performed again. The mask is selected and rotated to minimize the correlation of the keys provided by the hashing function. The well-known Neumann's code provides the basis for selecting and rotating the mask utilized in obtaining the seed values, such that the seed values are generally unique with respect to each other. Each of the subset of bits selected as a seed value are then compressed, providing a compressed, selected subset of bits such that the calculation of the key by the hashing function is simplified, thereby saving hardware or software resources otherwise required, depending on the implementation of the method.
Optionally, in the event the compressed, selected subset of bits representing a particular seed value are the same or similar to the compressed, selected subset of bits representing another seed value, one or both of the subset of bits may be folded, and the result(s) provided as the seed value(s) to the hashing function. By folding a compressed, selected subset of bits representing a particular seed value, the present invention ensures that different seed values input on different iterations of the hashing function are sufficiently unique to produce sufficiently unique keys for use in searching for a record in the table. In the event a collision occurs on a first search of the table utilizing a first key provided by a first iteration of the hashing function, a subsequent search of the table may be made with a second key provided by a second iteration of the hashing function, and so on. If a key matches the index value of a particular record, then the record being searched for has been found. If a match does not occur using a given key, i.e., if a collision occurs, the next key is compared against the index values of the records in the table to find a match, and so on, until a match is located or no further keys are provided by the hashing function. Optimally, the seed values, keys, and/or searches can be pipelined to reduce the time to locate a record in the table in the event a collision occurs on a search of the table.
REFERENCES:
patent: 5414704 (1995-05-01), Spinney
patent: 5490258 (1996-02-01), Fenner
patent: 5546390 (1996-08-01), Stone
patent: 5613110 (1997-03-01), Stuart
patent: 5692177 (1997
Blakely , Sokoloff, Taylor & Zafman LLP
Chan Eddie P.
McLean Kimberly
Nortel Networks Limited
LandOfFree
Method of searching for a data element in a data structure does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of searching for a data element in a data structure, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of searching for a data element in a data structure will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2556237