# tf_privacy.tree_aggregation.EfficientTreeAggregator

<br />

|---|
| [![](https://www.tensorflow.org/images/GitHub-Mark-32px.png) View source on GitHub](https://github.com/tensorflow/privacy/blob/v0.9.0/privacy/privacy/dp_query/tree_aggregation.py#L355-L522) |

Efficient tree aggregator to compute accumulated noise.

    tf_privacy.tree_aggregation.EfficientTreeAggregator(
        value_generator: Union[https://www.tensorflow.org/responsible_ai/privacy/api_docs/python/tf_privacy/tree_aggregation/ValueGenerator, Callable[[], Any]]
    )

This class implements the efficient tree aggregation algorithm based on
Honaker 2015 "Efficient Use of Differentially Private Binary Trees".
The noise standard deviation for a node at depth d is roughly
`sigma * sqrt(2^{d-1}/(2^d-1))`. which becomes `sigma / sqrt(2)` when
the tree is very tall.

<br />

<br />

<br />

| ## Example usage ||
|---|---|
| random_generator = GaussianNoiseGenerator(...) tree_aggregator = EfficientTreeAggregator(random_generator) state = tree_aggregator.init_state() for leaf_node_idx in range(total_steps): assert leaf_node_idx == get_step_idx(state)) noise, state = tree_aggregator.get_cumsum_and_update(state) ||

<br />

<br />

<br />

<br />

| ## Args ||
|---|---|
| `value_generator` | A `ValueGenerator` or a no-arg function to generate a noise value for each tree node. |

<br />

<br />

<br />

<br />

| ## Attributes ||
|---|---|
| `value_generator` | A `ValueGenerator` or a no-arg function to generate a noise value for each tree node. |

<br />

## Methods

### `get_cumsum_and_update`

[View source](https://github.com/tensorflow/privacy/blob/v0.9.0/privacy/privacy/dp_query/tree_aggregation.py#L442-L522)

    @tf.function
    get_cumsum_and_update(
        state: https://www.tensorflow.org/responsible_ai/privacy/api_docs/python/tf_privacy/tree_aggregation/TreeState
    ) -> Tuple[tf.Tensor, https://www.tensorflow.org/responsible_ai/privacy/api_docs/python/tf_privacy/tree_aggregation/TreeState]

Returns tree aggregated noise and updates `TreeState` for the next step.

`TreeState` is updated to prepare for accepting the *next* leaf node. Note
that `get_step_idx` can be called to get the current index of the leaf node
before calling this function. This function accept state for the current
leaf node and prepare for the next leaf node because TFF prefers to know
the types of state at initialization. Note that the value of new node in
[`TreeState.level_buffer`](https://www.tensorflow.org/responsible_ai/privacy/api_docs/python/tf_privacy/tree_aggregation/TreeState#level_buffer) will depend on its two children, and is updated
from bottom up for the right child.

<br />

<br />

<br />

| Args ||
|---|---|
| `state` | `TreeState` for the current leaf node, index can be queried by [`tree_aggregation.get_step_idx(state.level_buffer_idx)`](https://www.tensorflow.org/responsible_ai/privacy/api_docs/python/tf_privacy/tree_aggregation/get_step_idx). |

<br />

<br />

<br />

<br />

| Returns ||
|---|---|
| Tuple of (noise, state) where `noise` is generated by tree aggregated protocol for the cumulative sum of streaming data, and `state` is the updated `TreeState`.. ||

<br />

### `init_state`

[View source](https://github.com/tensorflow/privacy/blob/v0.9.0/privacy/privacy/dp_query/tree_aggregation.py#L407-L418)

    init_state() -> https://www.tensorflow.org/responsible_ai/privacy/api_docs/python/tf_privacy/tree_aggregation/TreeState

Returns initial `TreeState`.

Initializes `TreeState` for a tree of a single leaf node: the respective
initial node value in [`TreeState.level_buffer`](https://www.tensorflow.org/responsible_ai/privacy/api_docs/python/tf_privacy/tree_aggregation/TreeState#level_buffer) is generated by the value
generator function, and the node index is 0.

<br />

<br />

<br />

| Returns ||
|---|---|
| An initialized `TreeState`. ||

<br />

### `reset_state`

[View source](https://github.com/tensorflow/privacy/blob/v0.9.0/privacy/privacy/dp_query/tree_aggregation.py#L420-L422)

    reset_state(
        state: https://www.tensorflow.org/responsible_ai/privacy/api_docs/python/tf_privacy/tree_aggregation/TreeState
    ) -> https://www.tensorflow.org/responsible_ai/privacy/api_docs/python/tf_privacy/tree_aggregation/TreeState

Returns reset `TreeState` after restarting a new tree.