 |
Claims  |
|
|
I 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.
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. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
THE FIELD OF THE INVENTION
The present invention relates to associative memory systems, and more
particularly to associative memory systems for handling large key spaces.
BACKGROUND OF THE INVENTION
Data communication between computers has become a standard part of
worldwide networks in many areas of endeavors. These individual networks
gather data about diverse subjects and exchange information of common
interest among various media groups. Most of these networks are
independent communication entities that are established to serve the needs
of a particular group. Some use high speed connections while others use
slow speed networks. Some use one type of protocol while others use a
different type of protocol. Other well-known differences between networks
also exist. There has been considerable effort expended in an attempt to
make it possible to interconnect disparate physical networks and make them
function as a coordinated unit.
Whether they provide connections between one computer and another or
between terminals and computers, communication networks are divided
basically into circuit-switched or packet-switched types. Circuit-switched
networks operate by forming a dedicated connection between two points.
Such a dedicated circuit could be represented by a telephone connected
through a circuit from the originating phone to a local switching office,
across trunk lines to a remote switching office and finally to the
destination telephone. When that circuit is complete, no other
communications can travel over the wires that form the circuit. The
advantage of such circuit lies in the fact that once it is established, no
other network activity will decrease the capacity of the circuit. The
disadvantage is that concurrent communication cannot take place on the
line or circuit.
Packet-switched networks take an entirely different approach. In such
system, traffic on the network is divided into small segments of
information called packets that are multiplexed on high capacity
intermachine connections. Each packet carries identification that enables
other units on the network to know whether they are to receive the data or
are to transmit it to another destination. The chief advantage of
packet-switching is that multiple communications among information sources
such as computers can proceed concurrently with connections between
machines being shared by all machines that are communicating. The
disadvantage is that as activity increases, a given pair of communicating
devices can use less of the network capacity.
A new technology has been developed that is called Internet and it
accommodates information or communication networks having multiple,
diverse underlying hardware technologies, or physical media protocols, by
adding both physical connections and a new set of conventions. One of the
problems with the use of Internet is that addresses refer to connections
and not to the device itself that is sending the information. Thus, if a
communication source, such as an aircraft for example, moves from one
communication network to another, its Internet address must change.
Specifically, if an aircraft is transmitting a particular location address
code in one communication network in the Internet system and it moves to
another, its Internet address must change. It is similar to a traveler who
has a personal computer operating with a first communication network. If
the computer is taken on a trip and connected into the information system
after reaching the new destination, a new location address for the
computer must be obtained for the new destination. It is also similar to
moving a telephone from one location to another. A new telephone number
must be assigned to the telephone at the new location. The telephone
cannot be reached at the new location with the old number. Further, when
routing a signal from one station to another through a plurality of nodes
forming multipath connections, the message format contains a destination
location address that is used to make the routing decisions. When the
system has multiple addresses, the route taken by the packets traveling to
a particular station address depends upon the location code embedded in
the station address.
Thus, two problems occur in such message communication networks. The first
is the requirement to change the address code of the communication source
when it is at different locations in the network and the second is routing
the message to the receiver if the address has changed. It can be seen,
then, that with the presently existing system, if most A transmits a
message to host B with a specific location code, by the time the message
arrives at that location, host B may have moved to a new information
processing network and changed its location code to conform to the new
system and thus could not receive the message transmitted by host A. Host
A must know that host B has entered the new information processing system
and then must change the format of the new location address in order to
contact host B.
The present system overcomes the disadvantages of the prior art by simply
assigning a fixed, unique and unchanging identification code to both host
A and host B. As host B enters into a new network access system, it
transmits its identification code to the nearest node and all of the nodes
interconnecting all of the disparate networks each store, with the unique
identification code of host B, the address of those nodes which can
communicate with host B so that a path can be completed through the nodes
between host A and host B.
In the prior art, hierarchical logical routing is used to address highly
mobile end-systems (computers on ships and aircraft, etc.) that are
simultaneously connected to multiple communication paths and employ
multicast message traffic. Hierarchical routing schemes have great
difficulty solving this combined set of problems and a new approach must
be used to overcome the difficulties in using hierarchical routing to meet
the user's diverse requirements.
Further, in the prior art, a logical network address of larger than 32 bits
was too large to be used as a directory access method to locate a receiver
at a location address specified in the message format. Specialized
hierarchical address structures which embed network location information
have been employed to reduce the size of the access index to the routing
table and also to reduce the size of the routing table. This approach
couples the address structure to the Internet routing software design.
There are various "hidden assumptions" of hierarchical addressing. These
"hidden assumptions" are (1) the processing load of the router CPU
increases as the size of the routing table increases and (2) computer
memory is a scarce and expensive resource. The present invention overcomes
the first of these problems while computer memory technology has addressed
the second problem by making very large memories cost effective.
Traditional approaches for designing a network address structure have
either been intimately entwined in the design of efficient routing look-up
tables or assigned by a central authority such as ARPANET. Neither of
these approaches gives much if any thought to the needs, desires or ease
of use of the group which must make operational use of the system. In an
age of fourth generation database languages and high level compilers,
network addresses are basically hand-coded in low level language.
Addresses and address structures are difficult to change as a mobile
end-unit moves from one communication network to another. Experts are
often required to ensure that operational equipment is properly integrated
into the system. ISO (International Standards Organization) addressing
provides a basis for a much better approach but the overall design and
administration of a network addressing structure must be elevated to an
easily supported, user friendly, distributed architecture to effectively
support the user's long-term needs.
Traditional directory access methods, whether for Internet routing,
databases or compiler symbol tables, fall into three basic categories:
(1) Sorted Tables. The keys are sorted by some rule which allows a
particular search strategy (e.g., binary search) to locate the key.
Associated with the key location is a pointer to the data.
(2) Tree Structures. Parts of the key field are used to traverse a tree
data structure to a leaf node which holds the data or a pointer to the
data.
(3) Hashing. Some arithmetic function is applied to the key which
compresses the key field into a chosen integer range which is the initial
directory size. This integer is the index into the directory which usually
contains a pointer to the data.
Each of these techniques has advantages and disadvantages when applied to
the Internet routing table access design. Sorted tables provide the
potentially most compact storage utilization at the cost of having access
computations which grow with the number of addresses (keys) active in the
system. Computations for sorted tables grow proportional to the log of the
number of keys plus one. Using sorted tables, the router processing will
slow down as the number of active addresses increases. But the desirable
result is to make computation independent of the number of active
addresses. It has been theorized, without providing a method, that a
scheme to access sorted tables could exist which always allows access in
two probes. To date, no methods have been proposed which approaches this
theoretical result.
Tree data structures have been widely employed for directories,
particularly for file systems, such as the UNIX file system where larger
amounts of auxiliary disc storage is being managed. Trees offer access
times that are proportional to the length of the address (key). Trees
trade off memory space for processing load. More branches at each level
decreases the processing but uses much more memory. For example, a binary
tree uses two locations at each level for each bit in the address field
for which there is an active address. The binary tree processing of an
eight bit octet requires eight memory accesses as well as unpacking the
bits from the octet. On the other hand, processing a 256 way tree takes
one memory access using the address octet as an index at each level. A 256
way tree requires 256 locations at the next level for every different
octet active (a valid value) at the current level. An address of six
octets with ten valid octet values in each octet position would require
256.times.10.sup.6 (256 million) locations, rapidly reaching an
unrealizable size on current computer equipment. With current realizable
computer memory sizes, pure tree structures do not appear to offer a
viable structure for real time, address independent directory access
method.
Hashing has often been used over the last several decades to create
directories where fast access is desired. One system uses a multi-level
hashing scheme as the file system directory structure. The Total database
system is based on hashed key access. Many language compilers use hash
tables to store symbols. Hash table schemes have good average access
costs--often a single access, but can degrade drastically when the table
becomes too full or the hashing function does not perform a good job of
evenly distributing the keys across t | | |
