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: 3148
Venue: SIGMOD
Year: 1999
Pagerank: 5.5834218e-05
Overall Rank: 7,612 | 47.78%
DOI: 10.1145/304182.304186

Incoming Non-self Citations Over Time

Authors

1. H. V. Jagadish (AT&T; University of Illinois Urbana-Champaign)
2. Laks V. S. Lakshmanan (AT&T; Concordia University; Indian Institute of Technology Mumbai)
3. Divesh Srivastava (AT&T)

BibTeX Citation

@inproceedings{jagadish_sigmod99,
        title = {{Snakes and Sandwiches: Optimal Clustering Strategies for a Data Warehouse}},
        author = {Jagadish, H. V. and Lakshmanan, Laks V. S. and Srivastava, Divesh},
        series = {{SIGMOD} '99},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/304182.304186},
        url = {https://dl.acm.org/doi/10.1145/304182.304186},
        year = {1999}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,606	Mesa: Geo-Replicated, Near Real-Time, Scalable Data Warehousing	2014	VLDB	0.00010228576
6,879	Oracle8i Index-Organized Table and its Application to New Domains	2000	VLDB	5.7475732e-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.00071822821
104	Improved Query Performance with Variant Indexes	1997	SIGMOD	0.00033932213
198	Aggregate-Query Processing in Data Warehousing Environments	1995	VLDB	0.00025618616
253	A Class of Data Structures for Associative Searching	1984	PODS	0.00023200431
354	Linear Clustering of Objects with Multiple Attributes	1990	SIGMOD	0.00020355578
554	Answering Queries with Aggregation Using Views	1996	VLDB	0.00016580778
638	Materialized View Selection in a Multidimensional Database	1997	VLDB	0.000154719
1,202	Fractals for Secondary Key Retrieval	1989	PODS	0.00011672157
1,512	On the Analysis of Indexing Schemes	1997	PODS	0.00010536001
1,732	Caching Multidimensional Queries Using Chunks	1998	SIGMOD	9.9065981e-05
2,456	WATCHMAN: A Data Warehouse Intelligent Cache Manager	1996	VLDB	8.5526697e-05
2,742	Multiattribute Hashing Using Gray Codes.	1986	SIGMOD	8.1827223e-05
4,730	A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries	1998	PODS	6.5348792e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	136	Join Synopses for Approximate Query Answering	1999	SIGMOD
2	5,398	A Cost Model for Clustered Object-Oriented Databases	1995	VLDB
3	6,089	Window Query-Optimal Clustering of Spatial Objects	1995	PODS
4	7,162	Processing Star Queries on Hierarchically-Clustered Fact Tables	2002	VLDB
5	6,279	Fast and Effective Distribution-Key Recommendation for Amazon Redshift	2020	VLDB
6	1,044	Fine-grained Partitioning for Aggressive Data Skipping	2014	SIGMOD
7	11	Implementing Data Cubes Efficiently	1996	SIGMOD
8	10,063	Keep Your Distributed Data Warehouse Consistent at a Minimal Cost	2023	SIGMOD
9	5,888	Clustering Techniques for Minimizing External Path Length	1996	VLDB
10	995	Multi-Dimensional Database Allocation for Parallel Data Warehouses	2000	VLDB