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: 8562
Venue: VLDB
Year: 1996
Pagerank: 0.0001527187
Overall Rank: 654 | 95.52%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Amit Shukla (University of Wisconsin)
2. Jeffrey F. Naughton (University of Wisconsin)
3. Prasad M. Deshpande (University of Wisconsin)
4. Karthikeyan Ramasamy (University of Wisconsin)

BibTeX Citation

@article{shukla_vldb96,
        title = {{Storage Estimation for Multidimensional Aggregates in the Presence of Hierarchies}},
        author = {Shukla, Amit and Naughton, Jeffrey F. and Deshpande, Prasad M. and Ramasamy, Karthikeyan},
        journal = {PVLDB},
        series = {{VLDB} '96},
        pages = {522},
        year = {1996}
}

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
87	Automated Selection of Materialized Views and Indexes for SQL Databases	2000	VLDB	0.00035281619
207	On the Computation of Multidimensional Aggregates	1996	VLDB	0.00025088003
227	Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing	1998	VLDB	0.00023958508
482	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00017772185
638	Materialized View Selection in a Multidimensional Database	1997	VLDB	0.000154719
689	On Synopses for Distinct-Value Estimation Under Multiset Operations	2007	SIGMOD	0.00014940023
942	Materialized View Selection for Multidimensional Datasets	1998	VLDB	0.00013076262
1,100	Range Queries in OLAP Data Cubes	1997	SIGMOD	0.00012169143
1,732	Caching Multidimensional Queries Using Chunks	1998	SIGMOD	9.9065981e-05
3,366	AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics	2018	SIGMOD	7.4748604e-05
3,379	Cubetree: Organization of and Bulk Incremental Updates on the Data Cube	1997	SIGMOD	7.4582502e-05
5,136	Extending Practical Pre-Aggregation in On-Line Analytical Processing	1999	VLDB	6.3519278e-05
5,669	Data Streams with Bounded Deletions	2018	PODS	6.1278944e-05
6,902	The Polynomial Complexity of Fully Materialized Coalesced Cubes	2004	VLDB	5.7426524e-05
11,531	The White-Box Adversarial Data Stream Model	2022	PODS	5.093636e-05
12,859	Proxy-Server Architectures for OLAP	2001	SIGMOD	5.093636e-05
12,890	The TreeScape System: Reuse of Pre-Computed Aggregates over Irregular OLAP Hierarchies	2000	VLDB	5.093636e-05
12,954	Partial-Sum Queries in OLAP Data Cubes Using Covering Codes	1997	PODS	5.093636e-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.00071822821
75	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00037277061
207	On the Computation of Multidimensional Aggregates	1996	VLDB	0.00025088003

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	942	Materialized View Selection for Multidimensional Datasets	1998	VLDB
2	9,650	Aggregate Estimation Over Dynamic Hidden Web Databases	2014	VLDB
3	178	Processing Aggregate Relational Queries with Hard Time Constraints	1989	SIGMOD
4	55	Statistical Estimators for Relational Algebra Expressions	1988	PODS
5	8,671	Unbiased Estimation of Size and Other Aggregates Over Hidden Web Databases	2010	SIGMOD
6	723	Dynamic Multidimensional Histograms	2002	SIGMOD
7	3,215	Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates	2019	CIDR
8	817	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD
9	850	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD
10	235	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB