Invention Grant
- Patent Title: Offline radix tree compression with key sequence skip
- Patent Title (中): 使用键序列跳过的离线基数树压缩
-
Application No.: US14272441Application Date: 2014-05-07
-
Publication No.: US09361404B2Publication Date: 2016-06-07
- Inventor: Michael Tsirkin
- Applicant: Red Hat Israel, Ltd.
- Applicant Address: IL Ra'anana
- Assignee: Red Hat Israel, Ltd.
- Current Assignee: Red Hat Israel, Ltd.
- Current Assignee Address: IL Ra'anana
- Agency: Haynes and Boone, LLP
- Main IPC: G06F17/30
- IPC: G06F17/30

Abstract:
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.
Public/Granted literature
- US20150324484A1 OFFLINE RADIX TREE COMPRESSION WITH KEY SEQUENCE SKIP Public/Granted day:2015-11-12
Information query