Offline compression for limited sequence length radix tree

• US 9,355,133 B2
• Filed: 05/07/2014
• Issued: 05/31/2016
• Est. Priority Date: 05/07/2014
• Status: Active Grant

• Current Assignee: Red Hat Israel Ltd. (International Business Machines Corporation)
• Original Assignee: Red Hat Israel Ltd. (International Business Machines Corporation)
• Inventors: Tsirkin, Michael
• Primary Examiner(s): Woo, Isaac M
• Application Number:
  US14/272,444
• Publication Number:
  US 20150324401A1
• Time in Patent Office: 755 Days
• Field of Search: 707600-899
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/24561 Intermediate data storage techniques for performance improvement
• CPC Class Codes: G06F 16/9027 Trees

Abstract

Systems and methods are disclosed for compressing a radix tree. An example method of compressing a radix tree includes traversing a radix tree including a plurality of containers. The method also includes identifying, based on the traversing, a parent container having a single immediate child container. The parent container includes a first set of elements, and the child container includes a second set of elements. The method further includes determining whether a length of the first set of elements included in the parent container satisfies a threshold. The method also includes when the length of the first set of elements is determined to satisfy the threshold, combining the parent and child containers into a single container.

Claims

1. A method of compressing a radix tree including a plurality of containers, comprising:

traversing a radix tree including a plurality of containers;

identifying, based on the traversing, a parent container having a single immediate child container, the parent container including a first set of elements, and the child container including a second set of elements;

determining whether a length of the first set of elements included in the parent container satisfies a threshold; and

when the length of the first set of elements is determined to satisfy the threshold, combining the parent and child containers into a single container.

2. The method of claim 1, wherein the child container includes a single element.

3. The method of claim 1, wherein when the length of the first set of elements is less than the threshold, the length satisfies the threshold.

4. The method of claim 1, wherein the traversing includes traversing from a root node of the radix tree towards a leaf node of the radix tree.

5. The method of claim 4, further including:

after the combining, identifying, based on the traversing, a second parent container having a second immediate child container, the second parent container including a third set of elements and the second immediate child container including a fourth set of elements, the second parent container having a single child, and the first parent container having a shorter depth in the radix tree than the second parent container;

determining whether a length of the third set of elements satisfies threshold; and

when the length of the third set of elements is determined to satisfy the threshold, combining the second parent container and the second immediate child container.

6. The method of claim 1, wherein the combining includes appending the second set of elements as a suffix to the first set of elements included in the parent container, and wherein the single container is the parent container.

7. The method of claim 1, wherein the combining includes appending the first set of elements as a prefix to the second set of elements included in the child container, and wherein the single container is the child container.

8. The method of claim 1, wherein further including:

determining whether the single container has a second immediate child container, the single container having a single child and including a third set of elements;

determining whether a length of the third set of elements satisfies the threshold; and

when the length of the third set of elements is determined to satisfy the threshold, combining the single container and the second immediate child container into a second single container.

9. The method of claim 1, further including:

determining whether the child container is a leaf container; and

when the child container is determined to not be a leaf container;

identifying a set of children of the child container; and

replacing the child container with the single container as the parent of the set of children.

10. The method of claim 9, further including:

when the child container is determined to be a leaf container, marking the single container as a leaf container.

11. The method of claim 1, further including:

determining whether the parent container has a value, wherein the combining includes when the length of the first set of elements is determined to satisfy the threshold and when the parent container is determined to not have the value, combining the parent and child containers into the single container.

12. A system for compressing a radix tree, comprising:

a retriever that retrieves a radix tree stored in a memory;

a traverser that traverses the radix tree, and identifies, based on the traversal, a parent container having a single immediate child container, wherein the parent container includes a first set of elements, and the child container includes a second set of elements; and

a compressor that determines whether a length of the first set of elements included in the parent container satisfies a threshold, wherein when the length of the first set of elements is determined to satisfy the threshold, the compressor combines the parent and child containers into a single container.

13. The system of claim 12, wherein the compressor reduces a depth of the radix tree.

14. The system of claim 12, wherein each container in the retrieved radix tree includes a single element.

15. The system of claim 12, wherein a container is a node or an edge in the radix tree.

16. The system of claim 12, wherein when the length of the first set of elements is less than the threshold, the length satisfies the threshold.

17. The system of claim 12, wherein the traverser traverses from a root node of the radix tree towards a leaf node of the radix tree.

18. The system of claim 12, wherein the traverser traverses a parent of a container before traversing the container.

19. The system of claim 12, wherein the compressor determines whether the child container is a leaf container, wherein when the child container is determined to not be a leaf container, the compressor identifies a set of child containers of the child container and replaces the child container with the single container as the parent of the set of one or more children.

20. A machine-readable medium comprising a plurality of machine-readable instructions that when executed by one or more processors is adapted to cause the one or more processors to perform a method comprising:

traversing a radix tree including a plurality of containers;

identifying, based on the traversing, a parent container having a single immediate child container, the parent container including a first set of elements, and the child container including a second set of elements;

determining whether a length of the first set of elements included in the parent container satisfies a threshold; and

when the length of the first set of elements is determined to satisfy the threshold, combining the parent and child containers into a single container.