Compression of nodes in a trie structure

• US 6,910,043 B2
• Filed: 03/26/2001
• Issued: 06/21/2005
• Est. Priority Date: 09/29/1998
• Status: Expired due to Fees

• Current Assignee: Nokia Networks (Nokia Corporation)
• Original Assignee: Nokia Corporation
• Inventors: Tikkanen, Matti, Iivonen, Jukka-Pekka
• Primary Examiner(s): Coby, Frantz
• Assistant Examiner(s): NGUYEN, MERILYN P
• Application Number:
  US09/819,022
• Publication Number:
  US 20010042186A1
• Time in Patent Office: 1,548 Days
• Field of Search: 707 1- 10, 707/100, 707/102, 707/202, 707/205, 707/101
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99953 Recoverability

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.

Claims

1. A method for implementing a functional memory, wherein memory data is stored as data units for each of which a dedicated storage space is assigned in the memory, the method comprising:

implementing a memory as a directory structure comprising a tree-shaped hierarchy having nodes at several different levels, wherein an individual node includes (i) a trie node associated with a logical table wherein an individual element contains a pointer pointing to a lower node in the tree-shaped hierarchy, a number of elements in the logical table corresponding to a power of two, or (ii) a bucket containing at least one element wherein a type of said 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 said another directory structure;

performing address computation in the directory structure by

(a) selecting in the node at an uppermost level of the tree-shaped hierarchy a given number of bits from a bit string formed by employed search keys, forming from the given number of bits a search word for seeking an address of a next node in the individual node, and proceeding to said next node,

(b) selecting a predetermined number of bits from unselected bits in the bit string formed by the employed search keys and forming from the predetermined number of bits another search word for seeking another address of a further new node at a lower level from the logical table of the individual node that has been accessed,

repeating step (b) until an element containing a nil pointer is encountered or until the address of the new node at said lower level is the address of said bucket,

wherein the nodes to which a given node contains pointers are child nodes of said given node and the nodes to which the child nodes contain pointers are grandchild nodes of said given node; and

implementing trie nodes as quad nodes of four elements, and replacing in at least part of the directory structure groups of successive nodes by compressed nodes by

(a) replacing an individual group comprising a given quad node and its child nodes by a node whose logical table has 16 elements, and

(b) forming a compressed node known per se from said node of 16 elements by physically storing in the compressed node non-nil pointers and a bit pattern on a basis of which a physical storage location in the compressed node, corresponding to the search word, is determined.

2. A method as claimed in claim 1, further comprising performing replacement in the directory structure on all groups in which the quad node has two child nodes.

3. A method as claimed in claim 1, further comprising performing replacement in the directory structure on all groups in which the quad node has up to eight grandchild nodes.

4. A method as claimed in claim 2, further comprising setting an upper limit for the number of pointers in the compressed node, wherein when said limit is exceeded, the compressed node is decompressed to another quad node and child nodes.

5. A method as claimed in claim 4, further comprising evolving eight pointers said upper limit.

6. A method as claimed in claim 4, further comprising employing ten pointers as said upper limit.

7. A method as claimed in claim 2, further comprising performing compression on at least some of the quad nodes in the structure so that non-nil pointers are physically stored in the node and a bit pattern on a basis of which the physical storage location in the node, corresponding to the search word, is determined.

8. A method as claimed in claim 1, further comprising storing the non-nil pointers in the compressed node in a same order that the non-nil pointers have in said logical table.

9. A method as claimed in claim 8, wherein the bit pattern has one bit for each element in the table, said one bit indicating whether the corresponding element contains a nil pointer or a non-nil pointer.

10. A method as claimed in claim 8, further comprising reserving space for the bit pattern in said trie nodes of the directory structure.

11. A method as claimed in claim 8, further comprising reserving space for the bit pattern in the compressed nodes.

12. A method as claimed in claim 1, further comprising determining said individual element is empty, wherein a content of the individual element corresponds to said nil pointer.

13. A method for implementing a functional memory, wherein memory data is stored as data units for each of which a dedicated storage space is assigned in the memory, the method comprising:

implementing the memory as a directory structure comprising a tree-shaped hierarchy having nodes at several different hierarchy levels, wherein an individual node includes (i) an internal node associated with a logical table wherein an individual element contains a pointer pointing to a lower node in the tree-shaped hierarchy and a number of elements in the logical table corresponding to a power of two, or (ii) a leaf containing an element of a type is selected from a group including a pointer to a stored data unit, a data unit, and a pointer to a node in another directory structure;

performing address computation performed in the directory structure by

(a) selecting in the individual node at an uppermost level of the tree-shaped hierarchy a given number of bits from a bit string formed by the employed search keys, forming from the given number of bits a search word to seek an address of a next node in the individual node, and proceeding to said next node,

(b) selecting another given number of bits from the-unselected bits in the bit string formed by the employed search keys, and forming from the another given number of bits another search word to seek another address of a further new node at a lower level from the logical table of the individual node that has been accessed, and

repeating step (b) until an empty element is encountered or until the address of the new node at a lower level is the address of the leaf,

wherein the nodes to which a given node includes pointers are child nodes of said given node and the nodes to which the child nodes contain pointers are grandchild nodes of said given node; and

implementing internal nodes as quad nodes having four elements, and replacing, in at least part of the directory structures groups of successive nodes by compressed nodes by

replacing an individual group comprising a given quad node and its child nodes by a node whose node logical table has 16 elements, and

forming a compressed node known per se from said node of 16 elements by physically storing in the compressed node non-nil pointers and a bit pattern on a basis of which a physical storage location in the compressed node, corresponding to the search word, is determined.

14. A method as claimed in claim 13, further comprising performing replacement in the directory structure on all groups in which the quad node has two child nodes.

15. A method as claimed in claim 13, further comprising performing replacement in the directory structure on all groups in which the quad node has up to eight grandchild nodes.

16. A method as claimed in claim 14, further comprising setting an upper limit for a number of pointers in the compressed node, wherein

when said upper limit is exceeded, the compressed node is decompressed to a quad node and child nodes.

17. A method as claimed in claim 16, further comprising employing eight pointers as said upper limit.

18. A method as claimed in claim 16, further comprising employing ten pointers as said upper limit.

19. A method as claimed in claim 14, further comprising performing compression on at least some of the quad nodes in the structure so that the non-nil pointers are physically stored in the compressed node and a bit pattern on a basis of which the physical storage location in the node, corresponding to the search word, is determined.

20. A method as claimed in claim 13, further comprising storing the non-nil pointers in the compressed node in a same order as in said node logical table.

21. A method as claimed in claim 20, wherein the bit pattern has one bit for each element in the node logical table, each bit indicating whether the each element contains a nil pointer or a non-nil pointer.

22. A method as claimed in claim 20, further comprising reserving space for the bit pattern in all trie nodes of the directory structure.

23. A method as claimed in claim 20, further comprising reserving space for the bit pattern in the compressed nodes.

24. A method as claimed in claim 13, further comprising determining said individual element is empty, wherein a content of the individual node corresponds to said nil pointer.

25. A memory arrangement for storing data units, said memory arrangement comprising:

a directory structure wherein progress is made by using search words formed from a bit string constituted by search keys employed in each case, said directory structure comprising a tree-shaped hierarchy having nodes at several different hierarchy levels,

wherein an individual node is (i) a trie node associated with a logical table wherein an individual element contains a pointer pointing to a lower node in the tree-shaped hierarchy, a number of elements in the logical table corresponding to a power of two, or (ii) a bucket containing at least one element so that a 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 a node in another directory structure, and said another directory structure,

wherein some of the trie nodes are quad nodes having a node logical table that includes four elements and some of the trie nodes are nodes having a node logical table that includes 16 elements and wherein non-nil pointers are physically stored in addition to a bit pattern on a basis of which a physical storage location in the node, corresponding to the search word, is determined.

26. A memory arrangement as claimed in claim 25, wherein at least some of said quad nodes store physically those pointers that are non-nil pointers and a bit pattern on the basis of which the physical storage location in the node, corresponding to the search word, is determined.

27. A memory arrangement as claimed in claim 25, wherein said individual element is empty and a content of said individual element corresponds to a nil pointer.

28. A memory arrangement for storing data units, said memory arrangement comprising:

a directory structure wherein progress is made by using search words formed from a bit string constituted by search keys employed in each case, said directory structure comprising a tree-shaped hierarchy having nodes at several different hierarchy levels, wherein an individual node is (i) an internal node associated with a logical table wherein an individual element contains a pointer pointing to a lower node in the tree-shaped hierarchy, a the number of elements in the logical table corresponding to a power of two, or (ii) a leaf containing at least one element of a type selected from a group including a pointer to a stored data unit and a pointer to a node in another directory structure,

wherein some of the trie nodes are quad nodes having a node logical table including four elements and some of the trie nodes are nodes having a node logical table that includes 16 elements and wherein non-nil pointers are physically stored in addition to a bit pattern on a basis of which a physical storage location in the node, corresponding to the search word, is determined.

29. A method-memory arrangement as claimed in claim 28, wherein at least some of said quad nodes store physically those pointers that are non-nil pointers and a bit pattern on the basis of which the physical storage location in the node, corresponding to the search word, is determined.

30. A memory arrangement as claimed in claim 28, wherein said individual element is empty and a content of said individual element corresponds to nil pointer.