Data processing: database and file management or data structures – Database design – Data structure types
Patent
1999-09-03
2000-09-05
Black, Thomas G.
Data processing: database and file management or data structures
Database design
Data structure types
707101, 707102, G06F 1730
Patent
active
061157163
ABSTRACT:
The invention relates to a method for implementing a memory. The memory is implemented as a directory structure comprising a tree-shaped hierarchy having nodes at several different levels, wherein an individual node can be (i) a trie node comprising an array wherein an individual element may contain the address of a lower node in the tree-shaped hierarchy and wherein an individual element may also be empty, 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 a data unit, a pointer to a stored data unit, a pointer to another directory structure and another directory structure. To minimize storage space requirement, the arrays in the trie nodes are implemented as quad nodes having a fixed size of four elements, and in at least part of the directory structure sets of successive quad nodes are replaced with compressed nodes in such a way that an individual set made up by successive quad nodes, from each of which there is only one address to a quad node at a lower level, is replaced with a compressed node (CN) storing an address to the quad node that the lowest node in the set to be replaced points to, information on the value of the search word by means of which said address is found, and information on the total number of bits from which search words are formed in the set to be replaced. The invention also relates to a structure in which buckets are not employed.
REFERENCES:
patent: Re35881 (1998-08-01), Barrett et al.
patent: 5247658 (1993-09-01), Barrett et al.
patent: 5276868 (1994-01-01), Poole
patent: 5319777 (1994-06-01), Perez
patent: 5392427 (1995-02-01), Barrett et al.
patent: 5423034 (1995-06-01), Cohen-Levy et al.
patent: 5848416 (1998-08-01), Tikkanen
patent: 5960173 (1999-09-01), Tang et al.
patent: 6011897 (2000-01-01), Koyama et al.
K-tree container data structures: fast subscripting, slicing, and concatenation of sequences.; Rodney Bates; Dr. Dobb's Journal; Sep.1994; vol. 19, No. 10, p. 26(5).
Fast IP routing with LC-Tries; achieving gbit/see speed in software, (Internet/Web/Online Service Information); Stefan Nilsson et al.; Dr. Dobb's Journal; Aug. 1998; vol. 23, No. 8, p. 70 (5).
Patent Abstracts of Japan, Abstract of JP 8-194719 (Fujitsu Ltd.); Jul. 30, 1996.
"Approximate Average Storage Utilization of Bucket Methods with Arbitrary Fanout" Ang, et al. Nordic Journal of Computing Mar. 2, 1996, pp. 280-291.
K-tree container data structures: that subscripting, slicing, and concentration of sequences: Rodney Bates: Dr. Dobb' Journal: Sep. 1994: vol. 19, No. 10, p. 26(5).
Fast IP routing with LC-Tries; schieving gbit/see speed in software, (Internet/Web/Online Service Information), Stefan Nilsson et al., Dr.Dobb'Journal: Aug. 1998; vol. 23, No. 8, p. 70 (5).
Patents Abstracts of Japan, Abstract of JP 8-194719 (Fujitsu Ltd.); Jul 30, 1996.
Iivonen Jukka-Pekka
Tikkanen Matti
Black Thomas G.
Coby Frantz
Nokia Telecommunications Oy
LandOfFree
Method for implementing an associative memory based on a digital 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 digital, 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 digital will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2222881