Memory based on a digital trie structure

Details Memory based on a digital trie structure Memory based on a digital trie structure

2001-11-29

2004-01-06

Robinson, Greta (Department: 2177)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000

Reexamination Certificate

active

06675171

ABSTRACT:

FIELD OF THE INVENTION
The present invention generally relates to implementation of a memory. More specifically, the invention is intended to be used in connection with memories which are based on a digital trie structure and in which width-compressed nodes are used. The solution is mainly intended for central memory databases and is suited for both conventional overwriting memories and functional memories. The former denotes a memory in which updates are made directly on the existing data and the latter, on the other hand, a memory in which the path from the root of the structure to the point of addition is first copied, and the addition is thereafter made to the copied data (the addition is not made directly to the existing data). The former updating procedure is also called by the term “update-in-place” and the latter by the term “copy-on-write”.
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 trie structures can be implemented in two types: bucket tries, and tries having no buckets.
A bucket digital trie structure is a tree-shaped structure composed of two types of nodes: buckets and trie nodes. A bucket is a data structure that can accommodate a number of data units or a number of pointers to data units or a number of search key/data unit pairs or a number of search key/pointer pairs. A maximum size greater than one has been defined for said number. However, a bucket can contain a smaller number than said maximum number of data units, pointers, or key/pointer pairs, in which case the bucket is not full. 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 table contained in the trie node, the index indicating a given element in the table. 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 a leaf node containing only one element that can be a data unit, a pointer to a data unit, a search key/data unit pair or a search key/pointer pair corresponds to a bucket. In the present context, the nodes above the leaf nodes in the bucketless trie structure are called internal nodes; these correspond to trie nodes in a bucket structure (i.e., they comprise a similar table as trie nodes). In a bucketless digital trie structure, the nodes are thus 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, search key/data unit pairs or search key/pointer pairs can be accommodated in the buckets until a time when such a need arises.
FIG. 1
shows 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. Leaves are denoted with references A, B, C, D . . . H . . . M, N, O and P. Thus a leaf is a node that does not point to a lower level in the tree. Internal nodes are denoted with references IN
1
. . . IN
5
and elements in the internal node with reference NE in FIG.
1
.
In the exemplary case of
FIG. 1
, the search keys for the leaves 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 leaf 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 leaf A, the data relating to subscriber B in leaf B, etc.
The search key may also be multidimensional. In other words, the search key 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 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.
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 even, the node size may be increased to make the structure flatter (a flatter structure entails faster retrievals). On the other hand, with uneven 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 even key distribution and thereby smaller storage space occupancy. Dynamic changes of node size require the address computation to be implemented in such a way that in each node of the tree-shaped hierarchy constituted by the digital trie structure, a node-specific number of bits is selected from the bit string constituted by the search keys used. Dynamic reorganizing of the nodes naturally requires part of the processing capacity.
The choice between a fixed node size and a dynamically changing node size

Affiliated with

Also associated with

Rating

Memory based on a digital trie structure does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Memory based on a digital trie structure, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Memory based on a digital trie structure will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3231869