Data structure to array conversion
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.
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.
2. 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.
3. 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.
4. 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.
5. 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.
6. The method of claim 1 , wherein the tree structure represents a model used by machine learning functionality to output a prediction.
7. The method of claim 6 , wherein the prediction corresponds to predicted user behavior.
8. The method of claim 1 , comprising:
loading the array into memory for execution of a model represented by the tree structure.
9. 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.
10. The method of claim 9 , wherein the byte array comprises serialized internal data specifying split values of nodes.
11. The method of claim 9 , wherein the byte array comprises serialized internal data specifying a feature index.
12. 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.
13. 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.
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.
15. The computing device of claim 14 , wherein the reference comprises an index value in short integer format.
16. The computing device of claim 14 , wherein the operations comprise:
generating a lookup table comprising values occurring within models greater than a frequency threshold.
17. The computing device of claim 16 , wherein the operations comprise:
utilizing the lookup table to compress the array.
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.
19. 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.
20. The non-transitory machine readable medium of claim 18 , wherein the operations comprise:
utilizing bit level storage to represent node types and compression flags.