Implementing Data Cubes Efficiently

Summary: Uses a view-dependency lattice to decide which data-cube cells to materialize when full materialization is infeasible; greedy algorithms yield constant-factor near-optimality. Hypercube-lattice focus, detailing space–time tradeoffs and practical materialization strategies for fast aggregates. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h4a0ff95cf478c628
Venue: SIGMOD
Year: 1996
Pagerank: 0.00071084324
Overall Rank: 11 | 99.93%
DOI: 10.1145/233269.233333

Incoming Non-self Citations Over Time

Authors

1. Venky Harinarayan (Stanford University)
2. Anand Rajaraman (Stanford University)
3. Jeffrey D. Ullman (Stanford University)

BibTeX Citation

@inproceedings{harinarayan_sigmod96,
        title = {{Implementing Data Cubes Efficiently}},
        author = {Harinarayan, Venky and Rajaraman, Anand and Ullman, Jeffrey D.},
        series = {{SIGMOD} '96},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/233269.233333},
        url = {https://dl.acm.org/doi/10.1145/233269.233333},
        year = {1996}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 127 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,279	Searchlight: Enabling Integrated Search and Exploration over Large Multidimensional Data	2015	VLDB	7.4620555e-05
3,424	AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics	2018	SIGMOD	7.3117029e-05
3,427	Efficient Processing of Window Functions in Analytical SQL Queries	2015	VLDB	7.3082914e-05
3,442	Cubetree: Organization of and Bulk Incremental Updates on the Data Cube	1997	SIGMOD	7.2979501e-05
3,446	Apache Hive: From MapReduce to Enterprise-grade Big Data Warehousing	2019	SIGMOD	7.2942885e-05
3,545	Computation Reuse in Analytics Job Service at Microsoft	2018	SIGMOD	7.2134803e-05
3,782	Supporting Ad-hoc Ranking Aggregates	2006	SIGMOD	7.0230959e-05
3,785	Entity Resolution with Evolving Rules	2010	VLDB	7.0212807e-05
3,841	High-Dimensional OLAP: A Minimal Cubing Approach	2004	VLDB	6.9904505e-05
3,850	QC-Trees: An Efficient Summary Structure for Semantic OLAP	2003	SIGMOD	6.9801117e-05
3,920	Effective Caching of Shortest Paths for Location-Based Services	2012	SIGMOD	6.9252611e-05
3,960	On Efficiently Implementing SchemaSQL on a SQL Database System	1999	VLDB	6.8958644e-05
4,232	On the Content of Materialized Aggregate Views	2000	PODS	6.7145949e-05
4,238	A Foundation for Multi-Dimensional Databases	1997	VLDB	6.7099651e-05
4,282	MDL Summarization with Holes	2005	VLDB	6.6890966e-05
4,291	Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs	2008	SIGMOD	6.6827339e-05
4,341	An Adaptive Peer-to-Peer Network for Distributed Caching of OLAP Results	2002	SIGMOD	6.6513835e-05
4,361	Multi-Structural Databases	2005	PODS	6.6385952e-05
4,720	Multiple Aggregations Over Data Streams	2005	SIGMOD	6.4544772e-05
4,739	Going Beyond Provenance: Explaining Query Answers with Pattern-based Counterbalances	2019	SIGMOD	6.4441962e-05
4,798	Aggregation Algorithms for Very Large Compressed Data Warehouses	1999	VLDB	6.4112766e-05
4,802	Fast Data Anonymization with Low Information Loss	2007	VLDB	6.4095862e-05
5,012	User-Defined Aggregate Functions: Bridging Theory and Practice	2006	SIGMOD	6.3145331e-05
5,128	iTrails: Pay-as-you-go Information Integration in Dataspaces	2007	VLDB	6.260847e-05
5,200	Extending Practical Pre-Aggregation in On-Line Analytical Processing	1999	VLDB	6.2326019e-05
5,582	Efficient Computation of Multiple Group By Queries	2005	SIGMOD	6.0768264e-05
5,695	Efficient Allocation Algorithms for OLAP over Imprecise Data	2006	VLDB	6.0334848e-05
5,714	An Alternative Storage Organization for ROLAP Aggregate Views Based on Cubetrees	1998	SIGMOD	6.0202342e-05
5,783	Sampling Cube: A Framework for Statistical OLAP Over Sampling Data	2008	SIGMOD	5.9963988e-05
5,839	Shrinking the Warehouse Update Window	1999	SIGMOD	5.9746195e-05
6,253	Eliminating Costly Redundant Computations from SQL Trigger Executions	1997	SIGMOD	5.8340101e-05
6,543	Prediction Cubes	2005	VLDB	5.7519742e-05
6,577	Efficient Implementation of Large-Scale Multi-Structural Databases	2005	VLDB	5.7447944e-05
6,705	E-Cube: Multi-Dimensional Event Sequence Analysis Using Hierarchical Pattern Query Sharing	2011	SIGMOD	5.7051166e-05
6,715	Optimal Indexing Using Near-Minimal Space [Extended Abstract]	2003	PODS	5.7000336e-05
6,747	Spade: A Modular Framework for Analytical Exploration of RDF Graphs	2019	VLDB	5.6906839e-05
6,795	CURE for Cubes: Cubing Using a ROLAP Engine	2006	VLDB	5.6804621e-05
6,804	Stacked Indexed Views in Microsoft SQL Server	2005	SIGMOD	5.6782614e-05
6,929	Using Latency-Recency Profiles for Data Delivery on the Web	2002	VLDB	5.6414724e-05
6,934	FlowCube: Constructing RFID FlowCubes for Multi-Dimensional Analysis of Commodity Flows	2006	VLDB	5.6405847e-05
7,045	The Polynomial Complexity of Fully Materialized Coalesced Cubes	2004	VLDB	5.6138276e-05
7,701	Enabling Efficient and General Subpopulation Analytics in Multidimensional Data Streams	2022	VLDB	5.474978e-05
7,755	Snakes and Sandwiches: Optimal Clustering Strategies for a Data Warehouse	1999	SIGMOD	5.4590631e-05
8,142	Information Retrieval from an Incomplete Data Cube	1996	VLDB	5.3913918e-05
8,295	NetCube: A Scalable Tool for Fast Data Mining and Compression	2001	VLDB	5.3612406e-05
8,354	Sofos: Demonstrating the Challenges of Materialized View Selection on Knowledge Graphs	2021	SIGMOD	5.3484424e-05
8,561	Materialized View Selection for XQuery Workloads	2012	SIGMOD	5.314012e-05
8,621	Maintenance of Cube Automatic Summary Tables	2000	SIGMOD	5.3012918e-05
8,696	View Selection over Knowledge Graphs in Triple Stores	2021	VLDB	5.2905577e-05
8,750	Bellwether Analysis: Predicting Global Aggregates from Local Regions	2006	VLDB	5.2851374e-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
73	Including Group-By in Query Optimization	1994	VLDB	0.00037522101
77	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00036828234
202	Aggregate-Query Processing in Data Warehousing Environments	1995	VLDB	0.00025244649

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,619	Cost-Based Optimization of Decision Support Queries using Transient-Views	1998	SIGMOD
2	9,585	Materializing Views with Minimal Size To Answer Queries	2003	PODS
3	553	Optimizing Queries Using Materialized Views: A Practical, Scalable Solution	2001	SIGMOD
4	3,841	High-Dimensional OLAP: A Minimal Cubing Approach	2004	VLDB
5	1,706	Algorithms for Materialized View Design in Data Warehousing Environment	1997	VLDB
6	214	On the Computation of Multidimensional Aggregates	1996	VLDB
7	11,917	High-dimensional Data Cubes	2022	VLDB
8	644	Materialized View Selection in a Multidimensional Database	1997	VLDB
9	13,211	Dynamic Assembly of Views in Data Cubes	1998	PODS
10	1,068	Fast Computation of Sparse Datacubes	1997	VLDB