# US 11,308,063 B2 · Data structure to array conversion

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

- Number: US 11,308,063 B2
- Document ID: US11308063B2
- Status: Granted
- Kind: B2
- Application number: 16/730,910
- Filed: 2019-12-30
- Published: 2021-07-01
- Granted: 2022-04-19
- Earliest claimed: 2019-12-30
- Assignees: Yahoo Assets LLC
- Applicants: Oath Inc.
- Inventors: Attila Arpad Sahi; An Jiang; Raj Amrit; Dipankar Biswas
- Web page: https://patentgrep.com/patent/US11308063B2

## CPC

- G06F 16/2272: {Management thereof}
- G06F 16/2237: {Vectors, bitmaps or matrices}
- G06F 16/2246: {Trees, e.g. B+trees}
- G06F 16/258: {Data format conversion from or to a database}
- G06F 16/9027: {Trees}
- G06N 20/00: Machine learning
- G06N 5/01: Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

One or more computing devices, systems, and/or methods for converting a data structure into an array are provided herein. Nodes of a data structure, such as a tree structure, are recursively processed to convert the data structure into an array. When processing a numerical node that is a parent of a low child node and a high child node, the numerical node of the tree structure is inserted into a first array element. The low child node is inserted into a second array element next to the first array element. The high child node is inserted into a third array element next to the second array element. A reference to the high child node is stored in association with the numerical node.

## Claims

### Claim 1

A method, comprising:
executing, on a processor of a computing device, instructions that cause the computing device to perform operations, the operations comprising:
recursively processing nodes within a tree structure to convert the tree structure into an array, wherein for a node that is a parent of a low child node connected to the left of the node and a high child node connected to the right of the node:
inserting the node of the tree structure into a first array element;
inserting the low child node of the node into a second array element next to the first array element;
inserting the high child node of the node into a third array element next to the second array element, and
storing, in association with the node, a reference to the high child node that is within the third array element.

### Claim 2 (depends on 1)

The method of claim 1, wherein the recursively processing nodes comprises:
determining that a first low child node of a first node comprises a leaf low child node and that a first high child node of the first node comprises a numerical high child node;
inserting the first node into a target array element;
inserting the leaf low child node into a next array element;
setting a high child reference index to a value that is two greater than an index of the first node; and
inserting the numerical high child node into an array element subsequent the next array element.

### Claim 3 (depends on 1)

The method of claim 1, wherein the recursively processing nodes comprises:
determining that a first low child node of a first node comprises a leaf low child node and that a first high child node of the first node comprises a leaf high child node;
inserting the first node into a target array element;
inserting the leaf low child node into a next array element;
setting a high child reference index to a value that is two greater than an index of the first node; and
inserting the leaf high child node into an array element subsequent the next array element.

### Claim 4 (depends on 1)

The method of claim 1, wherein the recursively processing nodes comprises:
determining that a first low child node of a first node comprises a numerical low child node and that a first high child node of the first node comprises a numerical high child node;
inserting the first node into a target array element;
inserting the numerical low child node into a next array element;
determining a populated size of the array;
setting a high child reference index to a value corresponding to an end of the array identified using the populated size of the array; and
recursively processing the numerical high child node.

### Claim 5 (depends on 1)

The method of claim 1, wherein the recursively processing nodes comprises:
determining that a first low child node of a first node comprises a numerical low child node and that a first high child node of the first node comprises a leaf high child node;
inserting the first node into a target array element;
inserting the numerical low child node into a next array element;
determining a populated size of the array;
set a high child reference index to a value corresponding to an end of the array identified using the populated size of the array; and
processing the leaf high child node.

### Claim 6 (depends on 1)

The method of claim 1, wherein the tree structure represents a model used by machine learning functionality to output a prediction.

### Claim 7 (depends on 6)

The method of claim 6, wherein the prediction corresponds to predicted user behavior.

### Claim 8 (depends on 1)

The method of claim 1, comprising:
loading the array into memory for execution of a model represented by the tree structure.

### Claim 9 (depends on 1)

The method of claim 1, wherein the array comprises a node array, and wherein the method comprises:
serializing the node array into a byte array comprising a type identifier byte indicating whether a node has a numerical node type or a leaf node type.

### Claim 10 (depends on 9)

The method of claim 9, wherein the byte array comprises serialized internal data specifying split values of nodes.

### Claim 11 (depends on 9)

The method of claim 9, wherein the byte array comprises serialized internal data specifying a feature index.

### Claim 12 (depends on 9)

The method of claim 9, wherein the byte array comprises serialized internal data specifying an offset reference to the high child node having a numerical node type.

### Claim 13 (depends on 9)

The method of claim 9, wherein the byte array comprises serialized internal data specifying a double value for a high child node having a leaf node type.

### Claim 14

A computing device comprising:
a processor; and
memory comprising processor-executable instructions that when executed by the processor cause performance of operations, the operations comprising:
recursively processing nodes of a tree structure to generate an array, wherein for a node that is a parent of a low child node connected to the left of the node and a high child node connected to the right of the node:
inserting the node of the tree structure into a first array element;
inserting the low child node of the node into a next array element;
inserting the high child node of the node into an array element next to the next array element, and
storing, in association with the node, a reference to the high child node that is within the array element next to the next array element.

### Claim 15 (depends on 14)

The computing device of claim 14, wherein the reference comprises an index value in short integer format.

### Claim 16 (depends on 14)

The computing device of claim 14, wherein the operations comprise:
generating a lookup table comprising values occurring within models greater than a frequency threshold.

### Claim 17 (depends on 16)

The computing device of claim 16, wherein the operations comprise:
utilizing the lookup table to compress the array.

### Claim 18

A non-transitory machine readable medium having stored thereon processor-executable instructions that when executed cause performance of operations, the operations comprising:
recursively processing nodes of a tree structure to generate an array, wherein for a node that is a parent of a low child node connected to the left of the node and a high child node connected to the right of the node:
inserting the node of the tree structure into a first array element;
inserting the low child node of the node into a second array element;
inserting the high child node of the node into a third array element, and
storing, in association with the node, a reference to the high child node that is within the third array element.

### Claim 19 (depends on 18)

The non-transitory machine readable medium of claim 18, wherein the operations comprise:
clustering one or more nodes of the tree structure into a cluster for storage within the array as a single block representing the one or more nodes.

### Claim 20 (depends on 18)

The non-transitory machine readable medium of claim 18, wherein the operations comprise:
utilizing bit level storage to represent node types and compression flags.