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