Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-07-01
2001-06-12
Black, Thomas (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06247014
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to data communications networks, and more particularly, to a method and apparatus for performing hash lookups using valid bit tables with pointers.
BACKGROUND OF THE INVENTION
There are numerous 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. It is desirable 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.
A table or a file is a group of data elements, each of which may be called an entry or a record in the table. Generally, a key is associated with each record. The key is used to differentiate among different records. The key associated with a particular record may or may not need to be unique, depending on the search method utilized in accessing the table. In addition, the key may or may not be embedded within the record itself.
A search method accepts a key value as input and attempts to locate a record within a table stored in the memory of a computer system whose associated key is the key value. The search method may return a 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. If the search of a table is unsuccessful in finding the key, then there is no record in the table associated with the key value. Typically, if the search is unsuccessful, an insertion is performed to add a new record with the key value as its key.
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 data structure in which a table is stored is, in part, selected according to the search method to be used to access information within the table. The present invention is related to search operations on a file or table that is organized as a tree structure.
One known search method utilizes a tree to facilitate searching a table stored in the memory of a computer system. This search method forms a tree based on symbols of which the keys are comprised. This is generally referred to as a radix search tree. For example, if the key is comprised of the hexadecimal characters 0 through F, each successive hexadecimal digit position in the key determines 1 of 16 possible children of a given node in the tree.
When the set of keys in a table is sparse, known methods of storing a table of keys in a tree for later radix searching wastes a large amount of memory space. Therefore, there is a need for a way of storing information in a tree structure in the memory of a computer system and for subsequently searching the tree such that the amount of memory required to store a sparse table of keys is minimized. There is a further need for searching a tree in the memory of a computer system in a fast, efficient manner.
SUMMARY OF THE INVENTION
The present invention provides a method, apparatus, and article of manufacture for hash lookups using valid bit tables with pointers. A key is compressed by hashing the key using a hash function. The hash key is used as a valid bit index into the valid bit table. A first pointer associated with the valid bit index is then used as a pointer into a first block of entries in a result table. A sum of transition bits in the valid bit table below the valid bit index is used as a result index into the first block of entries in the result table. The result index into the first block of entries may be used to reference a result of the radix search tree lookup. Extra space is added in the result table to enable insertion of entries after the first block of entries. A second pointer is used to add redundant entries from the first block of entries into a second block of entries in the result table.
REFERENCES:
patent: 5355473 (1994-10-01), Au
patent: 5546390 (1996-08-01), Stone
patent: 5651099 (1997-07-01), Konsella
patent: 5829004 (1998-10-01), Au
patent: 5857196 (1999-01-01), Angle et al.
patent: 5873078 (1999-02-01), Angle et al.
Knox et al., Parallel Searching Techniques for Routing Table Lookup, IEEE, pp. 1400-1405, Apr. 1993.*
Wang et al., Searching Algorithm of the Optimal Radix of exponential Bidirectional Associative Memory, IEEE, pp. 1137-1142, Jun. 1994.*
Reznick, LZRW1 Without Hashing, IEEE, p. 569, Mar. 1998.*
Wang et al., Analysis of Radix Searching of Exponential Bidirectional Associative Memory, IEEE, pp. 279-285, Jul. 1998.*
Robert Sedgewick, Algorithms (Radix Searching), Addison-Wesley Publishing Company, pp. 213-223 201-210, 1983.
Angle Richard
Ladwig Geoff
Black Thomas
Blakely , Sokoloff, Taylor & Zafman LLP
Coby Frantz
Nortel Networks Limited
LandOfFree
Method and apparatus for performing hash lookups using valid... 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 and apparatus for performing hash lookups using valid..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for performing hash lookups using valid... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2476864