Abstract
We have developed an efficient summarization paradigm for data drawn from hierarchical domain to construct a succinct view of important large-valued regions (“heavy hitters”). It requires one pass over the data with moderate number of updates per element of the data and requires lesser amount of memory space as compared to existing approaches for approximating hierarchically discounted frequency counts of heavy hitters with provable guarantees. The proposed technique is generic that can make use of existing state-of-the-art sketch-based or count-based frequency estimation approaches. Any algorithm from both of these families can be coupled as a subroutine in the proposed framework without any substantial modifications. Experimental as well as theoretical justifications have been provided for its significance.