Method and apparatus for use of associated memory with large key spaces

• US 5,860,136 A
• Filed: 12/28/1993
• Issued: 01/12/1999
• Est. Priority Date: 06/16/1989
• Status: Expired due to Term

• Current Assignee: Fenner Investments Limited
• Original Assignee: Peter R. Fenner
• Inventors: Fenner, Peter R.
• Primary Examiner(s): Chan, Eddie P.
• Assistant Examiner(s): NGUYEN, THAN VINH
• Application Number:
  US08/174,361
• Time in Patent Office: 1,841 Days
• Field of Search: 395/425, 395/401, 395/395, 395/888, 395/497.01, 395/601, 395/602, 395/603, 364/200, 370/94, 370/85.13, 370/358, 370/409, 370/475, 370/417, 370/333, 370/400, 370/396, 370/397, 369/49, 365/49, 365/94, 711/201, 711/202
• US Class Current: 711/201
• CPC Class Codes: H03M 7/4006 Conversion to or from arithmetic code
• CPC Class Codes: H04L 12/4625 Single bridge functionality, e.g. connection of two networks over a single bridge
• CPC Class Codes: H04L 2101/30 Types of network names
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 61/5038 for local use, e.g. in LAN or USB networks, or in a controller area network [CAN]
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: H04W 4/40 for vehicles, e.g. vehicle-to-pedestrians [V2P]
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 8/26 Network addressing or numbering for mobility support
• CPC Class Codes: H04W 80/04 Network layer protocols, e.g. mobile IP [Internet Protocol]
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

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.

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.

2. 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.

3. 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.

4. 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.

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.

6. The apparatus of claim 5, wherein the associative set processor includes means for performing an intersection of a plurality of use count tables.

7. The apparatus of claim 5, wherein the associative set processor includes means for performing a mask operation on a plurality of use count tables.

8. 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.

31. The apparatus of claim 5, wherein the associative set processor includes means for performing a union of a plurality of use count tables.

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.

10. 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.

11. 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.

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.

13. 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.

14. 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.

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.

16. 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.

17. 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.

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.

19. 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.

20. The method of claim 19 wherein each key in a key set is encoded in a predetermined lexigraphic order.

21. 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.

22. 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.

23. 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.

24. 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.

25. 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.

26. The method of claim 18 wherein the next adjacent symbol is a higher order symbol.

27. The method of claim 18 wherein the next adjacent symbol is a lower order symbol.

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.

29. 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.

30. 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.