Dynamically optimizing decision tree inferences
A method of dynamically optimizing decision tree inference is provided. The method, which is performed at the computerized system, repeatedly executes one or more decision trees for inference purposes and repeatedly performs an optimization procedure according to two-phase cycles. Each cycle includes two alternating phases, i.e., a first phase followed by a second phase. The decision trees are executed based on a reference data structure, whereby attributes of nodes of the decision trees are repeatedly accessed from the reference data structure during the first phase of each of the cycles. First, the accessed attributes are monitored during the first phase of each cycle, which leads to update statistical characteristics of the nodes. Second, a substitute data structure is configured during the second phase of each cycle based on the updated statistical characteristics. Third, the reference data structure is updated in accordance with the substitute data structure.
1 . A method of dynamically optimizing decision tree inference operations performed by a computerized system, the method comprising, at the computerized system,
repeatedly executing one or more decision trees for inference purposes and repeatedly performing an optimization procedure according to two-phase cycles, wherein
each of the cycles includes two alternating phases, the two alternating phases including a first phase and a second phase,
the one or more decision trees are executed based on a reference data structure, whereby attributes of nodes of the one or more decision trees are repeatedly accessed from the reference data structure during the first phase of each of the cycles, and
performing the optimization procedure comprises:
during the first phase of each of the cycles, monitoring the accessed attributes to update statistical characteristics of the nodes;
during the second phase of each of the cycles, configuring a substitute data structure based on the updated statistical characteristics; and
updating the reference data structure in accordance with the substitute data structure.
2 . The method according to claim 1 , wherein,
the first phase of each of the cycles is triggered upon receiving a request to perform inferences,
the second phase of each of the cycles is subsequently triggered upon completing said inferences, and
the first phase of a next one of the cycles is triggered upon receiving a further request to perform further inferences.
3 . The method according to claim 1 , wherein,
the reference data structure is updated during the second phase of at least some of the cycles.
4 . The method according to claim 1 , wherein,
the reference data structure is updated by substituting at least a subset of the reference data structure for the substitute data structure.
5 . The method according to claim 4 , wherein,
the reference data structure is stored in a memory buffer of the computerized system, whereby the attributes are repeatedly accessed from this memory buffer upon executing the one or more decision trees, and
the reference data structure is updated by substituting at least said subset of the reference data structure for the substitute data structure in the memory buffer.
6 . The method according to claim 5 , wherein,
the substitute data structure represents only a subset of the one or more decision trees, whereby only said subset of the reference data structure is substituted for the substitute data structure in the memory buffer, while a residual subset of the reference data structure is modified to logically link it to the substitute data structure.
7 . The method according to claim 5 , wherein,
the updated statistical characteristics includes at least a most likely path of access to the nodes,
configuring the substitute data structure comprises writing attributes of the identified nodes in blocks of the substitute data structure, wherein the blocks are ordered in accordance with said statistical order, and
the reference data structure is updated by writing the ordered blocks to memory blocks of the memory buffer, whereby attributes of at least some pairs of the nodes that are consecutively accessed as per said statistical order are written in consecutive memory blocks of the memory buffer.
8 . The method according to claim 7 , wherein,
said memory buffer is a cache memory of the computerized system, whereby writing the ordered blocks causes to orderly map the ordered blocks onto memory blocks of cache lines of the cache memory.
9 . The method according to claim 7 , wherein,
at monitoring, the updated statistical characteristics of the nodes include access counts of the nodes and said statistical order is determined based on the access counts.
10 . The method according to claim 7 , wherein,
the substitute data structure represents only a subset of the nodes of the one or more decision trees.
11 . The method according to claim 10 , wherein,
the subsets of the nodes represented by the substitute data structure are nodes having larger access counts than remaining nodes of the one or more decision trees, as per the updated statistical characteristics.
12 . The method according to claim 1 , wherein,
the accessed attributes are monitored according to a process having a lower priority than an execution of instructions for executing the one or more decision trees.
13 . The method according to claim 1 , wherein performing the optimization procedure further comprises
comparing the substitute data structure with the reference data structure to determine an extent of changes from the reference data structure, and
based on the determined extent of changes, deciding whether to update the reference data structure in accordance with the substitute data structure.
14 . The method according to claim 13 , wherein,
said extent of changes is determined as a distance between the substitute data structure and a corresponding subset of the reference data structure.
15 . The method according to claim 14 , wherein,
said distance is determined according to access counts of the nodes, the access count forming part of the monitored attributes.
16 . The method according to claim 1 , wherein,
the method is performed in respect of a set of decision trees, whereby several decision trees are being concurrently executed for inference purposes.
17 . The method according to claim 16 , wherein,
the decision trees of the set form part of an ensemble model, whereby an inference result as eventually returned by the method is based on an outcome of executing each of the decision trees of the set.
18 . A computerized system for dynamically optimizing decision tree inference operations, wherein the computerized system comprises:
processing means that are configured to repeatedly execute one or more decision trees for inference purposes and repeatedly perform an optimization procedure according to two-phase cycles, wherein, in operation,
each of the cycles includes two alternating phases, the two alternating phases including a first phase and a second phase,
the one or more decision trees are executed based on a reference data structure, whereby attributes of nodes of the one or more decision trees are repeatedly accessed from the reference data structure during the first phase of each of the cycles, and
performing the optimization procedure comprises:
during the first phase of each of the cycles, monitoring the accessed attributes to update statistical characteristics of the nodes;
during the second phase of each of the cycles, configuring a substitute data structure based on the updated statistical characteristics; and
updating the reference data structure in accordance with the substitute data structure.
19 . A computer program product for dynamically optimizing decision tree inference operations, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by processing means to cause the latter to:
repeatedly execute one or more decision trees for inference purposes and repeatedly perform an optimization procedure according to two-phase cycles, wherein,
each of the cycles includes two alternating phases, the two alternating phases including a first phase and a second phase,
the one or more decision trees are executed based on a reference data structure, whereby attributes of nodes of the one or more decision trees are repeatedly accessed from the reference data structure during the first phase of each of the cycles, and
performing the optimization procedure comprises:
during the first phase of each of the cycles, monitoring the accessed attributes to update statistical characteristics of the nodes;
during the second phase of each of the cycles, configuring a substitute data structure based on the updated statistical characteristics; and
updating the reference data structure in accordance with the substitute data structure.
20 . The computer program product according to claim 19 , wherein,
the program instructions are executable by the processing means to further cause the latter to update the reference data structure by substituting at least a subset of the reference data structure for the substitute data structure.
21 . The computer program product according to claim 20 , wherein,
the program instructions are executable by the processing means to further cause the latter to store the reference data structure in a memory buffer of the computerized system, whereby the attributes are repeatedly accessed from this memory buffer upon executing the one or more decision trees, and
the reference data structure is updated by substituting at least said subset of the reference data structure for the substitute data structure in the memory buffer.
22 . The computer program product according to claim 20 , wherein,
the substitute data structure represents only a subset of the one or more decision trees, whereby only said subset of the reference data structure is substituted for the substitute data structure in the memory buffer, while a residual subset of the reference data structure is modified to logically link it to the substitute data structure.
23 . The computer program product according to claim 20 , wherein,
the program instructions are executable by the processing means to further cause the latter to update the reference data structure by substituting at least a subset of the reference data structure for the substitute data structure.
24 . The computer program product according to claim 20 , wherein,
the updated statistical characteristics includes at least a most likely path of access to the nodes,
configuring the substitute data structure comprises writing attributes of the identified nodes in blocks of the substitute data structure, wherein the blocks are ordered in accordance with said statistical order, and
the reference data structure is updated by writing the ordered blocks to memory blocks of the memory buffer, whereby attributes of at least some pairs of the nodes that are consecutively accessed as per said statistical order are written in consecutive memory blocks of the memory buffer.
25 . The computer program product according to claim 19 , wherein,
the accessed attributes are monitored according to a process having a lower priority than an execution of instructions for executing the one or more decision trees.