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: hf757eef6e7783156
Venue: VLDB
Year: 1996
Pagerank: 0.0001506436
Overall Rank: 656 | 95.60%
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
88	Automated Selection of Materialized Views and Indexes for SQL Databases	2000	VLDB	0.00035340164
214	On the Computation of Multidimensional Aggregates	1996	VLDB	0.00024650285
216	Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing	1998	VLDB	0.00024485637
494	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00017379171
646	Materialized View Selection in a Multidimensional Database	1997	VLDB	0.00015207197
707	On Synopses for Distinct-Value Estimation Under Multiset Operations	2007	SIGMOD	0.00014633741
957	Materialized View Selection for Multidimensional Datasets	1998	VLDB	0.00012855863
1,107	Range Queries in OLAP Data Cubes	1997	SIGMOD	0.00011988445
1,766	Caching Multidimensional Queries Using Chunks	1998	SIGMOD	9.6923431e-05
3,424	AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics	2018	SIGMOD	7.3084429e-05
3,442	Cubetree: Organization of and Bulk Incremental Updates on the Data Cube	1997	SIGMOD	7.2945433e-05
5,201	Extending Practical Pre-Aggregation in On-Line Analytical Processing	1999	VLDB	6.230103e-05
5,780	Data Streams with Bounded Deletions	2018	PODS	5.9949139e-05
7,046	The Polynomial Complexity of Fully Materialized Coalesced Cubes	2004	VLDB	5.6111702e-05
11,846	The White-Box Adversarial Data Stream Model	2022	PODS	4.9769913e-05
13,155	Proxy-Server Architectures for OLAP	2001	SIGMOD	4.9769913e-05
13,186	The TreeScape System: Reuse of Pre-Computed Aggregates over Irregular OLAP Hierarchies	2000	VLDB	4.9769913e-05
13,250	Partial-Sum Queries in OLAP Data Cubes Using Covering Codes	1997	PODS	4.9769913e-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.00071056708
77	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00036817139
214	On the Computation of Multidimensional Aggregates	1996	VLDB	0.00024650285

Semantically Similar Papers

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