  A large class of data questions can be modeled as identifying important
slices of data driven by user defined metrics. This paper presents TRACE, a
Time-Relational Approximate Cubing Engine that enables interactive analysis on
such slices with a low upfront cost - both in space and computation. It does
this by materializing the most important parts of the cube over time enabling
interactive querying for a large class of analytical queries e.g. what part of
my business has the highest revenue growth ([SubCategory=Sports Equipment,
Gender=Female]), what slices are lagging in revenue per user ([State=CA,
Age=20-30]). Many user defined metrics are supported including common
aggregations such as SUM, COUNT, DISTINCT COUNT and more complex ones such as
AVERAGE. We implemented and deployed TRACE for a variety of business use cases.
