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.00015022694
Overall Rank: 660 | 95.58%
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
89	Automated Selection of Materialized Views and Indexes for SQL Databases	2000	VLDB	0.00035265687
214	On the Computation of Multidimensional Aggregates	1996	VLDB	0.00024576033
216	Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing	1998	VLDB	0.00024446892
495	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00017347522
648	Materialized View Selection in a Multidimensional Database	1997	VLDB	0.00015161755
711	On Synopses for Distinct-Value Estimation Under Multiset Operations	2007	SIGMOD	0.00014589586
961	Materialized View Selection for Multidimensional Datasets	1998	VLDB	0.0001281898
1,110	Range Queries in OLAP Data Cubes	1997	SIGMOD	0.00011949109
1,779	Caching Multidimensional Queries Using Chunks	1998	SIGMOD	9.6641413e-05
3,435	AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics	2018	SIGMOD	7.2845431e-05
3,454	Cubetree: Organization of and Bulk Incremental Updates on the Data Cube	1997	SIGMOD	7.270801e-05
5,198	Extending Practical Pre-Aggregation in On-Line Analytical Processing	1999	VLDB	6.218781e-05
5,761	Data Streams with Bounded Deletions	2018	PODS	5.9847577e-05
7,067	The Polynomial Complexity of Fully Materialized Coalesced Cubes	2004	VLDB	5.5926201e-05
11,890	The White-Box Adversarial Data Stream Model	2022	PODS	4.9605343e-05
13,196	Proxy-Server Architectures for OLAP	2001	SIGMOD	4.9605343e-05
13,227	The TreeScape System: Reuse of Pre-Computed Aggregates over Irregular OLAP Hierarchies	2000	VLDB	4.9605343e-05
13,291	Partial-Sum Queries in OLAP Data Cubes Using Covering Codes	1997	PODS	4.9605343e-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.00070860346
78	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00036725074
214	On the Computation of Multidimensional Aggregates	1996	VLDB	0.00024576033

Semantically Similar Papers

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