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: 3269
Venue: SIGMOD
Year: 2001
Pagerank: 0.00016031973
Overall Rank: 842 | 94.15%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 44 of 44 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
224	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00032746205
325	The History of Histograms (abridged)	2003	VLDB	0.00027378328
449	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.00022846068
477	Model-Driven Data Acquisition in Sensor Networks	2004	VLDB	0.00022221803
627	Management of Probabilistic Data: Foundations and Challenges	2007	PODS	0.00018959005
684	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00018179769
758	Deep Unsupervised Cardinality Estimation	2020	VLDB	0.0001706608
910	NeuroCard: One Cardinality Estimator for All Tables	2021	VLDB	0.00015423056
1,547	Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions	2011	VLDB	0.00011442359
1,638	Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation	2022	VLDB	0.00011049779
1,703	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00010836769
1,737	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00010720294
1,974	BHUNT: Automatic Discovery of Fuzzy Algebraic Constraints in Relational Data	2003	VLDB	9.8866171e-05
2,118	Using Probabilistic Models for Data Management in Acquisitional Environments	2005	CIDR	9.5100739e-05
2,137	SASH: A Self-Adaptive Histogram Set for Dynamically Changing Workloads	2003	VLDB	9.4719326e-05
2,356	Consistently Estimating the Selectivity of Conjuncts of Predicates	2005	VLDB	8.9620762e-05
2,377	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	8.9402115e-05
2,549	GORDIAN: Efficient and Scalable Discovery of Composite Keys	2006	VLDB	8.5641554e-05
2,762	FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation	2021	VLDB	8.1585394e-05
3,113	Structure and Value Synopses for XML Data Graphs	2002	VLDB	7.5469926e-05
3,169	QueryFormer: A Tree Transformer Model for Query Plan Representation	2022	VLDB	7.4498425e-05
3,593	Graph-Based Synopses for Relational Selectivity Estimation	2006	SIGMOD	6.9385476e-05
3,651	Conditional Selectivity for Statistics on Query Expressions	2004	SIGMOD	6.8768678e-05
3,924	A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation	2021	SIGMOD	6.6271553e-05
3,990	FactorJoin: A New Cardinality Estimation Framework for Join Queries	2023	SIGMOD	6.5581983e-05
4,698	Deterministic Wavelet Thresholding for Maximum-Error Metrics	2004	PODS	5.9887317e-05
4,883	Content-Based Routing: Different Plans for Different Data	2005	VLDB	5.8545658e-05
5,065	Hierarchical Subspace Sampling: A Unified Framework for High Dimensional Data Reduction, Selectivity Estimation and Nearest Neighbor Search	2002	SIGMOD	5.7247716e-05
5,401	ALECE: An Attention-based Learned Cardinality Estimator for SPJ Queries on Dynamic Workloads	2024	VLDB	5.5285035e-05
5,783	Extended Wavelets for Multiple Measures	2003	SIGMOD	5.3289633e-05
6,368	Pre-training Summarization Models of Structured Datasets for Cardinality Estimation	2022	VLDB	5.0937722e-05
6,838	Capturing Data Uncertainty in High-Volume Stream Processing	2009	CIDR	4.9109732e-05
7,136	Distributed Top-N Query Processing with Possibly Uncooperative Local Systems	2003	VLDB	4.8220711e-05
7,221	Speeding Up End-to-end Query Execution via Learning-based Progressive Cardinality Estimation	2023	SIGMOD	4.797194e-05
7,854	dbET: Execution Time Distribution-based Plan Selection	2023	SIGMOD	4.6350172e-05
7,872	Probabilistic Database Summarization for Interactive Data Exploration	2017	VLDB	4.6307184e-05
8,869	Sharing-Aware Horizontal Partitioning for Exploiting Correlations During Query Processing	2010	VLDB	4.4320338e-05
9,524	Detecting Attribute Dependencies from Query Feedback	2007	VLDB	4.3310217e-05
9,691	Selectivity Estimation for Queries Containing Predicates over Set-Valued Attributes	2023	SIGMOD	4.3035354e-05
9,878	PRICE: A Pretrained Model for Cross-Database Cardinality Estimation	2025	VLDB	4.2656547e-05
10,149	CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations	2026	SIGMOD	4.1945683e-05
10,590	ACE: A Cardinality Estimator for Set-Valued Queries	2025	VLDB	4.1945683e-05
10,619	Data-Agnostic Cardinality Learning from Imperfect Workloads	2025	VLDB	4.1945683e-05
12,509	Adaptive Density Estimation	2006	VLDB	4.1945683e-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
64	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063612837
141	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00041786333
405	Approximate Query Processing Using Wavelets	2000	VLDB	0.00024057494
996	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD	0.00014741524

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,947	Aggregate Evaluability In Statistical Databases	1989	VLDB	4.1945683e-05
7,581	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS	4.7057641e-05
211	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00033981214
8,090	Probabilistic Histograms for Probabilistic Data	2009	VLDB	4.5888589e-05
1,120	Global Optimization of Histograms	2001	SIGMOD	0.00013856211
852	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00015941524
996	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD	0.00014741524
9,524	Detecting Attribute Dependencies from Query Feedback	2007	VLDB	4.3310217e-05
11,434	Data-Independent Space Partitionings for Summaries	2021	PODS	4.1945683e-05
141	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00041786333