Structure-Aware Abstraction of Hierarchical Time Series

Abstracting hierarchical time series at scale requires methods that remain both effective and efficient. Existing approaches, however, are limited to flat clustering ignoring hierarchy or hierarchical summarization overlooking temporal similarities, and thus fail to capture hierarchical time series structures pervasive from finance and healthcare to bibliographic corpora. We propose a novel problem of hierarchical time series abstraction (HTSA), which seeks a small set of structure-aware subseries that jointly capture temporal dynamics and hierarchical organization. We provide the first formal analysis of HTSA, proving its NP-hardness and showing that the objective is neither monotone nor submodular. To address these challenges, we design a scalable framework that constructs disjoint representative subtrees through greedy selection, enhanced with techniques targeting both effectiveness and efficiency. To further improve the effectiveness, we propose OSS, whose discretized search provides a 1/alpha-approximation guarantee for each single optimal-subtree computation. Here, alpha is a parameter to trade off the effectiveness and efficiency. Extensive experiments on four real-world datasets and one large dataset demonstrate that our methods consistently outperform strong baselines in representativeness and scalability. A case study on the ACM dataset further highlights how HTSA abstracts complex hierarchical structures into concise, informative representations.