Fast Computation of Sparse Datacubes

Summary: Introduces a novel, scalable algorithm for fast sparse datacubes with many CUBE BY attributes. In-memory data uses multiple sorts with no I/O beyond input and output; out-of-core uses divide-and-conquer to sub-datacubes, with I/O cost linear in the number of CUBE BY attributes. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h7d114059a86c27aa
Venue: VLDB
Year: 1997
Pagerank: 0.00012185465
Overall Rank: 1,068 | 92.83%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Kenneth A. Ross (Columbia University)
2. Divesh Srivastava (AT&T)

BibTeX Citation

@article{ross_vldb97,
        title = {{Fast Computation of Sparse Datacubes}},
        author = {Ross, Kenneth A. and Srivastava, Divesh},
        journal = {PVLDB},
        series = {{VLDB} '97},
        year = {1997}
}

Incoming Citations (Sorted by Pagerank)

Showing 22 of 22 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
403	Bottom-Up Computation of Sparse and Iceberg CUBEs	1999	SIGMOD	0.0001910396
957	Materialized View Selection for Multidimensional Datasets	1998	VLDB	0.00012861484
1,394	Efficient Computation of the Skyline Cube	2005	VLDB	0.00010796403
2,256	Dwarf: Shrinking the PetaCube	2002	SIGMOD	8.7438759e-05
2,544	Star-Cubing: Computing Iceberg Cubes by Top-Down and Bottom-Up Integration	2003	VLDB	8.3179863e-05
2,786	DADA: A Data Cube for Dominant Relationship Analysis	2006	SIGMOD	8.0165674e-05
3,782	Supporting Ad-hoc Ranking Aggregates	2006	SIGMOD	7.0230959e-05
3,832	OLAP on Sequence Data	2008	SIGMOD	6.9945112e-05
3,850	QC-Trees: An Efficient Summary Structure for Semantic OLAP	2003	SIGMOD	6.9801117e-05
5,582	Efficient Computation of Multiple Group By Queries	2005	SIGMOD	6.0768264e-05
5,632	Combi-Operator – Database Support for Data Mining Applications	2003	VLDB	6.0581466e-05
5,695	Efficient Allocation Algorithms for OLAP over Imprecise Data	2006	VLDB	6.0334848e-05
6,795	CURE for Cubes: Cubing Using a ROLAP Engine	2006	VLDB	5.6804621e-05
7,045	The Polynomial Complexity of Fully Materialized Coalesced Cubes	2004	VLDB	5.6138276e-05
10,012	Iceberg-cube Computation with PC Clusters	2001	SIGMOD	5.0979044e-05
10,799	Finding Non-Redundant Simpson's Paradox in Multidimensional Data	2026	VLDB	4.9793485e-05
11,917	High-dimensional Data Cubes	2022	VLDB	4.9793485e-05
12,213	Robust, Scalable, Real-Time Event Time Series Aggregation at Twitter	2018	SIGMOD	4.9793485e-05
12,331	An Efficient MapReduce Cube Algorithm for Varied Data Distributions	2016	SIGMOD	4.9793485e-05
12,586	Permuting Data on Random-Access Block Storage	2013	VLDB	4.9793485e-05
12,893	Dwarfs in the Rearview Mirror: How Big are they Really?	2008	VLDB	4.9793485e-05
13,211	Dynamic Assembly of Views in Data Cubes	1998	PODS	4.9793485e-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.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

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,489	Compressed Representations of Conjunctive Query Results	2018	PODS
2	1,874	Efficient Computation of Iceberg Cubes with Complex Measures	2001	SIGMOD
3	10,204	Dynamic Update Cube for Range-Sum Queries	2001	VLDB
4	8,814	ARCube: Supporting Ranking Aggregate Queries in Partially Materialized Data Cubes	2008	SIGMOD
5	12,331	An Efficient MapReduce Cube Algorithm for Varied Data Distributions	2016	SIGMOD
6	11,917	High-dimensional Data Cubes	2022	VLDB
7	7,045	The Polynomial Complexity of Fully Materialized Coalesced Cubes	2004	VLDB
8	214	On the Computation of Multidimensional Aggregates	1996	VLDB
9	11	Implementing Data Cubes Efficiently	1996	SIGMOD
10	403	Bottom-Up Computation of Sparse and Iceberg CUBEs	1999	SIGMOD