The Polynomial Complexity of Fully Materialized Coalesced Cubes

Summary: Shows analytically that fully materialized, exact coalesced cubes scale polynomially (often near-linearly in tuple count), avoiding the curse of dimensionality. A metadata-only size estimator is validated on uniform, Zipfian, and real data. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h7809acaa2a60e812
Venue: VLDB
Year: 2004
Pagerank: 5.6138276e-05
Overall Rank: 7,045 | 52.64%
DOI: 10.1016/B978-012088469-8.50049-8

Incoming Non-self Citations Over Time

Authors

1. Yannis Sismanis (University of Maryland)
2. Nick Roussopoulos (University of Maryland)

BibTeX Citation

@article{sismanis_vldb04,
        title = {{The Polynomial Complexity of Fully Materialized Coalesced Cubes}},
        author = {Sismanis, Yannis and Roussopoulos, Nick},
        journal = {PVLDB},
        series = {{VLDB} '04},
        doi = {10.1016/B978-012088469-8.50049-8},
        url = {https://doi.org/10.1016/B978-012088469-8.50049-8},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,291	GORDIAN: Efficient and Scalable Discovery of Composite Keys	2006	VLDB	8.6872323e-05
5,783	Sampling Cube: A Framework for Statistical OLAP Over Sampling Data	2008	SIGMOD	5.9963988e-05
6,795	CURE for Cubes: Cubing Using a ROLAP Engine	2006	VLDB	5.6804621e-05
12,893	Dwarfs in the Rearview Mirror: How Big are they Really?	2008	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 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
214	On the Computation of Multidimensional Aggregates	1996	VLDB	0.00024656893
323	An Array-Based Algorithm for Simultaneous Multidimensional Aggregates	1997	SIGMOD	0.0002100085
403	Bottom-Up Computation of Sparse and Iceberg CUBEs	1999	SIGMOD	0.0001910396
564	Congressional Samples for Approximate Answering of Group-By Queries	2000	SIGMOD	0.00016296665
655	Storage Estimation for Multidimensional Aggregates in the Presence of Hierarchies	1996	VLDB	0.00015070228
1,068	Fast Computation of Sparse Datacubes	1997	VLDB	0.00012185465
1,547	Data Warehouse Configuration	1997	VLDB	0.00010292395
2,256	Dwarf: Shrinking the PetaCube	2002	SIGMOD	8.7438759e-05
3,259	On the Complexity of the View-Selection Problem	1999	PODS	7.4855259e-05
3,442	Cubetree: Organization of and Bulk Incremental Updates on the Data Cube	1997	SIGMOD	7.2979501e-05
3,850	QC-Trees: An Efficient Summary Structure for Semantic OLAP	2003	SIGMOD	6.9801117e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,544	Star-Cubing: Computing Iceberg Cubes by Top-Down and Bottom-Up Integration	2003	VLDB
2	7,513	Computing A Well-Representative Summary of Conjunctive Query Results	2024	PODS
3	11,472	The Moments Method for Approximate Data Cube Queries	2024	PODS
4	403	Bottom-Up Computation of Sparse and Iceberg CUBEs	1999	SIGMOD
5	13,211	Dynamic Assembly of Views in Data Cubes	1998	PODS
6	3,841	High-Dimensional OLAP: A Minimal Cubing Approach	2004	VLDB
7	1,874	Efficient Computation of Iceberg Cubes with Complex Measures	2001	SIGMOD
8	11,917	High-dimensional Data Cubes	2022	VLDB
9	1,068	Fast Computation of Sparse Datacubes	1997	VLDB
10	214	On the Computation of Multidimensional Aggregates	1996	VLDB