MDL Summarization with Holes

Summary: Introduces MDL summaries S⊕H for hierarchical k-d cubes, separating generalized query results from explicit exceptions. The 1-D case is linear while 2-D is NP-hard; greedy and dynamic-programming heuristics yield substantially shorter summaries. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 9515
Venue: VLDB
Year: 2005
Pagerank: 6.834169e-05
Overall Rank: 4,204 | 71.16%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Shaofeng Bu (University of British Columbia)
2. Laks V.S. Lakshmanan (University of British Columbia)
3. Raymond T. Ng (University of British Columbia)

BibTeX Citation

@article{bu_vldb05,
        title = {{MDL Summarization with Holes}},
        author = {Bu, Shaofeng and Lakshmanan, Laks V.S. and Ng, Raymond T.},
        journal = {PVLDB},
        series = {{VLDB} '05},
        pages = {433},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
858	Interpretable and Informative Explanations of Outcomes	2015	VLDB	0.0001356511
6,932	Summarized Causal Explanations For Aggregate Views	2024	SIGMOD	5.7362362e-05
7,003	Guided Exploration of Data Summaries	2022	VLDB	5.7278883e-05
7,375	Compact Histograms for Hierarchical Identifiers	2006	VLDB	5.6299286e-05
8,153	The Cascading Analysts Algorithm	2018	SIGMOD	5.4769543e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
11	Implementing Data Cubes Efficiently	1996	SIGMOD	0.00071822821
213	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD	0.00024723025
324	An Array-Based Algorithm for Simultaneous Multidimensional Aggregates	1997	SIGMOD	0.00021200835
700	Explaining differences in multidimensional aggregates	1999	VLDB	0.00014871032
915	Intelligent Rollups in Multidimensional OLAP Data	2001	VLDB	0.00013243386
965	User-adaptive exploration of multidimensional data	2000	VLDB	0.00012933878
2,318	Dwarf: Shrinking the PetaCube	2002	SIGMOD	8.7588859e-05
2,382	The Generalized MDL Approach for Summarization	2002	VLDB	8.6603462e-05
3,407	Quotient Cube: How to Summarize the Semantics of a Data Cube	2002	VLDB	7.4391131e-05
8,393	Concise Descriptions of Subsets of Structured Sets	2003	PODS	5.4353444e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,647	Data Summarization with Hierarchical Taxonomy	2021	SIGMOD
2	4,723	Aggregation Algorithms for Very Large Compressed Data Warehouses	1999	VLDB
3	3,774	QC-Trees: An Efficient Summary Structure for Semantic OLAP	2003	SIGMOD
4	4,889	Fast Algorithms For Hierarchical Range Histogram Construction	2002	PODS
5	3,753	High-Dimensional OLAP: A Minimal Cubing Approach	2004	VLDB
6	8,728	Computing A Well-Representative Summary of Conjunctive Query Results	2024	PODS
7	1,107	Simultaneous Optimization and Evaluation of Multiple Dimensional Queries	1998	SIGMOD
8	700	Explaining differences in multidimensional aggregates	1999	VLDB
9	8,393	Concise Descriptions of Subsets of Structured Sets	2003	PODS
10	2,382	The Generalized MDL Approach for Summarization	2002	VLDB