Effective and Efficient Summarization for Non-hierarchical Data

Xiang Ji1; Xiao Yan2; Kaijun Ren1; Xiang Wang1; Bo Tang2

10.1109/ISPRAS53967.2021.00019

2021

2767-9519

978-1-6654-2331-1

2021 Ivannikov Ispras Open Conference (ISPRAS)

100-106

2-3 Dec. 2021

Moscow, Russian Federation

Data cubes are ubiquitous in domains including meteorology, sales and demography, and data summarization is an important service that can be used to compress data cubes and extract insight. Existing data summarization methods require presupposed hierarchies for the data cube dimensions, which do not exist for many types of data (e.g., rainfall and temperature). To tackle this problem, we first define the non-hierarchical data summarization (NHDS) problem, which covers data cube using rectangle regions with an error bound and minimizes the summary size. We then show that the NHDS problem is NP-hard and design the Mark and Select (MS) algorithm to find an approximate solution. MS first identifies the qualified rectangles and then selects among the rectangles to cover the data cube. To improve efficiency, we show that it suffices to find only some of the qualified rectangles, devise a procedure to avoid checking rectangles that do not contribute to the result, save unnecessary computation during rectangle selection using sub-modularity. We conducted experiments on both real and synthetic datasets. The results show that MS significantly outperforms a state-of-the-art baseline in summary size, error and running time.

data cube non-hierarchical data summary

其他

EI

IEEE

1.National University of Defense Technology,Changsha,China
2.Southern University of Science and Technology,Shenzhen,China

Xiang Ji,Xiao Yan,Kaijun Ren,et al. Effective and Efficient Summarization for Non-hierarchical Data[C],2021:100-106.