US6061679A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Creating and searching a data structure ordered by ranges of key masks associated with the data structure
Assignee: International Business Machines Corp
•
Filing: 1997-11-25
•
Granted: 2000-05-09
•
Expires: 2017-11-25
Abstract
Abstract A data structure, which includes a plurality of sub-data structures, is created. The sub-data structures are ordered based on ranges of key masks associated with the sub-data structures. In particular, in one example, the sub-data structures are linked in a list in ascending order of key mask ranges, thus, creating an ordered list of sub-data structures. The ordered data structure can be modified by adding new nodes to existing sub-data structures or by adding new sub-data structures. Further, nodes or sub-data structures can be removed from the ordered data structure. The data structure can also be searched in order to collect target records associated with requested keys of the data structure.
Inventors
- 👤 Redha M. Bournas
- 👤 Valery I. Garger
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 11:34
CPC Classifications
H; H04; H04L; H04L45/00; G; G06; G06F; G06F16/00; G06F16/90; G06F16/901; G06F16/9024; H04L45/54; H04L45/74; H04L45/745; H04L45/74591; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99937; Y10S707/99941; Y10S707/99942
Claims Analysis
Total Claims: 101
Claim 1
Independent Claim
51 words
A method of creating a data structure in a computing environment, said method comprising: obtaining a plurality of sub-data structures; and ordering said plurality of sub-data structures based on ranges of key masks associated with said plurality of sub-data structures, wherein said data structure comprises said ordered plurality of sub-data structures.
Claim 2
Independent Claim
51 words
A method of creating a data structure in a computing environment, said method comprising: obtaining a plurality of sub-data structures; and ordering said plurality of sub-data structures based on ranges of key masks associated with said plurality of sub-data structures, wherein said data structure comprises said ordered plurality of sub-data structures.
Claim 3
Dependent Claim
26 words
The method of claim 1, wherein said ordering comprises ordering said plurality of sub-data structures based on an ascending order of said ranges of key masks.
Claim 4
Dependent Claim
28 words
The method of claim 2, wherein said ordering comprises linking said plurality of sub-data structures in a linked list in ascending order of said ranges of key masks.
Claim 5
Dependent Claim
53 words
The method of claim 1, wherein a sub-data structure of said plurality of sub-data structures represents at least one group of one or more keys, and wherein any group associated with said sub-data structure has the same range of key mask as any other group that may be associated with said sub-data structure.
Claim 6
Dependent Claim
20 words
The method of claim 1, further comprising determining said ranges of key masks associated with said plurality of sub-data structures.
Claim 7
Dependent Claim
50 words
The method of claim 5, wherein said determining comprises for a key mask associated with a sub-data structure: converting said key mask into a binary notation; and counting a number of zeros within said binary notation, said number of zeros providing an indication of the range of said key mask.
Claim 8
Dependent Claim
22 words
The method of claim 6, wherein said range of said key mask is two to the power of said number of zeros.
Claim 9
Dependent Claim
16 words
The method of claim 1, wherein said plurality of sub-data structures comprises a plurality of trees.
Claim 10
Dependent Claim
16 words
The method of claim 8, wherein said plurality of trees comprises a plurality of PATRICIA trees.
Claim 11
Dependent Claim
34 words
The method of claim 1, further comprising adding another sub-data structure to said data structure, wherein said another sub-data structure is inserted in order in said data structure based on its key mask range.
Claim 12
Dependent Claim
15 words
The method of claim 1, further comprising inserting a new key into said data structure.
Claim 13
Dependent Claim
88 words
The method of claim 11, wherein said inserting comprises: determining a key mask range for said new key; creating a new sub-data structure when said key mask range is not within said data structure; adding a key mask associated with said new key to an existing sub-data structure when said key mask range is within said data structure and said key mask is not among the key masks of said existing sub-data structure; and adding said new key to said new sub-data structure or said existing sub-data structure.
Claim 14
Dependent Claim
15 words
The method of claim 1, further comprising removing one of said plurality of sub-data structures.
Claim 15
Dependent Claim
40 words
The method of claim 1, wherein said plurality of sub-data structures includes a plurality of keys, and wherein said method further comprises removing one key of said plurality of keys from one sub-data structure of said plurality of sub-data structures.
Claim 16
Dependent Claim
27 words
The method of claim 14, wherein said removing comprises using a key mask range of said one key to be removed to locate said one sub-data structure.
Claim 17
Dependent Claim
11 words
The method of claim 1, further comprising searching said data structure.
Claim 18
Dependent Claim
61 words
The method of claim 16, wherein said searching comprises searching said data structure for one or more target records associated with a requested key, said searching beginning with a more specific sub-data structure of said plurality of sub-data structures and proceeding to less specific sub-data structures of said plurality of sub-data structures until said one or more target records is collected.
Claim 19
Dependent Claim
131 words
The method of claim 16, wherein said searching comprises: determining whether a requested key belongs to a sub-data structure of said ordered plurality of sub-data structures, said determining beginning with a first sub-data structure of said ordered plurality of sub-data structures; selecting one or more target records associated with said requested key from said sub-data structure, when said requested key belongs to said sub-data structure; deciding whether one or more target records is still needed for said requested key; proceeding to a next sub-data structure of said ordered plurality of sub-data structures when said one or more target records is still needed for said requested key; repeating said determining, selecting, and deciding at said next sub-data structure and said proceeding until no more target records are needed for said requested key.
Claim 20
Dependent Claim
38 words
The method of claim 18, wherein said determining comprises performing a bit wise AND operation with said requested key and a key mask of said sub-data structure to determine whether said requested key belongs to said sub-data structure.
Claim 21
Dependent Claim
17 words
The method of claim 1, wherein said key masks designate variations in keys of said sub-data structures.
Claim 22
Dependent Claim
10 words
The method of claim 20, wherein said keys comprise addresses.
Claim 23
Dependent Claim
15 words
The method of claim 1, wherein said obtaining comprises defining said plurality of sub-data structures.
Claim 24
Dependent Claim
22 words
The method of claim 1, wherein each sub-data structure of said plurality of sub-data structures has associated therewith one or more addresses.
Claim 25
Dependent Claim
18 words
The method of claim 23, wherein each of said one or more addresses has a corresponding key mask.
Claim 26
Dependent Claim
22 words
The method of claim 1, wherein each sub-data structure of said plurality of sub-data structures has associated therewith a key mask range.
Claim 27
Dependent Claim
29 words
A memory comprising a data structure, said data structure comprising a plurality of sub-data structures ordered based on ranges of key masks associated with said plurality of sub-data structures.
Claim 28
Dependent Claim
29 words
A memory comprising a data structure, said data structure comprising a plurality of sub-data structures ordered based on ranges of key masks associated with said plurality of sub-data structures.
Claim 29
Dependent Claim
26 words
The memory of claim 26, wherein said plurality of sub-data structures are linked in a linked list in ascending order of said ranges of key masks.
Claim 30
Dependent Claim
17 words
The memory of claim 26, wherein said key masks designate variations in keys of said sub-data structures.
Claim 31
Dependent Claim
10 words
The memory of claim 28, wherein said keys comprise addresses.
Claim 32
Dependent Claim
22 words
The memory of claim 26, wherein each sub-data structure of said plurality of sub-data structures has associated therewith one or more addresses.
Claim 33
Dependent Claim
18 words
The memory of claim 30, wherein each of said one or more addresses has a corresponding key mask.
Claim 34
Dependent Claim
22 words
The memory of claim 26, wherein each sub-data structure of said plurality of sub-data structures has associated therewith a key mask range.
Claim 35
Dependent Claim
71 words
At least one program storage device readable by a machine, tangibly embodying at least one program of instructions executable by the machine to perform a method of creating a data structure, said method comprising: obtaining a plurality of sub-data structures; and ordering said plurality of sub-data structures based on ranges of key masks associated with said plurality of sub-data structures, wherein said data structure comprises said ordered plurality of sub-data structures.
Claim 36
Dependent Claim
71 words
At least one program storage device readable by a machine, tangibly embodying at least one program of instructions executable by the machine to perform a method of creating a data structure, said method comprising: obtaining a plurality of sub-data structures; and ordering said plurality of sub-data structures based on ranges of key masks associated with said plurality of sub-data structures, wherein said data structure comprises said ordered plurality of sub-data structures.
Claim 37
Dependent Claim
31 words
The at least one program storage device of claim 33, wherein said ordering comprises ordering said plurality of sub-data structures based on an ascending order of said ranges of key masks.
Claim 38
Dependent Claim
58 words
The at least one program storage device of claim 33, wherein a sub-data structure of said plurality of sub-data structures represents at least one group of one or more keys, and wherein any group associated with said sub-data structure has the same range of key mask as any other group that may be associated with said sub-data structure.
Claim 39
Dependent Claim
28 words
The at least one program storage device of claim 33, wherein said method further comprises determining said ranges of key masks associated with said plurality of sub-data structures.
Claim 40
Dependent Claim
55 words
The at least one program storage device of claim 36, wherein said determining comprises for a key mask associated with a sub-data structure: converting said key mask into a binary notation; and counting a number of zeros within said binary notation, said number of zeros providing an indication of the range of said key mask.
Claim 41
Dependent Claim
27 words
The at least one program storage device of claim 37, wherein said range of said key mask is two to the power of said number of zeros.
Claim 42
Dependent Claim
21 words
The at least one program storage device of claim 33, wherein said plurality of sub-data structures comprises a plurality of trees.
Claim 43
Dependent Claim
42 words
The at least one program storage device of claim 33, wherein said method further comprises adding another sub-data structure to said data structure, wherein said another sub-data structure is inserted in order in said data structure based on its key mask range.
Claim 44
Dependent Claim
23 words
The at least one program storage device of claim 33, wherein said method further comprises inserting a new key into said data structure.
Claim 45
Dependent Claim
93 words
The at least one program storage device of claim 41, wherein said inserting comprises: determining a key mask range for said new key; creating a new sub-data structure when said key mask range is not within said data structure; adding a key mask associated with said new key to an existing sub-data structure when said key mask range is within said data structure and said key mask is not among the key masks of said existing sub-data structure; and adding said new key to said new sub-data structure or said existing sub-data structure.
Claim 46
Dependent Claim
23 words
The at least one program storage device of claim 33, wherein said method further comprises removing one of said plurality of sub-data structures.
Claim 47
Dependent Claim
45 words
The at least one program storage device of claim 33, wherein said plurality of sub-data structures includes a plurality of keys, and wherein said method further comprises removing one key of said plurality of keys from one sub-data structure of said plurality of sub-data structures.
Claim 48
Dependent Claim
32 words
The at least one program storage device of claim 44, wherein said removing comprises using a key mask range of said one key to be removed to locate said one sub-data structure.
Claim 49
Dependent Claim
16 words
The at least one program storage device of claim 33, further comprising searching said data structure.
Claim 50
Dependent Claim
66 words
The at least one program storage device of claim 46, wherein said searching comprises searching said data structure for one or more target records associated with a requested key, said searching beginning with a more specific sub-data structure of said plurality of sub-data structures and proceeding to less specific sub-data structures of said plurality of sub-data structures until said one or more target records is collected.
Claim 51
Dependent Claim
136 words
The at least one program storage device of claim 46, wherein said searching comprises: determining whether a requested key belongs to a sub-data structure of said ordered plurality of sub-data structures, said determining beginning with a first sub-data structure of said ordered plurality of sub-data structures; selecting one or more target records associated with said requested key from said sub-data structure, when said requested key belongs to said sub-data structure; deciding whether one or more target records is still needed for said requested key; proceeding to a next sub-data structure of said ordered plurality of sub-data structures when said one or more target records is still needed for said requested key; repeating said determining, selecting, and deciding at said next sub-data structure and said proceeding until no more target records are needed for said requested key.
Claim 52
Dependent Claim
43 words
The at least one program storage device of claim 48, wherein said determining comprises performing a bit wise AND operation with said requested key and a key mask of said sub-data structure to determine whether said requested key belongs to said sub-data structure.
Claim 53
Dependent Claim
22 words
The at least one program storage device of claim 33, wherein said key masks designate variations in keys of said sub-data structures.
Claim 54
Dependent Claim
15 words
The at least one program storage device of claim 50, wherein said keys comprise addresses.
Claim 55
Dependent Claim
20 words
The at least one program storage device of claim 33, wherein said obtaining comprises defining said plurality of sub-data structures.
Claim 56
Dependent Claim
27 words
The at least one program storage device of claim 33, wherein each sub-data structure of said plurality of sub-data structures has associated therewith one or more addresses.
Claim 57
Dependent Claim
23 words
The at least one program storage device of claim 53, wherein each of said one or more addresses has a corresponding key mask.
Claim 58
Dependent Claim
27 words
The at least one program storage device of claim 33, wherein each sub-data structure of said plurality of sub-data structures has associated therewith a key mask range.
Claim 59
Dependent Claim
96 words
An article of manufacture, comprising: at least one computer useable medium having computer readable program code means embodied therein for causing the creating of a data structure, the computer readable program code means in said article of manufacture comprising: computer readable program code means for causing a computer to obtain a plurality of sub-data structures; and computer readable program code means for causing a computer to order said plurality of sub-data structures based on ranges of key masks associated with said plurality of sub-data structures, wherein said data structure comprises said ordered plurality of sub-data structures.
Claim 60
Dependent Claim
96 words
An article of manufacture, comprising: at least one computer useable medium having computer readable program code means embodied therein for causing the creating of a data structure, the computer readable program code means in said article of manufacture comprising: computer readable program code means for causing a computer to obtain a plurality of sub-data structures; and computer readable program code means for causing a computer to order said plurality of sub-data structures based on ranges of key masks associated with said plurality of sub-data structures, wherein said data structure comprises said ordered plurality of sub-data structures.
Claim 61
Dependent Claim
32 words
The article of manufacture of claim 56, further comprising computer readable program code means for causing a computer to determine said ranges of key masks associated with said plurality of sub-data structures.
Claim 62
Dependent Claim
46 words
The article of manufacture of claim 56, further comprising computer readable program code means for causing a computer to add another sub-data structure to said data structure, wherein said another sub-data structure is inserted in order in said data structure based on its key mask range.
Claim 63
Dependent Claim
41 words
The article of manufacture of claim 56, further comprising computer readable program code means for causing a computer to perform at least one of inserting a new key into said data structure and removing one of said plurality of sub-data structures.
Claim 64
Dependent Claim
49 words
The article of manufacture of claim 56, wherein said plurality of sub-data structures includes a plurality of keys, and further comprising computer readable program code means for causing a computer to remove one key of said plurality of keys from one sub-data structure of said plurality of sub-data structures.
Claim 65
Dependent Claim
23 words
The article of manufacture of claim 56, further comprising computer readable program code means for causing a computer to search said data structure.
Claim 66
Dependent Claim
19 words
The article of manufacture of claim 56, wherein said key masks designate variations in keys of said sub-data structures.
Claim 67
Dependent Claim
12 words
The article of manufacture of claim 62, wherein said keys comprise addresses.
Claim 68
Dependent Claim
37 words
The article of manufacture of claim 56, wherein said computer readable program code means for causing a computer to obtain comprises computer readable program code means for causing a computer to define said plurality of sub-data structures.
Claim 69
Dependent Claim
24 words
The article of manufacture of claim 56, wherein each sub-data structure of said plurality of sub-data structures has associated therewith one or more addresses.
Claim 70
Dependent Claim
20 words
The article of manufacture of claim 65, wherein each of said one or more addresses has a corresponding key mask.
Claim 71
Dependent Claim
24 words
The article of manufacture of claim 56, wherein each sub-data structure of said plurality of sub-data structures has associated therewith a key mask range.
Claim 72
Independent Claim
48 words
A system of creating a data structure, said system comprising: a plurality of sub-data structures; and means for ordering said plurality of sub-data structures based on ranges of key masks associated with said plurality of sub-data structures, wherein said data structure comprises said ordered plurality of sub-data structures.
Claim 73
Independent Claim
48 words
A system of creating a data structure, said system comprising: a plurality of sub-data structures; and means for ordering said plurality of sub-data structures based on ranges of key masks associated with said plurality of sub-data structures, wherein said data structure comprises said ordered plurality of sub-data structures.
Claim 74
Dependent Claim
22 words
The system of claim 68, further comprising means for determining said ranges of key masks associated with said plurality of sub-data structures.
Claim 75
Dependent Claim
36 words
The system of claim 68, further comprising means for adding another sub-data structure to said data structure, wherein said another sub-data structure is inserted in order in said data structure based on its key mask range.
Claim 76
Dependent Claim
32 words
The system of claim 68, further comprising at least one of means for inserting a new key into said data structure and means for removing one of said plurality of sub-data structures.
Claim 77
Dependent Claim
42 words
The system of claim 68, wherein said plurality of sub-data structures includes a plurality of keys, and wherein said system further comprises means for removing one key of said plurality of keys from one sub-data structure of said plurality of sub-data structures.
Claim 78
Dependent Claim
13 words
The system of claim 68, further comprising means for searching said data structure.
Claim 79
Dependent Claim
65 words
The system of claim 73, wherein said means for searching comprises means for searching said data structure for one or more target records associated with a requested key, said searching beginning with a more specific sub-data structure of said plurality of sub-data structures and proceeding to less specific sub-data structures of said plurality of sub-data structures until said one or more target records is collected.
Claim 80
Dependent Claim
17 words
The system of claim 68, wherein said key masks designate variations in keys of said sub-data structures.
Claim 81
Dependent Claim
10 words
The system of claim 75, wherein said keys comprise addresses.
Claim 82
Dependent Claim
15 words
The system of claim 68, further comprising means for defining said plurality of sub-data structures.
Claim 83
Dependent Claim
22 words
The system of claim 68, wherein each sub-data structure of said plurality of sub-data structures has associated therewith one or more addresses.
Claim 84
Dependent Claim
18 words
The system of claim 78, wherein each of said one or more addresses has a corresponding key mask.
Claim 85
Dependent Claim
22 words
The system of claim 68, wherein each sub-data structure of said plurality of sub-data structures has associated therewith a key mask range.
Claim 86
Independent Claim
46 words
A method of creating a data structure in a computing environment, said method comprising: obtaining a plurality of sub-data structures; and providing a key mask range for each sub-data structure of said plurality of sub-data structures, wherein said data structure comprises said plurality of sub-data structures.
Claim 87
Independent Claim
46 words
A method of creating a data structure in a computing environment, said method comprising: obtaining a plurality of sub-data structures; and providing a key mask range for each sub-data structure of said plurality of sub-data structures, wherein said data structure comprises said plurality of sub-data structures.
Claim 88
Dependent Claim
13 words
The method of claim 81, wherein each sub-data structure comprises a PATRICIA tree.
Claim 89
Dependent Claim
29 words
The method of claim 81, wherein each key mask range is associated with one or more key masks, said key masks designating variations in keys of said sub-data structures.
Claim 90
Dependent Claim
10 words
The method of claim 83, wherein said keys comprise addresses.
Claim 91
Dependent Claim
15 words
The method of claim 81, wherein said obtaining comprises defining a plurality of sub-data structures.
Claim 92
Dependent Claim
22 words
The method of claim 81, wherein each sub-data structure of said plurality of sub-data structures has associated therewith one or more addresses.
Claim 93
Dependent Claim
18 words
The method of claim 86, wherein each of said one or more addresses has a corresponding key mask.
Claim 94
Dependent Claim
32 words
A memory comprising a data structure, said data structure comprising a plurality of sub-data structures, wherein each sub-data structure of said plurality of sub-data structures has associated therewith a key mask range.
Claim 95
Dependent Claim
32 words
A memory comprising a data structure, said data structure comprising a plurality of sub-data structures, wherein each sub-data structure of said plurality of sub-data structures has associated therewith a key mask range.
Claim 96
Dependent Claim
29 words
The memory of claim 88, wherein each key mask range is associated with one or more key masks, said key masks designating variations in keys of said sub-data structures.
Claim 97
Dependent Claim
66 words
At least one program storage device readable by a machine, tangibly embodying at least one program of instructions executable by the machine to perform a method of creating a data structure, said method comprising: obtaining a plurality of sub-data structures; and providing a key mask range for each sub-data structure of said plurality of sub-data structures, wherein said data structure comprises said plurality of sub-data structures.
Claim 98
Dependent Claim
66 words
At least one program storage device readable by a machine, tangibly embodying at least one program of instructions executable by the machine to perform a method of creating a data structure, said method comprising: obtaining a plurality of sub-data structures; and providing a key mask range for each sub-data structure of said plurality of sub-data structures, wherein said data structure comprises said plurality of sub-data structures.
Claim 99
Dependent Claim
34 words
The at least one program storage device of claim 90, wherein each key mask range is associated with one or more key masks, said key masks designating variations of keys of said sub-data structures.
Claim 100
Independent Claim
43 words
A system of creating a data structure, said system comprising: a plurality of sub-data structures; and means for providing a key mask range for each sub-data structure of said plurality of sub-data structures, wherein said data structure comprises said plurality of sub-data structures.
Claim 101
Independent Claim
43 words
A system of creating a data structure, said system comprising: a plurality of sub-data structures; and means for providing a key mask range for each sub-data structure of said plurality of sub-data structures, wherein said data structure comprises said plurality of sub-data structures.
References Cited (Backward Citations)
US4468728A
Cited
US5095480A
Cited
US5539922A
Cited
US5519858A
Cited
US5574910A
Cited
US5386413A
Cited
US5640551A
Cited
US5701467A
Cited
US5557786A
Cited
US5655129A
Cited
US5787430A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-05-09 | 2003-11-08 | 2004-05-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-05-09 | 2007-11-08 | 2008-05-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-05-09 | 2011-11-08 | 2012-05-09 | $7700.00 | Window Closed / Lapsed |