Method and apparatus for use of associated memory with large key spaces
First Claim
1. 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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
31 Claims
-
1. 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. - View Dependent Claims (2, 3, 4)
-
-
5. 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. - View Dependent Claims (6, 7, 8, 31)
-
-
9. 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. - View Dependent Claims (10, 11)
-
-
12. 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. - View Dependent Claims (13, 14)
-
-
15. 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. - View Dependent Claims (16, 17)
-
-
18. 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. - View Dependent Claims (19, 20, 21, 22, 23, 24, 25, 26, 27)
- the method comprising the steps of;
-
28. 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. - View Dependent Claims (29, 30)
- the data processing system comprising;
Specification