Independence is Good: Dependency-Based Histogram Synopses for High-Dimensional Data

Summary: Dependency-based histogram synopses for high-dimensional data via interaction models capturing correlations. Low-dimensional marginals guided by the model approximate the joint, outperforming independence and aiding other space-partitioning methods. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h5055d6d35eff17e5
Venue: SIGMOD
Year: 2001
Pagerank: 0.00014680907
Overall Rank: 701 | 95.29%
DOI: 10.1145/375663.375685

Incoming Non-self Citations Over Time

Authors

1. Amol Deshpande (University of California Berkeley)
2. Minos Garofalakis (AT&T)
3. Rajeev Rastogi (AT&T)

BibTeX Citation

@inproceedings{deshpande_sigmod01,
        title = {{Independence is Good: Dependency-Based Histogram Synopses for High-Dimensional Data}},
        author = {Deshpande, Amol and Garofalakis, Minos and Rastogi, Rajeev},
        series = {{SIGMOD} '01},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/375663.375685},
        url = {https://dl.acm.org/doi/10.1145/375663.375685},
        year = {2001}
}

Incoming Citations (Sorted by Pagerank)

Showing 44 of 44 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
160	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00027837289
255	The History of Histograms (abridged)	2003	VLDB	0.00022981861
343	Model-Driven Data Acquisition in Sensor Networks	2004	VLDB	0.00020519525
372	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.00019720059
406	Deep Unsupervised Cardinality Estimation	2020	VLDB	0.00019045544
512	NeuroCard: One Cardinality Estimator for All Tables	2021	VLDB	0.00017050173
569	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00016245271
587	Management of Probabilistic Data: Foundations and Challenges	2007	PODS	0.00015933201
982	Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation	2022	VLDB	0.00012714044
1,060	Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions	2011	VLDB	0.00012224575
1,064	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00012202282
1,156	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00011777105
1,662	BHUNT: Automatic Discovery of Fuzzy Algebraic Constraints in Relational Data	2003	VLDB	9.9465656e-05
1,891	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	9.4184294e-05
1,929	Consistently Estimating the Selectivity of Conjuncts of Predicates	2005	VLDB	9.3546057e-05
2,004	FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation	2021	VLDB	9.2065719e-05
2,140	SASH: A Self-Adaptive Histogram Set for Dynamically Changing Workloads	2003	VLDB	8.9682092e-05
2,250	QueryFormer: A Tree Transformer Model for Query Plan Representation	2022	VLDB	8.7533306e-05
2,291	GORDIAN: Efficient and Scalable Discovery of Composite Keys	2006	VLDB	8.6872323e-05
2,415	Using Probabilistic Models for Data Management in Acquisitional Environments	2005	CIDR	8.4985276e-05
2,846	FactorJoin: A New Cardinality Estimation Framework for Join Queries	2023	SIGMOD	7.9453616e-05
3,052	A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation	2021	SIGMOD	7.7052471e-05
3,184	Structure and Value Synopses for XML Data Graphs	2002	VLDB	7.5577589e-05
3,361	Conditional Selectivity for Statistics on Query Expressions	2004	SIGMOD	7.3760492e-05
3,851	Graph-Based Synopses for Relational Selectivity Estimation	2006	SIGMOD	6.9785886e-05
4,106	Content-Based Routing: Different Plans for Different Data	2005	VLDB	6.8032891e-05
4,311	ALECE: An Attention-based Learned Cardinality Estimator for SPJ Queries on Dynamic Workloads	2024	VLDB	6.6727978e-05
4,416	Deterministic Wavelet Thresholding for Maximum-Error Metrics	2004	PODS	6.6089486e-05
5,785	Extended Wavelets for Multiple Measures	2003	SIGMOD	5.9961546e-05
5,840	Pre-training Summarization Models of Structured Datasets for Cardinality Estimation	2022	VLDB	5.9737703e-05
6,032	Hierarchical Subspace Sampling: A Unified Framework for High Dimensional Data Reduction, Selectivity Estimation and Nearest Neighbor Search	2002	SIGMOD	5.9097667e-05
6,660	Speeding Up End-to-end Query Execution via Learning-based Progressive Cardinality Estimation	2023	SIGMOD	5.7178404e-05
6,791	dbET: Execution Time Distribution-based Plan Selection	2023	SIGMOD	5.6811782e-05
6,846	Capturing Data Uncertainty in High-Volume Stream Processing	2009	CIDR	5.6662335e-05
7,320	Distributed Top-N Query Processing with Possibly Uncooperative Local Systems	2003	VLDB	5.5538431e-05
8,363	Probabilistic Database Summarization for Interactive Data Exploration	2017	VLDB	5.3472423e-05
9,124	Sharing-Aware Horizontal Partitioning for Exploiting Correlations During Query Processing	2010	VLDB	5.2253914e-05
9,845	Detecting Attribute Dependencies from Query Feedback	2007	VLDB	5.1213286e-05
9,976	Selectivity Estimation for Queries Containing Predicates over Set-Valued Attributes	2023	SIGMOD	5.1031384e-05
10,216	PRICE: A Pretrained Model for Cross-Database Cardinality Estimation	2025	VLDB	5.0584922e-05
10,294	Data-Agnostic Cardinality Learning from Imperfect Workloads	2025	VLDB	5.0431863e-05
10,627	CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations	2026	SIGMOD	4.9793485e-05
11,257	ACE: A Cardinality Estimator for Set-Valued Queries	2025	VLDB	4.9793485e-05
12,992	Adaptive Density Estimation	2006	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00047731453
103	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00033894985
309	Approximate Query Processing Using Wavelets	2000	VLDB	0.00021384073
866	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD	0.00013381261

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,432	Aggregate Evaluability in Statistical Databases	1989	VLDB
2	138	Join Synopses for Approximate Query Answering	1999	SIGMOD
3	7,493	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS
4	8,206	Probabilistic Histograms for Probabilistic Data	2009	VLDB
5	1,687	Global Optimization of Histograms	2001	SIGMOD
6	742	Dynamic Multidimensional Histograms	2002	SIGMOD
7	866	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD
8	9,845	Detecting Attribute Dependencies from Query Feedback	2007	VLDB
9	11,939	Data-Independent Space Partitionings for Summaries	2021	PODS
10	103	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB