US5857196A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for storing a tree of potential keys in a sparse table
Assignee: Nortel Networks Ltd
•
Filing: 1996-07-19
•
Granted: 1999-01-05
•
Expires: 2016-07-19
Abstract
Abstract A computer implemented method for searching for a key in a radix search tree in a memory of a computer system. A table of keys is organized in a radix search tree stored in a memory of a computer system. The keys are divided into a string of symbols. Each node in the tree corresponds to a symbol. A path from a root node to a leaf node at level n in the tree represents a string of n symbols comprising a key. Each node is capable of having m possible entries corresponding to m possible symbol values. Each entry comprises a pointer to a son node and an existence map indicating which entries exist in the son node. In the preferred embodiment, the existence map is a bit mask that indicates, based on bit positions enabled and disabled in the bit mask, which entries exist in the son node pointed to by the pointer. By providing an existence map along with the pointer to a son node, m memory locations for m entries are allocated for the son node only if all of the m possible entries are used. Memory locations for entries that would otherwise be empty are not allocated, thereby minimizing memory resources required by a radix search tree.
Inventors
- 👤 Richard L. Angle
- 👤 Edward S. Harriman, Jr.
- 👤 Geoffrey B. Ladwig
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 15:31
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/30; G06F16/31; G06F16/316; G06F16/322; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99937; Y10S707/99941; Y10S707/99943; Y10S707/99944; Y10S707/99945
Claims Analysis
Total Claims: 8
Claim 1
Independent Claim
203 words
A computer implemented method for searching for a key in a table, where the sparse table of potential keys is organized as a tree in a memory of a computer system, comprising: a) receiving a key; b) dividing the key into a string of n symbols; c) searching the tree for the string of n symbols, comprising: i) comparing a first symbol in the string of n symbols with an existence map associated with a root node in the tree; ii) traversing the tree to a son node in the tree pointed to by an entry in the root node corresponding to the first symbol if the existence map associated with the root node indicates the entry exists; iii) comparing a next symbol in the string of n symbols with an existence map associated with the son node in the tree; iv) traversing the tree to a subsequent son node in the tree pointed to by an entry in the son node corresponding to the next symbol if the existence map associated with the son node indicates the entry exists; v) repeating steps iii and iv until the comparison fails or the next symbol is the last symbol in the string of symbols.
Claim 2
Dependent Claim
203 words
A computer implemented method for searching for a key in a table, where the sparse table of potential keys is organized as a tree in a memory of a computer system, comprising: a) receiving a key; b) dividing the key into a string of n symbols; c) searching the tree for the string of n symbols, comprising: i) comparing a first symbol in the string of n symbols with an existence map associated with a root node in the tree; ii) traversing the tree to a son node in the tree pointed to by an entry in the root node corresponding to the first symbol if the existence map associated with the root node indicates the entry exists; iii) comparing a next symbol in the string of n symbols with an existence map associated with the son node in the tree; iv) traversing the tree to a subsequent son node in the tree pointed to by an entry in the son node corresponding to the next symbol if the existence map associated with the son node indicates the entry exists; v) repeating steps iii and iv until the comparison fails or the next symbol is the last symbol in the string of symbols.
Claim 3
Dependent Claim
33 words
The method of claim 1, wherein dividing the key into a string of n symbols includes dividing the key into a string of n hexadecimal digits, where each hexadecimal digit represents a symbol.
Claim 4
Dependent Claim
48 words
The method of claim 1 wherein comparing a first symbol in the string of n symbols with an existence map associated with a root node in the tree includes comparing a first symbol in the string of n symbols with a bit mask associated with the root node.
Claim 5
Dependent Claim
87 words
The method of claim 3 wherein traversing the tree to a son node in the tree pointed to by an entry in the root node corresponding to the first symbol if the existence map associated with the root node indicates the entry exists includes traversing the tree to a son node in the tree pointed to by an entry in the root node corresponding to the first symbol if a bit position corresponding to the first symbol is enabled in the bit mask indicating the entry exists.
Claim 6
Dependent Claim
48 words
The method of claim 1 wherein comparing a next symbol in the string of n symbols with an existence map associated with the son node in the tree includes comparing the next symbol in the string of n symbols with a bit mask associated with the son node.
Claim 7
Dependent Claim
94 words
The method of claim 5 wherein traversing the tree to a subsequent son node in the tree pointed to by an entry in the son node corresponding to the next symbol if the existence map associated with the son node indicates the entry exists includes traversing the tree to a subsequent son node in the tree pointed to by an entry in the son node corresponding to the next symbol if a bit position corresponding to the next symbol is enabled in the bit mask associated with the son node indicating the entry exists.
Claim 8
Dependent Claim
80 words
The method of claim 6 wherein repeating steps iii and iv until the comparison fails or the next symbol is the last symbol in the string of symbols comprises: traversing the tree to a subsequent son node in the tree pointed to by an entry in the son node corresponding to the next symbol until a bit position corresponding to the next symbol is disabled in the bit mask associated with the son node indicating the entry does not exist.
References Cited (Backward Citations)
US4468728A
Cited
US4774657A
Cited
US5333317A
Cited
US5261088A
Cited
US5396622A
Cited
US5490269A
Cited
US5440734A
Cited
US5487164A
Cited
US5557786A
Cited
US5546390A
Cited
US5651099A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-01-04 | 2002-07-06 | 2003-01-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-01-04 | 2006-07-06 | 2007-01-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-01-04 | 2010-07-06 | 2011-01-05 | $7700.00 | Window Closed / Lapsed |