发明名称 |
OFFLINE RADIX TREE COMPRESSION WITH KEY SEQUENCE SKIP |
摘要 |
Systems and methods are disclosed for compressing a radix tree. An example method of compressing a radix tree including a plurality of containers includes traversing a radix tree including a plurality of containers. The method also includes identifying, based on the traversing, a parent container that represents a sequence of elements and has a single immediate child container. The parent container includes a prefix of the sequence of elements that is represented by the parent container, and the immediate child container includes a single element. The method further includes determining whether a length of the sequence of elements that is represented by the parent container satisfies a container threshold. The method also includes when the length is determined to satisfy the container threshold, selecting one of the parent container and immediate child container, incrementing a length of the selected container, and removing the non-selected container from the radix tree. |
申请公布号 |
US2015324484(A1) |
申请公布日期 |
2015.11.12 |
申请号 |
US201414272441 |
申请日期 |
2014.05.07 |
申请人 |
Red Hat Israel, Ltd. |
发明人 |
Tsirkin Michael |
分类号 |
G06F17/30 |
主分类号 |
G06F17/30 |
代理机构 |
|
代理人 |
|
主权项 |
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 that represents a sequence of elements and has a single immediate child container, the parent container including a prefix of the sequence of elements that is represented by the parent container, and the immediate child container including a single element; determining whether a length of the sequence of elements that is represented by the parent container satisfies a container threshold; and when the length is determined to satisfy the container threshold:
selecting one of the parent container and immediate child container;incrementing a length of the selected container; andremoving the non-selected container from the radix tree. |
地址 |
Ra'anana IL |