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: 3086
Venue: SIGMOD
Year: 1999
Pagerank: 4.7314388e-05
Overall Rank: 7,433 | 48.30%
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,814	Mesa: Geo-Replicated, Near Real-Time, Scalable Data Warehousing	2014	VLDB	0.00010458107
6,597	Oracle8i Index-Organized Table and its Application to New Domains	2000	VLDB	4.9982502e-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.0011708144
121	Improved Query Performance with Variant Indexes	1997	SIGMOD	0.00045447517
216	A Class of Data Structures for Associative Searching	1984	PODS	0.00033542705
218	Aggregate-Query Processing in Data Warehousing Environments	1995	VLDB	0.00033503922
290	Linear Clustering of Objects with Multiple Attributes	1990	SIGMOD	0.00028919734
584	Answering Queries with Aggregation Using Views	1996	VLDB	0.0001971526
681	Materialized View Selection in a Multidimensional Database	1997	VLDB	0.00018203591
1,249	Fractals for Secondary Key Retrieval	1989	PODS	0.00013044758
1,488	On the Analysis of Indexing Schemes	1997	PODS	0.00011699446
1,887	Caching Multidimensional Queries Using Chunks	1998	SIGMOD	0.00010204659
2,485	Multiattribute Hashing Using Gray Codes.	1986	SIGMOD	8.6800526e-05
2,645	WATCHMAN: A Data Warehouse Intelligent Cache Manager	1996	VLDB	8.3829312e-05
5,013	A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries	1998	PODS	5.7598528e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
211	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00033981214
4,933	A Cost Model for Clustered Object-Oriented Databases	1995	VLDB	5.8205625e-05
6,076	Window Query-Optimal Clustering of Spatial Objects	1995	PODS	5.223696e-05
7,045	Processing Star Queries on Hierarchically-Clustered Fact Tables	2002	VLDB	4.8528709e-05
6,659	Fast and Effective Distribution-Key Recommendation for Amazon Redshift	2020	VLDB	4.9710856e-05
11	Implementing Data Cubes Efficiently	1996	SIGMOD	0.0011708144
1,477	Fine-grained Partitioning for Aggressive Data Skipping	2014	SIGMOD	0.00011770865
9,908	Keep Your Distributed Data Warehouse Consistent at a Minimal Cost	2023	SIGMOD	4.2576943e-05
5,196	Clustering Techniques for Minimizing External Path Length	1996	VLDB	5.6365164e-05
773	Multi-Dimensional Database Allocation for Parallel Data Warehouses	2000	VLDB	0.00016870159