Graph-Based Synopses for Relational Selectivity Estimation

Summary: TuG synopses model a relational DB as a semi-structured tuple-graph, with joins as traversals. Query selectivity for complex joins is estimated by traversing the compact TuG, with scalable construction under fixed storage budget and improved accuracy over prior summaries. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3814
Venue: SIGMOD
Year: 2006
Pagerank: 7.1244416e-05
Overall Rank: 3,788 | 74.02%
DOI: 10.1145/1142473.1142497

Incoming Non-self Citations Over Time

Authors

1. Joshua Spiegel (University of California Santa Cruz)
2. Neoklis Polyzotis (University of California Santa Cruz)

BibTeX Citation

@inproceedings{spiegel_sigmod06,
        title = {{Graph-Based Synopses for Relational Selectivity Estimation}},
        author = {Spiegel, Joshua and Polyzotis, Neoklis},
        series = {{SIGMOD} '06},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1142473.1142497},
        url = {https://dl.acm.org/doi/10.1145/1142473.1142497},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,071	Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions	2011	VLDB	0.00012322342
1,170	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00011827259
1,893	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	9.5269935e-05
3,086	A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation	2021	SIGMOD	7.7708642e-05
4,863	Pyramid Sketch: a Sketch Framework for Frequency Estimation of Data Streams	2017	VLDB	6.4740702e-05
5,319	xPAD: A Platform for Analytic Data Flows	2013	SIGMOD	6.2671857e-05
7,123	Depth Estimation for Ranking Query Optimization	2007	VLDB	5.6966694e-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
31	BIRCH: An Efficient Data Clustering Method for Very Large Databases	1996	SIGMOD	0.00050347119
35	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00048481081
54	On Random Sampling over Joins	1999	SIGMOD	0.00040810225
136	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00030123303
168	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00027541029
280	Selectivity Estimation using Probabilistic Models	2001	SIGMOD	0.00022454217
304	Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications	1998	SIGMOD	0.00021917388
307	Approximate Query Processing Using Wavelets	2000	VLDB	0.00021792475
448	Self-tuning Histograms: Building Histograms Without Looking at Data	1999	SIGMOD	0.00018292618
692	Independence is Good: Dependency-Based Histogram Synopses for High-Dimensional Data	2001	SIGMOD	0.00014919816
730	Bifocal Sampling for Skew-Resistant Join Size Estimation	1996	SIGMOD	0.00014539362
817	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00013823702
3,180	Approximate XML Query Answers	2004	SIGMOD	7.6599179e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,532	Summarizing Relational Databases	2009	VLDB
2	1,262	Discovering Queries based on Example Tuples	2014	SIGMOD
3	3,070	Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs	2022	VLDB
4	280	Selectivity Estimation using Probabilistic Models	2001	SIGMOD
5	3,162	Efficiently Approximating Selectivity Functions using Low Overhead Regression Models	2020	VLDB
6	2,854	Extracting and Analyzing Hidden Graphs from Relational Databases	2017	SIGMOD
7	136	Join Synopses for Approximate Query Answering	1999	SIGMOD
8	8,728	Computing A Well-Representative Summary of Conjunctive Query Results	2024	PODS
9	3,572	Summary Graphs for Relational Database Schemas	2011	VLDB
10	1,536	Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses	2018	VLDB