Storage Estimation for Multidimensional Aggregates in the Presence of Hierarchies

Summary: Estimates storage blowup from precomputing multidimensional aggregates with hierarchies to guide precomputation decisions without materializing them. Three strategies: sampling, mathematical approximation, and probabilistic counting—analyzed; probabilistic counting offers provable error bounds with a single data scan across diverse distributions and schemas. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 8371
Venue: VLDB
Year: 1996
Pagerank: 0.00019536993
Overall Rank: 593 | 95.88%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
158	Automated Selection of Materialized Views and Indexes for SQL Databases	2000	VLDB	0.00040071492
247	On the Computation of Multidimensional Aggregates	1996	VLDB	0.00030927763
368	Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing	1998	VLDB	0.000254931
383	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00024820873
681	Materialized View Selection in a Multidimensional Database	1997	VLDB	0.00018203591
727	On Synopses for Distinct-Value Estimation Under Multiset Operations	2007	SIGMOD	0.00017508726
1,021	Materialized View Selection for Multidimensional Datasets*	1998	VLDB	0.00014619259
1,359	Range Queries in OLAP Data Cubes	1997	SIGMOD	0.0001238588
1,887	Caching Multidimensional Queries Using Chunks	1998	SIGMOD	0.00010204659
3,498	Cubetree: Organization of and Bulk Incremental Updates on the Data Cube	1997	SIGMOD	7.0389539e-05
3,944	AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics	2018	SIGMOD	6.6078243e-05
4,796	Extending Practical Pre-Aggregation in On-Line Analytical Processing	1999	VLDB	5.9152598e-05
7,081	The Polynomial Complexity of Fully Materialized Coalesced Cubes	2004	VLDB	4.8413336e-05
11,332	The White-Box Adversarial Data Stream Model	2022	PODS	4.1945683e-05
12,666	Proxy-Server Architectures for OLAP	2001	SIGMOD	4.1945683e-05
12,697	The TreeScape System: Reuse of Pre-Computed Aggregates over Irregular OLAP Hierarchies	2000	VLDB	4.1945683e-05
12,760	Partial-Sum Queries in OLAP Data Cubes Using Covering Codes	1997	PODS	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 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.0011708144
59	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00064501896
247	On the Computation of Multidimensional Aggregates	1996	VLDB	0.00030927763

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,021	Materialized View Selection for Multidimensional Datasets*	1998	VLDB	0.00014619259
9,432	Aggregate Estimation Over Dynamic Hidden Web Databases	2014	VLDB	4.3431757e-05
134	Processing Aggregate Relational Queries with Hard Time Constraints	1989	SIGMOD	0.00042452811
39	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00074745564
8,684	Unbiased Estimation of Size and Other Aggregates Over Hidden Web Databases	2010	SIGMOD	4.4677591e-05
852	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00015941524
3,702	Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates	2019	CIDR	6.8295759e-05
1,064	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00014356481
996	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD	0.00014741524
269	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00029656549