Title: Hierarchical Summarization of Metric Changes,
Abstract: We study changes in metrics that are defined on a cartesian product of trees.
Such metrics occur naturally in many practical applications, where a global
metric (such as revenue) can be broken down along several hierarchical
dimensions (such as location, gender, etc).
Given a change in such a metric, our goal is to identify a small set of
non-overlapping data segments that account for the change. An organization
interested in improving the metric can then focus their attention on these data
segments.
Our key contribution is an algorithm that mimics the operation of a
hierarchical organization of analysts. The algorithm has been successfully
applied, for example within Google Adwords to help advertisers triage the
performance of their advertising campaigns.
We show that the algorithm is optimal for two dimensions, and has an
approximation ratio $\log^{d-2}(n+1)$ for $d \geq 3$ dimensions, where $n$ is
the number of input data segments. For the Adwords application, we can show
that our algorithm is in fact a $2$-approximation.
Mathematically, we identify a certain data pattern called a \emph{conflict}
that both guides the design of the algorithm, and plays a central role in the
hardness results. We use these conflicts to both derive a lower bound of
$1.144^{d-2}$ (again $d\geq3$) for our algorithm, and to show that the problem
is NP-hard, justifying the focus on approximation.