Compression of nodes in a trie structure

Details Compression of nodes in a trie structure Compression of nodes in a trie structure

2005-06-21

2005-06-21

Coby, Frantz (Department: 2161)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000

Reexamination Certificate

active

06910043

ABSTRACT:
The invention relates to a method for implementing a functional memory and to a memory arrangement. The memory is implemented as a directory structure comprising a tree-shaped hierarchy having nodes at several different hierarchy levels, wherein an individual node can be (i) a trie node associated with a logical table wherein an individual element may contain a pointer pointing to a lower node in the hierarchy, or (ii) a bucket containing at least one element so that the type of an individual element in the bucket is selected from a group including of e.g. a data unit or a pointer to a stored data unit. To optimize the performance of the functional trie structure, the trie nodes are implemented as quad nodes of four elements, and in at least part of the directory structure groups of successive quad nodes are replaced by compressed nodes in such a way that (a) an individual group comprising a given quad node and its child nodes is replaced by a node whose logical table has 16 elements, and (b) a compressed node known per se is formed from said node of 16 elements by physically storing in the node only non-nil pointers and in addition a bit pattern on the basis of which the physical storage location in the node, corresponding to the search word, can be determined. The invention also relates to a structure in which no buckets are used.

REFERENCES:
patent: 5276868 (1994-01-01), Poole
patent: 5592667 (1997-01-01), Bugajski
patent: 5684976 (1997-11-01), Soheili-Arasi et al.
patent: 5721899 (1998-02-01), Namba
patent: 5787430 (1998-07-01), Doeringer et al.
patent: 5829004 (1998-10-01), Au
patent: 5848416 (1998-12-01), Tikkanen
patent: WO 95/34155 (1995-12-01), None
patent: WO 98/41932 (1998-09-01), None
International Search Report for PCT/FI99/00717.

Affiliated with

Also associated with

Rating

Compression of nodes in a 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 Compression of nodes in a trie structure, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compression of nodes in a trie structure will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3520847