Associative memory for very large key spaces

• US 5,490,258 A
• Filed: 09/29/1992
• Issued: 02/06/1996
• Est. Priority Date: 07/29/1991
• Status: Expired due to Term

• Current Assignee: Fenner Investments Limited
• Original Assignee: Peter R. Fenner
• Inventors: Fenner, Peter R.
• Primary Examiner(s): Harvey, Jack B.
• Assistant Examiner(s): WHITFIELD, MICHAEL
• Application Number:
  US07/952,988
• Time in Patent Office: 1,225 Days
• Field of Search: 395/400, 395/425, 370/85.12, 370/85.13, 370/85.14, 370/85.15, 341/51, 341/65, 341/67, 341/106
• US Class Current: 711/1
• CPC Class Codes: G06F 16/9014 hash tables
• 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 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

Abstract

To provide for fast access times with very large key fields, an associative memory utilizes a location addressable memory and look up tables to generate from a key an address in memory storing an associated record. The look up tables, stored in a memory, are constructed with the aid of arithmetic data compression methods to create a near perfect hashing of the keys. For encoding into the look up table, keys are divided into a string of symbols. Each symbol is assigned an index value, such that a sum of 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.

Claims

1. A method for finding a record of data in a record memory with a key string associated with the record, the method comprising the steps of:

assigning a key index value for each Symbol(i,j) of a predetermined key in a predetermined key set, where i represents a predetermined symbol position in the key and j represents a predetermined symbol value, the symbol positions and the symbol values each assuming a predetermined order 1 in a first range 1 to N and a second range 1 to M, respectively;

receiving a first key that is a member of the predetermined key set;

summing the key index value assigned to Symbol(i,j) for i=1 to N to produce an integer record index value;

providing the record index value to a record memory as a record address to a record of data associated with the first key and stored in the memory; and

accessing the record of data in the memory in response to receiving the first key.

2. The method of claim 1 wherein the step of assigning key index values includes the steps of:

determining a base value for symbol position i=I; and

assigning to Symbol(I,J), a symbol j=J in position i=I where J is in the range 1 to M and I is in the range 1 to N, which is present in at least one of keys in the predetermined key set, an index value equal to the number of symbols for j=1 to M that have been assigned an index value in symbol position I, times the base value for the symbol position I.

3. The method of claim 2 wherein the step of determining a base value for a symbol position I where I is in the range 2 to N, comprises the step of assigning a base value equal to a base value of symbol position (I-1) multiplied by the number of symbols in symbol position (I-1) assigned an index value.

4. The method of claim 1 wherein the step of assigning a key index value for each Symbol(i,j) comprises the step of assigning to Symbol(I,J), a symbol J in position I where j=J and J is within the range of 1 to M and where i=I and I is within the range of 1 to N, index value Index(I,J) such that the smallest sum of Index(i,j), over i=1 to I, for any of the keys in the predetermined key set sharing Symbol(I,J) is larger than the largest sum of previously assigned Index(i,j), over i=1 to I, for any of the keys in the key set.

5. The method of claim 4 wherein the step of assigning a key index value comprises the steps of:

for each Symbol(i,j), i=1 and j=1 to M, that occurs in at least one of the keys in position i=1, assigning a predetermined value; and

for each Symbol(i,j), from i=2 to N and j=1 to M, that occurs in at least one of the keys in position i;

determining a maximum suffix string for Symbol(K,P) where P is a symbol with the largest assigned index value occurring in symbol position i=K in at least one of the keys, K being a symbol position in the range 1 to N and equal to I-1 if no index values have been assigned in symbol position I and equal to I otherwise, I being a symbol in the range of 1 to N; and

assigning for Symbol(I,J) a symbol j=J in position i=I, where J is in the range 1 to M but not equal to P, an index value equal to the sum of the index value assigned to Symbol(K,P) and the index values assigned to each symbol occurring in positions i=1 to (K-1) in the maximum suffix string of the Symbol(K,P).

6. The method of claim 4 wherein the step of assigning a key index value comprises the steps of:

for each Symbol(i,j), i=1 and j=1 to M, that occurs in at least one of the keys in position i=1 assigning a predetermined value; and

for each Symbol(i,j), from i=2 to N and j=1 to M, that occurs in at least one of the keys in position i;

determining a maximum suffix string for Symbol(K,P) where P is a symbol with the largest assigned index value occurring in symbol position i=K in at least one of the keys, K being a symbol position in the range 1 to N and equal to I-1 if no index values have been assigned in symbol position I and equal to I otherwise, I being a symbol in the range of 1 to N,;

determining a minimum suffix string for Symbol (I,J), where J is a next higher order symbol in the range of 1 to M after symbol P that occurs in position I in at least one of the keys;

the minimum suffix string being a lowest order string of symbols present in symbol positions i=1 to I-1 in at least one of the keys; and

assigning for Symbol(I,J) an index value equal to the sum of the index value assigned to Symbol(K,P) and the index values assigned to each symbol occurring in positions i=1 to (K-1) in the maximum suffix string of the Symbol(K,P) minus the sum of index values assigned to each of the symbols in the minimum suffix string of Symbol(I,J).

7. An associative memory for accessing records of data with an associated key of data without searching, the associative memory comprising:

a memory circuit for storing records of data in a record table, a given record of data being accessed in the record table by presentation of a numerical value;

a first logic circuit for generating the numerical value from a key of data associated with a record in response to being presented with the key, and for providing the numerical value to the memory to uniquely identify a record of data associated with the key, the first logic circuit including a table of index values assigned to each symbol in the key and an adder for summing the index values for the symbols in the key to generate the numerical value; and

a second logic circuit for encoding a new key into the first logic circuit, the second logic circuit including means for detecting whether each symbol in a new key has been assigned an index value and, if not, creating a new index value for the symbol.

8. The associative memory of claim 7 wherein the second logic circuit further comprises:

means for determining a base value for a symbol position; and

means for assigning to a symbol value within a symbol position an index value equal to the product of number of lower order symbols within the position assigned an index value and the base value for the symbol position.

9. The associative memory of claim 8 wherein each key is comprised of a plurality of symbols, each symbol assuming one of a plurality of values having a predetermined order j in a first range 1 to M, and occupying one of a plurality of symbol positions each having an order i in a second range 1 to N:

and wherein the means for determining a base value includes means for assigning to symbol position i=1, a predetermined base value, and, for symbol positions i=2 to N, means for assigning a base value for position i=I, where I is in the range of 2 to N, equal to a base value of symbol position (I-1) multiplied by the number of symbols previously assigned an index value in symbol position (I-1).

10. The associative memory of claim 7 wherein each key is comprised of a plurality of symbols, each symbol assuming one of a plurality of values having a predetermined order j in a first range 1 to M and occupying one of a plurality of symbol, positions each having an order i in a second range 1 to N;

and wherein the means for creating a new index value includes means for assigning to SYMBOL(I,J), a symbol j=J in position i=I, where J is in the range 1 to M and I is in the range of 1 to N, in one of a plurality of keys index value INDEX(I,J) such that the smallest sum of INDEX(i,j), over i=1 to I, for any of the keys in the predetermined key set sharing SYMBOL(I,J) is larger than the largest sum of previously assigned Index(i,j), over i=1 to I, for any of the keys in the key set.

11. The associative memory of claim 10 wherein the second logic circuit is comprised of:

means for determining a maximum suffix string for each symbol value in each symbol position assigned an index value;

a max suffix table for storing the maximum suffix strings; and

means for assigning an index value to a symbol value equal to the index value of a next lower order symbol in the same symbol position assigned an index value, plus the sum of the index values of the symbols in the maximum suffix string for the next lower order symbol.

12. The associative memory of claim 10 wherein the second logic circuit is comprised of:

means for determining a maximum and a minimum suffix string for each symbol value in each symbol position assigned an index value;

a max suffix table for storing the maximum suffix strings;

a min suffix table for storing the minimum suffix strings; and

means for assigning an index value to a symbol value equal to the index value of a next lower order symbol in the same symbol position assigned an index value, plus the sum of the index values of the symbols in the maximum suffix string for the next lower order symbol, minus the sum of the index values assigned the symbol in the minimum suffix string of the symbol being assigned the index value.

13. A method of accessing a record of data with a key string associated with the record, the key string having a plurality of symbols SYMBOL(j) from a set of symbols having a predetermined lexigraphic order j, j=1 to M;

the method comprising the steps of;

arithmetically coding with an encoder, according to a predetermined model, a key string as a numerical value;

using the numerical value to uniquely identify a record of data associated with the key string in a record table stored in a record memory; and

accessing the record of data associated with the key in response to the record memory receiving the key.

14. The method of claim 13 wherein the step of arithmetically coding further comprises the steps of determining an index value INDEX(j) for each SYMBOL(j) occurring in the key string according to the predetermined model and combining index values INDEX(j) for each SYMBOL(j) occurring in the first key string according to a predetermined arithmetic operation to generate the numerical value associated with first key string.

15. The method of claim 13 wherein the key string is divided into a predetermined order of symbol positions i=1 to N;

wherein the step of determining further includes looking up in an index table a preassigned index value INDEX(i,j) for each SYMBOL(i,j) present in a plurality of keys, the plurality of keys including the key string; and

wherein the step of combining index values includes the step of summing to the numerical value the index values INDEX(i,j) for SYMBOL(i,j) occurring in each symbol position i=1 to N to create the numerical value.

16. The method of claim 15 wherein preassigned index value INDEX(I,J), stored in the index table for SYMBOL(I,J), a symbol j=J in position i=I, where J is in the range 1 to M and I is in the range 1 to N, is equal to or greater than a largest possible sum of INDEX(i,j) assigned for each symbol position i, i=1 to I-1, and INDEX(I,H) where j=H and H is the order of a next lower order symbol in position I having assigned to it an index value.

17. The method of claim 15 wherein preassigned index value INDEX(I,J), stored in the index table for SYMBOL(I,J), a symbol j=J, where J is in the range 1 to M, in position i=I, where I is in the range 1 to N, is equal to or greater than a largest possible sum of INDEX(i,j) previously assigned for each symbol position i, i=1 to I-1, plus the largest value of INDEX(I,j) for j not equal to J previously assigned in symbol position I.

18. The method of claim 15 further including the step of assigning an index value INDEX(i,j) for each SYMBOL(i,j) occurring in a plurality of key strings, the plurality of key strings including the key string, and storing the index values in the index table.

19. The method of claim 18 wherein the step of determining an index value for each symbol further includes the steps of:

determining for each symbol position a base value BASE(i), BASE(1) being assigned a predetermined base value and BASE(i), i=2 to N assigned a value equal to BASE(i-1) multiplied by the number symbols in symbol position (i-1) assigned an index value; and

setting INDEX(I,J), where i=I and I is in the range 1 to N, and where j=J and J is in the range 1 to M, equal to the sum of INDEX(I,H) and BASE(I), where H is the order of the next lower order symbol in symbol position I having assigned to it an index value.

20. The method of claim 18 wherein the step of assigning an index value further includes setting, for SYMBOL(I,J), where i=I and I is in the range 1 to N and j=J and J is in the range 1 to M, present in one of the keys of the key set, INDEX(I,J) equal to or greater than a largest possible sum of INDEX(i,j) previously assigned for each symbol position i, i=1 to I-1, plus the largest value of INDEX(I,j) for j not equal to J previously assigned in symbol position I.

21. The method of claim 18 wherein the step of assigning an index value further includes the step of setting, for SYMBOL(I,J), where i=I and I is in the range 1 to N, and where j=J and J is in the range 1 to M, that is present in one of the plurality of keys an INDEX(I,J) equal to or greater than a largest possible sum of INDEX(i,j) assigned for each symbol position i, i =1 to I-1, and INDEX(I,H) where H is the order of a next lower order symbol in position I having assigned to it an index value.

22. The method of claim 18 wherein the step of assigning an index value further includes the step of assigning to SYMBOL(I,J), where i=I and I is in the range 1 to N and where j=J and J is in the range 1 to M, an index value INDEX(I,J) such that the smallest sum of INDEX(i,j), over i=1 to I, for any key in the plurality of keys sharing SYMBOL(I,J) is larger than the largest sum of previously assigned INDEX(i,j), over i=1 to I, for any key in the plurality of keys.

23. An associative memory for accessing one of a plurality of records of data with an associated key string without searching through all of the records of data, the key string having one or more symbol positions i, i=1 to N, each symbol position occupied by a symbol, SYMBOL(i,j), from a set of symbols having a predetermined lexigraphic order j=1 to M, the associative memory comprising:

an encoder for receiving each symbol in a key string and arithmetically encoding the key string as a numerical value for uniquely identifying a record address to a record of data associated with the key stored in a record table; and

memory for storing the record table and, in response to receiving the record address accessing the record of data in the record table.

24. The associative memory according to claim 23 wherein the encoder includes a second memory for storing a look-up index table storing INDEX(i,j) for each SYMBOL(i,j) present in a plurality of key strings that includes the first key string, the second memory reading out, in response to the encoder receiving one of the plurality of key strings, INDEX(i,j) for each Symbol(i,j,) present in said one of the plurality of key strings, the adder then summing INDEX(i,j) for each SYMBOL(i,j) present to said one of the plurality of keys strings to produce the numerical value.

25. The associative memory according to claim 24 further including means for assigning to a symbol j=J in position i=I, where J is in the range 1 to M and I is in the range 1 to N, in one of a plurality of keys an index value INDEX(I,J) equal to or greater than the largest possible sum of INDEX(i,j) stored in the look-up table for i=1 to I-1, plus INDEX(I,j) having the largest value for any other SYMBOL(I,j), where j is not equal to J.

26. The associative memory according to claim 24 further including means for assigning to a symbol j=J in position i=I, where J is in the range 1 to M and I is in the range 1 to N, in one of a plurality of keys an index value INDEX(I,J) equal to or greater than the largest possible sum of INDEX(i,j) stored in the look-up table for i=1 to I-1, plus INDEX(I,H) where H is the order of the next lower order symbol in position I having assigned to it an index value.

27. The associative memory of claim 24 further including:

means for determining for each symbol position a base value BASE(i), the means for determining assigning to BASE(1) a predetermined base value and to BASE(i), i=2 to N, assigning a value equal to BASE(i-1) multiplied by the number symbols in symbol position (i-1) assigned an index value; and

means for assigning for SYMBOL(I,J), a symbol j=J in position i=I, where J is in the range 1 to M and I is in the range 1 to N, an INDEX(I,J) equal to the sum of INDEX(I,L) and BASE(I) where j=L and L is in the range of 1 to M and is the order of the next lower order symbol in symbol position I having assigned to it an index value.

28. The associative memory according to claim 24 further including means for assigning to SYMBOL(I,J), where j=J and J is in the range 1 to M and i=I and I is in the range 1 to N, that is present in one of a plurality of keys an index value INDEX(I,J) such that the smallest sum of INDEX(i,j), over i=1 to I, for a key in the predetermined key set sharing SYMBOL(I,J) is larger than the largest sum of previously assigned INDEX(i,j), over i=1 to I, for a key in the key set.

29. A method for indexing each key in key set as a unique numerical value for uniquely identifying the key, the method comprising the steps of:

dividing each key in a plurality of key strings into a plurality of symbols, each symbol being a member of a set of symbols having a predetermined order j=1 to M and occupying a one of a plurality of predefined positions i having a predetermined order i=1 to I;

assigning an index value Index(i,j) to each Symbol(i,j) occurring in at least one of the plurality of key strings such that the sum of index values for each symbol in each key in the plurality of key strings is a numerical value uniquely associated with that key; and

storing each assigned index values Index(i,j) in a look-up table in memory for retrieval in response to presentation of a Symbol(i,j).

30. The method of claim 29 wherein the step of assigning a key index value to Symbol(i,j) comprises the step of assigning to Symbol(I,J), where j=J and J is in the range 1 to M and where i=I and I is in the range 1 to N, an index value INDEX(I,J) such that the smallest sum of INDEX(i,j), over i=1 to I, for any key in the predetermined key set sharing SYMBOL(I,J) is larger than the largest sum of previously assigned INDEX(i,j), over i=1 to I, for any key in the key set.

31. The method of claim 29 wherein the step of assigning an index value to SYMBOL(i,j) further includes setting, for SYMBOL(I,J), where j=J and J is in the range 1 to J and where i=I and I is in the range 1 to N, present in one of the keys of the key set, an INDEX(I,J) equal to or greater than a largest possible sum of INDEX(i,j) previously assigned for each symbol position i, i=1 to I-1, plus the largest value of INDEX(I,j) for j not equal to J previously assigned in symbol position I.

32. The method of claim 29 wherein the step of assigning an index value further includes the step of setting for SYMBOL(I,J), where j=J and J is in the range 1 to M and where i=I and I is in the range 1 to N, present in one of the plurality of keys, an INDEX(I,J) equal to or greater than a largest possible sum of INDEX(i,j) assigned for each symbol position i, i=1 to I-1 plus INDEX(I,H) where j=H and H is the order of a next lower order symbol in the range 1 to M in position I having assigned to it an index value.