Snakes and Sandwiches: Optimal Clustering Strategies for a Data Warehouse

Summary: Lattice-path clustering for fact tables under a workload; dynamic programming computes the optimal lattice-path clustering in time linear in lattice size. Snaking yields near-optimal snaked clustering; for star schemas, a snaked lattice path is globally optimal with guarantees and TPC-D validation. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3087
Venue: SIGMOD
Year: 1999
Pagerank: 4.7316475e-05
Overall Rank: 7,412 | 48.49%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,838	Mesa: Geo-Replicated, Near Real-Time, Scalable Data Warehousing	2014	VLDB	0.00010353323
6,598	Oracle8i Index-Organized Table and its Application to New Domains	2000	VLDB	4.9934662e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 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.0011695087
121	Improved Query Performance with Variant Indexes	1997	SIGMOD	0.00045429472
217	A Class of Data Structures for Associative Searching	1984	PODS	0.00033533621
218	Aggregate-Query Processing in Data Warehousing Environments	1995	VLDB	0.00033489004
290	Linear Clustering of Objects with Multiple Attributes	1990	SIGMOD	0.00028845557
583	Answering Queries with Aggregation Using Views	1996	VLDB	0.00019705383
681	Materialized View Selection in a Multidimensional Database	1997	VLDB	0.0001818285
1,250	Fractals for Secondary Key Retrieval	1989	PODS	0.00013037936
1,485	On the Analysis of Indexing Schemes	1997	PODS	0.00011698762
1,890	Caching Multidimensional Queries Using Chunks	1998	SIGMOD	0.0001018961
2,481	Multiattribute Hashing Using Gray Codes.	1986	SIGMOD	8.6794604e-05
2,647	WATCHMAN: A Data Warehouse Intelligent Cache Manager	1996	VLDB	8.3750419e-05
5,010	A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries	1998	PODS	5.7545425e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
212	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00033997204
4,944	A Cost Model for Clustered Object-Oriented Databases	1995	VLDB	5.8120276e-05
6,073	Window Query-Optimal Clustering of Spatial Objects	1995	PODS	5.2215154e-05
7,042	Processing Star Queries on Hierarchically-Clustered Fact Tables	2002	VLDB	4.8483133e-05
6,655	Fast and Effective Distribution-Key Recommendation for Amazon Redshift	2020	VLDB	4.9693109e-05
11	Implementing Data Cubes Efficiently	1996	SIGMOD	0.0011695087
1,473	Fine-grained Partitioning for Aggressive Data Skipping	2014	SIGMOD	0.00011786148
9,907	Keep Your Distributed Data Warehouse Consistent at a Minimal Cost	2023	SIGMOD	4.2536148e-05
5,194	Clustering Techniques for Minimizing External Path Length	1996	VLDB	5.6318244e-05
769	Multi-Dimensional Database Allocation for Parallel Data Warehouses	2000	VLDB	0.00016862794