Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-09-03
2002-12-24
Popovici, Dov (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06499032
ABSTRACT:
FIELD OF THE INVENTION
The present invention generally relates to implementation of an associative memory, particularly to implementation of an associative memory based on a digital trie structure. The solution in accordance with the invention is intended for use primarily in connection with central memory databases. Suitable applications particularly include databases in which a large number of retrievals are made but in which there are only a small number of insertions or deletions compared to retrievals. Such applications include home location registers (HLR) in mobile communications networks and geographical information systems (GIS) used in map applications.
BACKGROUND OF THE INVENTION
The prior art unidimensional directory structure termed digital trie (the word “trie” is derived from the English word “retrieval”) is the underlying basis of the principle of the present invention. Digital tries can be implemented in two types: bucket tries, and tries having no buckets.
A digital bucket trie structure is a tree-shaped structure composed of two types of nodes: buckets and trie nodes. A bucket is a data structure containing a number of data units or a number of pointers to data units or a number of search key/pointer pairs (the number may include only one data unit, one pointer or one key/pointer pair). A trie node, on the other hand, is an array guiding the retrieval, having a size of two by the power of k (2
k
) elements. If an element in a trie node is in use, it refers either to a trie node at the next level in the directory tree or to a bucket. In other cases, the element is free (empty).
Search in the database proceeds by examining the search key (which in the case of a subscriber database in a mobile telephone network or a telephone exchange, for instance, is typically the binary numeral corresponding to the telephone number of the subscriber) k bits at a time. The bits to be searched are selected in such a way that at the root level of the structure (in the first trie node), k leftmost bits are searched; at the second level of the structure, k bits next to the leftmost bits are searched, etc. The bits to be searched are interpreted as an unsigned binary integer that is employed directly to index the element array contained in the trie node, the index indicating a given element in the array. If the element indicated by the index is free, the search will terminate as unsuccessful. If the element refers to a trie node at the next level, k next bits extracted from the search key are searched at that level in the manner described above. As a result of comparison, the routine branches off in the trie node either to a trie node at the next level or to a bucket. If the element refers to a bucket containing a key, the key stored therein is compared with the search key. The entire search key is thus compared only after the search has encountered a bucket. Where the keys are equal, the search is successful, and the desired data unit is obtained at the storage address indicated by the pointer of the bucket. Where the keys differ, the search terminates as unsuccessful.
A bucketless trie structure has no buckets, but reference to a data unit is effected from a trie node at the lowest level of a tree-shaped hierarchy, called a leaf node. Unlike buckets, the leaf nodes in a bucketless structure cannot contain data units but only pointers to data units. Also a bucket structure has leaf nodes, and hence trie nodes containing at least one pointer to a bucket (bucket structure) or to a data unit (bucketless structure) are leaf nodes. The other nodes in the trie are internal nodes. Trie nodes may thus be either internal nodes or leaf nodes. By means of buckets, the need for reorganizing the directory structure can be postponed, as a large number of pointers/data units can be accommodated in the buckets until a time when the need for reorganization arises.
The solution in accordance with the invention can be applied to a bucket structure as well as a bucketless structure. In the following, bucket structures will nevertheless be used as examples.
FIG. 1
illustrates an example of a digital trie structure in which the key has a length of 4 bits and k=2, and thus each trie node has 2
2
=4 elements, and two bits extracted from the key are searched at each level. Buckets are denoted with references A, B, C, D . . . H . . . M, N, O and P. Thus a bucket is a node that does not point to a lower level in the tree. Trie nodes are denoted with references IN
1
. . . IN
5
and elements in the trie node with reference NE in FIG.
1
.
In the exemplary case of
FIG. 1
, the search keys for the buckets shown are as follows: A=0000, B=0001, C=0010, . . . , H=0111, . . . and P=1111. In this case, a pointer is stored in each bucket to that storage location in the database SD at which the actual data, e.g. the telephone number of the pertinent subscriber and other information relating to that subscriber, is to be found. The actual subscriber data may be stored in the database for instance as a sequential file of the type shown in the figure. The search is performed on the basis of the search key of record H, for example, by first extracting from the search key the two leftmost bits (
01
) and interpreting them, which delivers the second element of node IN
1
, containing a pointer to node IN
3
at the next level. At this level, the two next bits (
11
) are extracted from the search key, thus yielding the fourth element of that node, pointing to record H.
Instead of a pointer, a bucket may contain (besides a search key) an actual data file (also called by the more generic term data unit). Thus for example the data relating to subscriber A (
FIG. 1
) may be located in bucket A, the data relating to subscriber B in bucket B, etc. Thus in the first embodiment of an associative memory, a key-pointer pair is stored in the bucket, and in the second embodiment a key and actual data are stored, even though the key is not indispensable.
The search key may also be multidimensional. In other words, it may comprise a number of attributes (for example the family name and one or more forenames of a subscriber). Such a multidimensional trie structure is disclosed in international application No. PCT/FI95/00319 (published under number WO 95/34155). In said structure, address computation is performed in such a way that a given predetermined number of bits at a time is selected from each dimension independently of the other dimensions. Hence, a fixed limit independent of the other dimensions is set for each dimension in any individual node of the trie structure, by predetermining the number of search key bits to be searched in each dimension. With such a structure, the need for memory circuit requirement can be curbed when the distribution of the values of the search keys is known in advance, in which case the structure can be implemented in a static form.
Often, however, the situation is such that the distribution of the search key values is not known in advance. In such a case, the structure disclosed in the above patent application will not give an optimum result in view of storage space occupancy, as the number of bits to be searched in each dimension is a predetermined constant.
If the possibility of reorganizing the structure in accordance with the current key distribution to be optimal in terms of efficiency and storage space occupancy is desired, the size of the nodes must vary dynamically as the key distribution changes. When the key distribution is uniform, the node size may be increased to make the structure flatter. On the other hand, with non-uniform key distributions in connection with which storage space occupancy will present a problem in memory structures employing dynamic node size, the node size can be maintained small, which will enable locally a more uniform key distribution and thereby smaller storage space occupancy.
With dynamic changing of node size, however, a problem will be presented by the fact how the structure of the memory is to be maintained to o
Iivonen Jukka-Pekka
Tikkanen Matti
Altera Law Group LLC
Mofiz Apu M
Nokia Telecommunications Oy
Popovici Dov
LandOfFree
Method for implementing an associative memory based on a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for implementing an associative memory based on a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for implementing an associative memory based on a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2920879