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: h3a3e69e7cb0af886
Venue: VLDB
Year: 2005
Pagerank: 6.6890966e-05
Overall Rank: 4,282 | 71.22%
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
878	Interpretable and Informative Explanations of Outcomes	2015	VLDB	0.00013302631
6,436	Summarized Causal Explanations For Aggregate Views	2024	SIGMOD	5.7853643e-05
7,146	Guided Exploration of Data Summaries	2022	VLDB	5.5993699e-05
7,512	Compact Histograms for Hierarchical Identifiers	2006	VLDB	5.504973e-05
8,326	The Cascading Analysts Algorithm	2018	SIGMOD	5.3540725e-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.00071084324
222	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD	0.00024218831
323	An Array-Based Algorithm for Simultaneous Multidimensional Aggregates	1997	SIGMOD	0.0002100085
700	Explaining differences in multidimensional aggregates	1999	VLDB	0.00014681669
925	Intelligent Rollups in Multidimensional OLAP Data	2001	VLDB	0.00013051939
984	User-adaptive exploration of multidimensional data	2000	VLDB	0.00012686375
2,256	Dwarf: Shrinking the PetaCube	2002	SIGMOD	8.7438759e-05
2,434	The Generalized MDL Approach for Summarization	2002	VLDB	8.4746361e-05
3,460	Quotient Cube: How to Summarize the Semantics of a Data Cube	2002	VLDB	7.2845441e-05
8,564	Concise Descriptions of Subsets of Structured Sets	2003	PODS	5.3138033e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	214	On the Computation of Multidimensional Aggregates	1996	VLDB
2	4,798	Aggregation Algorithms for Very Large Compressed Data Warehouses	1999	VLDB
3	3,850	QC-Trees: An Efficient Summary Structure for Semantic OLAP	2003	SIGMOD
4	5,004	Fast Algorithms For Hierarchical Range Histogram Construction	2002	PODS
5	3,841	High-Dimensional OLAP: A Minimal Cubing Approach	2004	VLDB
6	7,513	Computing A Well-Representative Summary of Conjunctive Query Results	2024	PODS
7	1,127	Simultaneous Optimization and Evaluation of Multiple Dimensional Queries	1998	SIGMOD
8	700	Explaining differences in multidimensional aggregates	1999	VLDB
9	8,564	Concise Descriptions of Subsets of Structured Sets	2003	PODS
10	2,434	The Generalized MDL Approach for Summarization	2002	VLDB