tf_privacy.tree_aggregation.TreeAggregator

Tree aggregator to compute accumulated noise in private algorithms.

This class implements the tree aggregation algorithm for noise values to efficiently privatize streaming algorithms based on Dwork et al. (2010) https://dl.acm.org/doi/pdf/10.1145/1806689.1806787 A buffer at the scale of tree depth is maintained and updated when a new conceptual leaf node arrives.

random_generator = GaussianNoiseGenerator(...) tree_aggregator = TreeAggregator(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)

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

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

Methods

get_cumsum_and_update

View source

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.

Args
state TreeState for the current leaf node, index can be queried by tree_aggregation.get_step_idx(state.level_buffer_idx).

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.

init_state

View source

Returns initial TreeState.

Initializes TreeState for a tree of a single leaf node: the respective initial node value in TreeState.level_buffer is generated by the value generator function, and the node index is 0.

Returns
An initialized TreeState.

reset_state

View source

Returns reset TreeState after restarting a new tree.