# Efficient and Optimal Algorithms for Tree Summarization with Weighted Terminologies

arXiv: https://arxiv.org/abs/2008.03053 · HTML: https://mlsanity.com/paper/2008.03053/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Aug 2020.

## Built on by (most cited first, 1 of 1)

- [LLM-CoOpt: A Co-Design and Optimization Framework for Efficient LLM Inference on Heterogeneous Platforms](https://mlsanity.com/paper/2602.09323/) (2026)

## Abstract (arXiv)

Data summarization that presents a small subset of a dataset to users has been widely applied in numerous applications and systems. Many datasets are coded with hierarchical terminologies, e.g., the international classification of Diseases-9, Medical Subject Heading, and Gene Ontology, to name a few. In this paper, we study the problem of selecting a diverse set of k elements to summarize an input dataset with hierarchical terminologies, and visualize the summary in an ontology structure. We propose an efficient greedy algorithm to solve the problem with (1-1/e) = 62% -approximation guarantee. Although this greedy solution achieves quality-guaranteed answers approximately but it is still not optimal. To tackle the problem optimally, we further develop a dynamic programming algorithm to obtain optimal answers for graph visualization of log-data using ontology terminologies called OVDO . The complexity and correctness of OVDO are theoretically analyzed. In addition, we propose a useful optimization technique of tree reduction to remove useless nodes with zero weights and shrink the tree into a smaller one, which ensures the efficiency acceleration of OVDO in many real-world applications. Extensive experimental results on real-world datasets show the effectiveness and efficiency of our proposed approximate and exact algorithms for tree data summarization.