# US 2012/0254496 A1 · Method, system and computer program product for storing a decision tree

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0254496 A1
- Document ID: US20120254496A1
- Status: Published application
- Kind: A1
- Application number: 13/439,013
- Filed: 2012-04-04
- Published: 2012-10-04
- Earliest claimed: 2011-04-04
- Assignees: Texas Instruments Incorporated
- Inventors: Goksel Dedeoglu
- Web page: https://patentgrep.com/patent/US20120254496A1

## CPC

- G06F 16/2246: {Trees, e.g. B+trees}
- G06F 16/322: {Trees}
- G06F 16/9027: {Trees}
- G06F 12/0207: {with multidimensional access, e.g. row/column, matrix}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

At least first nodes and second nodes of a decision tree are stored within a memory of an information handling system. The first nodes include a first parent node and first remaining nodes that descend from the first parent node. The second nodes include a second parent node and second remaining nodes that descend from the second parent node. The first nodes are grouped into a first packed node stored in first physically contiguous locations of the memory. The first nodes are sequenced in the first physically contiguous locations according to respective depth levels of the first nodes within the decision tree. The second nodes are grouped into a second packed node stored in second physically contiguous locations of the memory. The second nodes are sequenced in the second physically contiguous locations according to respective depth levels of the second nodes within the decision tree.

## Claims

### Claim 1

A method performed by an information handling system for storing a decision tree, the method comprising:
storing at least first nodes and second nodes of the decision tree within a memory of the information handling system, wherein the first nodes include a first parent node and first remaining nodes that descend from the first parent node, and wherein the second nodes include a second parent node and second remaining nodes that descend from the second parent node;
grouping the first nodes into a first packed node stored in first physically contiguous locations of the memory, wherein the first nodes are sequenced in the first physically contiguous locations according to respective depth levels of the first nodes within the decision tree; and
grouping the second nodes into a second packed node stored in second physically contiguous locations of the memory, wherein the second nodes are sequenced in the second physically contiguous locations according to respective depth levels of the second nodes within the decision tree.

### Claim 2 (depends on 1)

The method of claim 1, wherein the first nodes descend from the second parent node, and wherein the method includes: inserting the first packed node into the decision tree as one of the second remaining nodes, so that the second packed node includes the first packed node.

### Claim 3 (depends on 2)

The method of claim 2, wherein the second physically contiguous locations include the first physically contiguous locations, in which the first nodes remain sequenced according to respective depth levels of the first nodes within the decision tree.

### Claim 4 (depends on 1)

The method of claim 1, wherein grouping the second nodes includes: grouping the second nodes into the second packed node stored in the second physically contiguous locations, but only up to a particular number of the second physically contiguous locations.

### Claim 5 (depends on 4)

The method of claim 4, wherein the memory is a system memory, and wherein the particular number is within a storage capacity of a cache memory of a processor device.

### Claim 6 (depends on 4)

The method of claim 4, wherein the memory is a system memory, and wherein the particular number is within a storage capacity of a direct memory access (“DMA”) memory of a processor device.

### Claim 7 (depends on 1)

The method of claim 1, wherein the first nodes are sequenced in the first physically contiguous locations in a descending order of respective depth levels of the first nodes within the decision tree.

### Claim 8 (depends on 1)

The method of claim 1, wherein the second physically contiguous locations are located within a same page of the memory.

### Claim 9 (depends on 1)

The method of claim 1, wherein the first physically contiguous locations are located within a same line of the memory.

### Claim 10 (depends on 1)

The method of claim 1, wherein the first packed node has a first set of local addresses for linking the first parent node through first pointers to the first remaining nodes, and wherein the second packed node has a second set of local addresses for linking the second parent node through second pointers to the second remaining nodes.

### Claim 11

A system for storing a decision tree, the system comprising:
at least one device for: storing at least first nodes and second nodes of the decision tree within a memory, wherein the first nodes include a first parent node and first remaining nodes that descend from the first parent node, and wherein the second nodes include a second parent node and second remaining nodes that descend from the second parent node; grouping the first nodes into a first packed node stored in first physically contiguous locations of the memory, wherein the first nodes are sequenced in the first physically contiguous locations according to respective depth levels of the first nodes within the decision tree; and grouping the second nodes into a second packed node stored in second physically contiguous locations of the memory, wherein the second nodes are sequenced in the second physically contiguous locations according to respective depth levels of the second nodes within the decision tree.

### Claim 12 (depends on 11)

The system of claim 11, wherein the first nodes descend from the second parent node, and wherein the device is for: inserting the first packed node into the decision tree as one of the second remaining nodes, so that the second packed node includes the first packed node.

### Claim 13 (depends on 12)

The system of claim 12, wherein the second physically contiguous locations include the first physically contiguous locations, in which the first nodes remain sequenced according to respective depth levels of the first nodes within the decision tree.

### Claim 14 (depends on 11)

The system of claim 11, wherein grouping the second nodes includes: grouping the second nodes into the second packed node stored in the second physically contiguous locations, but only up to a particular number of the second physically contiguous locations.

### Claim 15 (depends on 14)

The system of claim 14, wherein the memory is a system memory, and wherein the particular number is within a storage capacity of a cache memory of a processor device.

### Claim 16 (depends on 14)

The system of claim 14, wherein the memory is a system memory, and wherein the particular number is within a storage capacity of a direct memory access (“DMA”) memory of a processor device.

### Claim 17 (depends on 11)

The system of claim 11, wherein the first nodes are sequenced in the first physically contiguous locations in a descending order of respective depth levels of the first nodes within the decision tree.

### Claim 18 (depends on 11)

The system of claim 11, wherein the second physically contiguous locations are located within a same page of the memory.

### Claim 19 (depends on 11)

The system of claim 11, wherein the first physically contiguous locations are located within a same line of the memory.

### Claim 20 (depends on 11)

The system of claim 11, wherein the first packed node has a first set of local addresses for linking the first parent node through first pointers to the first remaining nodes, and wherein the second packed node has a second set of local addresses for linking the second parent node through second pointers to the second remaining nodes.

### Claim 21

A computer program product for storing a decision tree, the computer program product comprising:
a tangible computer-readable storage medium; and
a computer-readable program stored on the tangible computer-readable storage medium, wherein the computer-readable program is processable by an information handling system for causing the information handling system to perform operations including: storing at least first nodes and second nodes of the decision tree within a memory of the information handling system, wherein the first nodes include a first parent node and first remaining nodes that descend from the first parent node, and wherein the second nodes include a second parent node and second remaining nodes that descend from the second parent node; grouping the first nodes into a first packed node stored in first physically contiguous locations of the memory, wherein the first nodes are sequenced in the first physically contiguous locations according to respective depth levels of the first nodes within the decision tree; and grouping the second nodes into a second packed node stored in second physically contiguous locations of the memory, wherein the second nodes are sequenced in the second physically contiguous locations according to respective depth levels of the second nodes within the decision tree.

### Claim 22 (depends on 21)

The computer program product of claim 21, wherein the first nodes descend from the second parent node, and wherein the operations include: inserting the first packed node into the decision tree as one of the second remaining nodes, so that the second packed node includes the first packed node.

### Claim 23 (depends on 22)

The computer program product of claim 22, wherein the second physically contiguous locations include the first physically contiguous locations, in which the first nodes remain sequenced according to respective depth levels of the first nodes within the decision tree.

### Claim 24 (depends on 21)

The computer program product of claim 21, wherein grouping the second nodes includes: grouping the second nodes into the second packed node stored in the second physically contiguous locations, but only up to a particular number of the second physically contiguous locations.

### Claim 25 (depends on 24)

The computer program product of claim 24, wherein the memory is a system memory, and wherein the particular number is within a storage capacity of a cache memory of a processor device.

### Claim 26 (depends on 24)

The computer program product of claim 24, wherein the memory is a system memory, and wherein the particular number is within a storage capacity of a direct memory access (“DMA”) memory of a processor device.

### Claim 27 (depends on 21)

The computer program product of claim 21, wherein the first nodes are sequenced in the first physically contiguous locations in a descending order of respective depth levels of the first nodes within the decision tree.

### Claim 28 (depends on 21)

The computer program product of claim 21, wherein the second physically contiguous locations are located within a same page of the memory.

### Claim 29 (depends on 21)

The computer program product of claim 21, wherein the first physically contiguous locations are located within a same line of the memory.

### Claim 30 (depends on 21)

The computer program product of claim 21, wherein the first packed node has a first set of local addresses for linking the first parent node through first pointers to the first remaining nodes, and wherein the second packed node has a second set of local addresses for linking the second parent node through second pointers to the second remaining nodes.
