US5860136A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for use of associated memory with large key spaces
Assignee: Fenner Investments Ltd
•
Filing: 1993-12-28
•
Granted: 1999-01-12
•
Expires: 2013-12-28
Abstract
Abstract To provide fast access times with very large key fields, an associative memory utilizes a location addressable memory and lookup table to generate from a key the address in memory storing an associated record. The lookup tables, stored in memory, are constructed with the aid of arithmetic data compression methods to create a near perfect hashing of the keys. For encoding into the lookup table, keys are divided into a string of symbols. Each valid and invalid symbol is assigned an index value, such that the sum of valid index values for symbols of a particular key is a unique value that is used as an address to the memory storing the record associated with that key, and the sum of keys containing invalid index values point to a location in memory containing similar data. Utilizing the lookup tables set and relational operations maybe carried out that provide a user with a maximum number of key records resulting from a sequence of intersection, union and mask operations.
Inventors
- 👤 Peter R. Fenner
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 01:10
CPC Classifications
H; H04; H04W; H04W40/00; H04W40/02; H03; H03M; H03M7/00; H03M7/30; H03M7/40; H03M7/4006; H04L; H04L12/00; H04L12/28; H04L12/46; H04L12/4604; H04L12/462; H04L12/4625; H04L45/00; H04L45/16; H04L45/74; H04L45/742; H04L9/00; H04L9/40; H04L2101/00; H04L2101/30; H04L61/00; H04L61/50; H04L61/5038; H04W4/00; H04W4/30; H04W4/40; H04W8/00; H04W8/26; H04W80/00; H04W80/04; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933
Claims Analysis
Total Claims: 38
Claim 1
Independent Claim
164 words
A method for finding a record of data in a record addressable location of memory using valid data keys comprised of a plurality of values associated with the record, said method further pointing to the location of related data for invalid data keys, the method comprising the steps of: assigning index values to valid and invalid symbol values within an entire key set prior to receiving a first key; receiving a key associated with a record of data stored in a memory having record addresses; arithmetically coding a key to a record index value; if the key is valid, providing the record index value to the memory as an address, the record associated with the key being stored at the address; if the key is invalid, providing a record index value pointing to a record stored in the memory which is related to a record associated with the key but not stored in the memory; and accessing the record of data in the memory.
Claim 2
Independent Claim
164 words
A method for finding a record of data in a record addressable location of memory using valid data keys comprised of a plurality of values associated with the record, said method further pointing to the location of related data for invalid data keys, the method comprising the steps of: assigning index values to valid and invalid symbol values within an entire key set prior to receiving a first key; receiving a key associated with a record of data stored in a memory having record addresses; arithmetically coding a key to a record index value; if the key is valid, providing the record index value to the memory as an address, the record associated with the key being stored at the address; if the key is invalid, providing a record index value pointing to a record stored in the memory which is related to a record associated with the key but not stored in the memory; and accessing the record of data in the memory.
Claim 3
Dependent Claim
106 words
The method of claim 1, wherein the step of assigning index values includes the steps of: dividing every key of a key set into a sequence of symbols; counting each use of a symbol value within each symbol position of the key sets; storing the count within a use count table; assigning index values to each symbol value within a symbol position having a non zero use count; and assigning index values to each symbol value within a symbol position having a zero use count equal to the index value of a non-zero use count symbol value most immediately following the zero use count symbol value.
Claim 4
Dependent Claim
155 words
The method of claim 1, wherein the step of assigning index values includes the steps of: dividing every key of a key set into a sequence of symbols; counting each use of a symbol value within each symbol position of the key set; storing the count within a use count table; counting the number of non zero entries within a symbol position of the use count table; determining a base value for the symbol position; and assigning to each symbol value with a non zero use count within a symbol position an index value equal to the count of the non zero entries from the beginning of the symbol position multiplied by the base value for the symbol position; and assigning to each symbol value with a zero use count within a symbol position, an index value equal to the value of the non zero symbol position immediately following the zero use count symbol position.
Claim 5
Dependent Claim
123 words
The method of claim 1, wherein the step of assigning index values includes the steps of: dividing every key of a key set into a sequence of symbol positions; counting each use of a symbol value within each symbol position of the key sets; storing the count within a use count table; counting the number of non zero entries within a symbol position of the use count table; determining a base value for each symbol position; and assigning to each symbol value within a symbol position, an index value equal to the base value for the symbol position plus the count of the previous non zero entries from the beginning of the symbol position, multiplied by the base value for the symbol position.
Claim 6
Independent Claim
132 words
An apparatus for performing set and relational operations on a plurality of sets of data records, the apparatus including: a plurality of memory locations for storing a use count table for each of a plurality of sets of records, each record in each of the sets of records being associated with a key and the use count table for a particular set of records storing the number of times a symbol occurs in a particular position in any of the keys for the records in that particular set; an associative processor for performing set and relational operations on the use count tables and, in response thereto, creating a use count table for keys of resultant set of data records which would result from operation on the plurality of sets of data records.
Claim 7
Independent Claim
132 words
An apparatus for performing set and relational operations on a plurality of sets of data records, the apparatus including: a plurality of memory locations for storing a use count table for each of a plurality of sets of records, each record in each of the sets of records being associated with a key and the use count table for a particular set of records storing the number of times a symbol occurs in a particular position in any of the keys for the records in that particular set; an associative processor for performing set and relational operations on the use count tables and, in response thereto, creating a use count table for keys of resultant set of data records which would result from operation on the plurality of sets of data records.
Claim 8
Dependent Claim
23 words
The apparatus of claim 5, wherein the associative set processor includes means for performing an intersection of a plurality of use count tables.
Claim 9
Dependent Claim
24 words
The apparatus of claim 5, wherein the associative set processor includes means for performing a mask operation on a plurality of use count tables.
Claim 10
Dependent Claim
30 words
The apparatus of claim 5, wherein the associative set processor includes a table access counter for sequencing through all index values resulting from a sequence of set and relational operations.
Claim 11
Independent Claim
93 words
A method for determining a maximum number of key records resulting from the union of a first and a second key record memory by performing the union of use count tables of the first and second key record memories comprising the steps of: determining the sum of the use counts for each symbol position; determining which symbol position contains a minimum sum of use counts; and outputting the minimum sum of use counts as the maximum number of possible key records resulting from the union of the first and second key record memories.
Claim 12
Independent Claim
93 words
A method for determining a maximum number of key records resulting from the union of a first and a second key record memory by performing the union of use count tables of the first and second key record memories comprising the steps of: determining the sum of the use counts for each symbol position; determining which symbol position contains a minimum sum of use counts; and outputting the minimum sum of use counts as the maximum number of possible key records resulting from the union of the first and second key record memories.
Claim 13
Dependent Claim
61 words
The method of claim 9, wherein the step of determining the minimum sum of use counts for each symbol position further includes the steps of: comparing each symbol value of the first use count table to the corresponding symbol value in the second use count table; and storing a maximum use count value resulting from each comparison in a results table.
Claim 14
Dependent Claim
41 words
The method of claim 10, wherein the step of determining which symbol position has a minimum of use counts further includes the step of: totalling the sum of the maximum use count values for each symbol value of each symbol position.
Claim 15
Independent Claim
81 words
A method for determining a maximum number of key records resulting from the intersection of a first and a second key record memory, comprising the steps of: determining the sum of use counts for each symbol position; determining which symbol position has the smallest sum value of use counts; and outputting the smallest sum value of use counts as the maximum number of key records resulting from the intersection of a first use count table and a second use count table.
Claim 16
Independent Claim
81 words
A method for determining a maximum number of key records resulting from the intersection of a first and a second key record memory, comprising the steps of: determining the sum of use counts for each symbol position; determining which symbol position has the smallest sum value of use counts; and outputting the smallest sum value of use counts as the maximum number of key records resulting from the intersection of a first use count table and a second use count table.
Claim 17
Dependent Claim
70 words
Method of claim 12, wherein the step of determining the sum of use counts for each symbol position further includes the steps of: comparing each use count value of the first use count table to the corresponding use count value in the second use count table to determine the minimum value at each symbol value position; and storing the minimum use count value from each comparison in a results table.
Claim 18
Dependent Claim
37 words
Method of claim 13, wherein the step of determining which symbol position has a minimum sum of use counts further comprises the step of: totalling the sum of the minimum use count values for each symbol position.
Claim 19
Independent Claim
116 words
A method for performing a mask operation between a mask table and a use count table comprising the steps of: comparing the use count table to the mask table; determining each non zero entry in the mask table; storing in a corresponding position of a results table the use count table entry for each non zero entry of the mask table; storing in a corresponding position of the results table a zero for each zero entry of the mask table; determining the sum of the resulting use counts for each symbol position; determining the minimum sum value; and outputting the minimum sum value as the maximum number of key record entries resulting from the mask operation.
Claim 20
Independent Claim
116 words
A method for performing a mask operation between a mask table and a use count table comprising the steps of: comparing the use count table to the mask table; determining each non zero entry in the mask table; storing in a corresponding position of a results table the use count table entry for each non zero entry of the mask table; storing in a corresponding position of the results table a zero for each zero entry of the mask table; determining the sum of the resulting use counts for each symbol position; determining the minimum sum value; and outputting the minimum sum value as the maximum number of key record entries resulting from the mask operation.
Claim 21
Dependent Claim
62 words
A method of claim 15, wherein the step of determining the minimum sum value of use counts for each symbol position further includes the steps of: comparing each symbol value of the use count table to the corresponding symbol value in the mask table; and storing the use count value from each comparison with a non-zero mask value in a results table.
Claim 22
Dependent Claim
50 words
The method of claim 16, wherein the step of determining the minimum sum for each symbol position further includes the steps of: totalling the sum of the resulting use count values for each symbol position; comparing all of the sums for each symbol position to determine the minimum sum value.
Claim 23
Independent Claim
200 words
A method for encoding keys for use in an associative memory of a data processing system, each key including a plurality of symbols, each symbol having a predetermined symbol value and occupying a predefined symbol position; the method comprising the steps of: encoding each key in a key set, the step of encoding a key in the key set including assigning and storing in an index table stored in a memory of a data processing system an index value for each symbol present in at least one symbol position of the key such that index values for all symbols in the key to which an index value is assigned compute to a record index value uniquely associated with that key; and filling in index values in the index table for the at least one symbol position, the step of filling in index values including, for each symbol in a predetermined set of symbols which is not present in the at least one symbol position in any key in the key set, assigning and storing an index value equal to the index value assigned to a next adjacent symbol present in the at least one symbol position in any encoded key.
Claim 24
Independent Claim
200 words
A method for encoding keys for use in an associative memory of a data processing system, each key including a plurality of symbols, each symbol having a predetermined symbol value and occupying a predefined symbol position; the method comprising the steps of: encoding each key in a key set, the step of encoding a key in the key set including assigning and storing in an index table stored in a memory of a data processing system an index value for each symbol present in at least one symbol position of the key such that index values for all symbols in the key to which an index value is assigned compute to a record index value uniquely associated with that key; and filling in index values in the index table for the at least one symbol position, the step of filling in index values including, for each symbol in a predetermined set of symbols which is not present in the at least one symbol position in any key in the key set, assigning and storing an index value equal to the index value assigned to a next adjacent symbol present in the at least one symbol position in any encoded key.
Claim 25
Dependent Claim
35 words
The method of claim 18 further comprising the steps of: receiving an unencoded key; returning a record index computed from the index values stored in the index table for symbols present in the unencoded key.
Claim 26
Dependent Claim
19 words
The method of claim 19 wherein each key in a key set is encoded in a predetermined lexigraphic order.
Claim 27
Dependent Claim
80 words
The method of claim 18 further comprising the steps of: for each symbol present in the at least one symbol position in any of the keys in the key set, setting a flag in the memory of the data processing system to a first value; and for each symbol not present in the at least one of symbol positions in any key in the key set, setting a flag in memory of the data processing system to a second value.
Claim 28
Dependent Claim
65 words
The method of claim 21 further including the steps of: receiving an unencoded key; returning a record index computed from the index values stored in the index table for symbols present in the unencoded key; and returning an indication of whether any of the symbols in the unencoded key for which an index value is assigned is a symbol not present in the key set.
Claim 29
Dependent Claim
94 words
The method of claim 18 further comprising: receiving an unencoded key; returning a record index computed from the index values stored in the index table for symbols present in the unencoded key; returning an indication of whether any of the symbols in the unencoded key for which an index value is assigned is a symbol not present in the key set; and storing data associated with the unencoded key in a first location in the memory identified by the record index if data associated with another key is not stored at the first location.
Claim 30
Dependent Claim
101 words
The method of claim 23 further comprising: if there is data stored at the first location associated with a key other than the unencoded key, encoding the unencoded key by assigning and storing in the index table an index value for a symbol in the unencoded key not found in any previously encoded key such that the index values for all symbols in the unencoded key compute to a record index value uniquely associated with that key; and storing the data associated with the unencoded key at a second location in the memory indicated by the unencoded key's record index value.
Claim 31
Dependent Claim
59 words
The method of claim 24 further comprising determining whether any one of the previously encoded keys has a changed record index value as a consequence of encoding the unencoded key and, if so, moving the record associated with the one of the previously encoded keys to a third location in the memory identified by the changed record index value.
Claim 32
Dependent Claim
15 words
The method of claim 18 wherein the next adjacent symbol is a higher order symbol.
Claim 33
Dependent Claim
15 words
The method of claim 18 wherein the next adjacent symbol is a lower order symbol.
Claim 34
Dependent Claim
197 words
A data processing system having an associative memory in which data is accessed using keys associated with the data, each key including a plurality of symbols, each symbol having a predetermined symbol value and occupying a predefined symbol position; the data processing system comprising: means for encoding each key in a key set, the means for encoding a key in the key set including means for assigning and storing in an index table in a memory of the data processing system an index value for each symbol present in at least one symbol position of the key such that index values for all symbols in the key to which an index value is assigned compute to a value uniquely associated with that key; and means for filling in index values in the index table for the at least one symbol position, the means for filling in index values including means for assigning and storing for each symbol in a predetermined set of symbols which is not present in the at least one symbol position in any key in the key set an index value equal to the index value assigned to a next lowest order valid symbol.
Claim 35
Dependent Claim
197 words
A data processing system having an associative memory in which data is accessed using keys associated with the data, each key including a plurality of symbols, each symbol having a predetermined symbol value and occupying a predefined symbol position; the data processing system comprising: means for encoding each key in a key set, the means for encoding a key in the key set including means for assigning and storing in an index table in a memory of the data processing system an index value for each symbol present in at least one symbol position of the key such that index values for all symbols in the key to which an index value is assigned compute to a value uniquely associated with that key; and means for filling in index values in the index table for the at least one symbol position, the means for filling in index values including means for assigning and storing for each symbol in a predetermined set of symbols which is not present in the at least one symbol position in any key in the key set an index value equal to the index value assigned to a next lowest order valid symbol.
Claim 36
Dependent Claim
38 words
The data processing system of claim 28 further comprising: means for receiving an unencoded key; and means for computing a record index from the index values stored in the index table for symbols present in the unencoded key.
Claim 37
Dependent Claim
72 words
The data processing system of claim 29 further comprising: means for indicating whether any of the symbols in the unencoded key for which an index value is assigned is a symbol not present in the key set; and means for storing data associated with the unencoded key in a first location in the memory identified by the record index if data associated with another key is not stored at the first location.
Claim 38
Dependent Claim
23 words
The apparatus of claim 5, wherein the associative set processor includes means for performing a union of a plurality of use count tables.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-01-11 | 2002-07-13 | 2003-01-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-01-11 | 2006-07-13 | 2007-01-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-01-11 | 2010-07-13 | 2011-01-12 | $7700.00 | Window Closed / Lapsed |