# US 2012/0254576 A1 · Method, system and computer program product for reading 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/0254576 A1
- Document ID: US20120254576A1
- Status: Published application
- Kind: A1
- Application number: 13/439,129
- 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/US20120254576A1

## 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

In response to a query of a decision tree, a first packed node of the decision tree is copied from a system memory into a direct memory access (“DMA”) memory. In response to copying the first packed node from the system memory into the DMA memory, copying is initiated of a second packed node of the decision tree from the system memory into the DMA memory, up to a limit of then-currently available space within the DMA memory. Concurrently with copying the second packed node from the system memory into the DMA memory, the first packed node is evaluated in the DMA memory. In response to evaluating the first packed node, the second packed node is evaluated in the DMA memory without waiting for additional copying of the second packed node from the system memory into the DMA memory.

## Claims

### Claim 1

A method performed by an information handling system for reading a decision tree, the method comprising:
in response to a query of the decision tree, copying a first packed node of the decision tree from a system memory into a direct memory access (“DMA”) memory, wherein the first packed node includes a first set of nodes;
in response to copying the first packed node from the system memory into the DMA memory, initiating copying of a second packed node of the decision tree from the system memory into the DMA memory, up to a limit of then-currently available space within the DMA memory, wherein the second packed node includes a second set of nodes that descend from the first packed node;
concurrently with copying the second packed node from the system memory into the DMA memory, evaluating the first packed node in the DMA memory; and
in response to evaluating the first packed node, evaluating the second packed node in the DMA memory without waiting for additional copying of the second packed node from the system memory into the DMA memory.

### Claim 2 (depends on 1)

The method of claim 1, wherein the first set of nodes include a root node of the decision tree and remaining nodes that descend from the root node.

### Claim 3 (depends on 2)

The method of claim 2, wherein the remaining nodes include a third packed node, and wherein the third packed node includes a third set of nodes.

### Claim 4 (depends on 1)

The method of claim 1, wherein the first set of nodes include a first parent node and first remaining nodes that descend from the first parent node, wherein the second set of nodes include a second parent node and second remaining nodes that descend from the second parent node, 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 5 (depends on 1)

The method of claim 1, wherein the first set of nodes are: stored in physically contiguous locations of the system memory; and sequenced in the physically contiguous locations according to respective depth levels of the first set of nodes within the decision tree.

### Claim 6 (depends on 5)

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

### Claim 7 (depends on 5)

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

### Claim 8 (depends on 5)

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

### Claim 9 (depends on 1)

The method of claim 1, wherein the method includes: in response to copying the second packed node from the system memory into the DMA memory, initiating copying of a third packed node of the decision tree from the system memory into the DMA memory, up to the limit of then-currently available space within the DMA memory, wherein the third packed node includes a third set of nodes that descend from the second packed node.

### Claim 10 (depends on 9)

The method of claim 9, wherein the method includes: concurrently with copying the third packed node from the system memory into the DMA memory, evaluating the second packed node in the DMA memory; and, in response to evaluating the second packed node, copying a fourth packed node of the decision tree from the system memory into the DMA memory, and evaluating the fourth packed node in the DMA memory after waiting for the copying of the fourth packed node.

### Claim 11

A system for reading a decision tree, the system comprising:
at least one device for: in response to a query of the decision tree, copying a first packed node of the decision tree from a system memory into a direct memory access (“DMA”) memory, wherein the first packed node includes a first set of nodes; in response to copying the first packed node from the system memory into the DMA memory, initiating copying of a second packed node of the decision tree from the system memory into the DMA memory, up to a limit of then-currently available space within the DMA memory, wherein the second packed node includes a second set of nodes that descend from the first packed node; concurrently with copying the second packed node from the system memory into the DMA memory, evaluating the first packed node in the DMA memory; and, in response to evaluating the first packed node, evaluating the second packed node in the DMA memory without waiting for additional copying of the second packed node from the system memory into the DMA memory.

### Claim 12 (depends on 11)

The system of claim 11, wherein the first set of nodes include a root node of the decision tree and remaining nodes that descend from the root node.

### Claim 13 (depends on 12)

The system of claim 12, wherein the remaining nodes include a third packed node, and wherein the third packed node includes a third set of nodes.

### Claim 14 (depends on 11)

The system of claim 11, wherein the first set of nodes include a first parent node and first remaining nodes that descend from the first parent node, wherein the second set of nodes include a second parent node and second remaining nodes that descend from the second parent node, 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 15 (depends on 11)

The system of claim 11, wherein the first set of nodes are: stored in physically contiguous locations of the system memory; and sequenced in the physically contiguous locations according to respective depth levels of the first set of nodes within the decision tree.

### Claim 16 (depends on 15)

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

### Claim 17 (depends on 15)

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

### Claim 18 (depends on 15)

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

### Claim 19 (depends on 11)

The system of claim 11, wherein the device is for: in response to copying the second packed node from the system memory into the DMA memory, initiating copying of a third packed node of the decision tree from the system memory into the DMA memory, up to the limit of then-currently available space within the DMA memory, wherein the third packed node includes a third set of nodes that descend from the second packed node.

### Claim 20 (depends on 19)

The system of claim 19, wherein the device is for: concurrently with copying the third packed node from the system memory into the DMA memory, evaluating the second packed node in the DMA memory; and, in response to evaluating the second packed node, copying a fourth packed node of the decision tree from the system memory into the DMA memory, and evaluating the fourth packed node in the DMA memory after waiting for the copying of the fourth packed node.

### Claim 21

A computer program product for reading 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: in response to a query of the decision tree, copying a first packed node of the decision tree from a system memory into a direct memory access (“DMA”) memory, wherein the first packed node includes a first set of nodes; in response to copying the first packed node from the system memory into the DMA memory, initiating copying of a second packed node of the decision tree from the system memory into the DMA memory, up to a limit of then-currently available space within the DMA memory, wherein the second packed node includes a second set of nodes that descend from the first packed node; concurrently with copying the second packed node from the system memory into the DMA memory, evaluating the first packed node in the DMA memory; and, in response to evaluating the first packed node, evaluating the second packed node in the DMA memory without waiting for additional copying of the second packed node from the system memory into the DMA memory.

### Claim 22 (depends on 21)

The computer program product of claim 21, wherein the first set of nodes include a root node of the decision tree and remaining nodes that descend from the root node.

### Claim 23 (depends on 22)

The computer program product of claim 22, wherein the remaining nodes include a third packed node, and wherein the third packed node includes a third set of nodes.

### Claim 24 (depends on 21)

The computer program product of claim 21, wherein the first set of nodes include a first parent node and first remaining nodes that descend from the first parent node, wherein the second set of nodes include a second parent node and second remaining nodes that descend from the second parent node, 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 25 (depends on 21)

The computer program product of claim 21, wherein the first set of nodes are: stored in physically contiguous locations of the system memory; and sequenced in the physically contiguous locations according to respective depth levels of the first set of nodes within the decision tree.

### Claim 26 (depends on 25)

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

### Claim 27 (depends on 25)

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

### Claim 28 (depends on 25)

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

### Claim 29 (depends on 21)

The computer program product of claim 21, wherein the operations include: in response to copying the second packed node from the system memory into the DMA memory, initiating copying of a third packed node of the decision tree from the system memory into the DMA memory, up to the limit of then-currently available space within the DMA memory, wherein the third packed node includes a third set of nodes that descend from the second packed node.

### Claim 30 (depends on 29)

The computer program product of claim 29, wherein the operations include: concurrently with copying the third packed node from the system memory into the DMA memory, evaluating the second packed node in the DMA memory; and, in response to evaluating the second packed node, copying a fourth packed node of the decision tree from the system memory into the DMA memory, and evaluating the fourth packed node in the DMA memory after waiting for the copying of the fourth packed node.
