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: 3752
Venue: SIGMOD
Year: 2006
Pagerank: 6.9385476e-05
Overall Rank: 3,593 | 75.01%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Joshua Spiegel
2. Neoklis Polyzotis

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,547	Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions	2011	VLDB	0.00011442359
1,737	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00010720294
2,377	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	8.9402115e-05
3,924	A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation	2021	SIGMOD	6.6271553e-05
5,050	xPAD: A Platform for Analytic Data Flows	2013	SIGMOD	5.7340229e-05
5,369	Pyramid Sketch: a Sketch Framework for Frequency Estimation of Data Streams	2017	VLDB	5.5434712e-05
6,829	Depth Estimation for Ranking Query Optimization	2007	VLDB	4.9136064e-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
18	On Random Sampling over Joins	1999	SIGMOD	0.00092385438
33	BIRCH: An Efficient Data Clustering Method for Very Large Databases	1996	SIGMOD	0.00077324389
64	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063612837
211	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00033981214
222	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00032828302
277	Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications	1998	SIGMOD	0.00029311426
372	Selectivity Estimation using Probabilistic Models	2001	SIGMOD	0.00025354779
405	Approximate Query Processing Using Wavelets	2000	VLDB	0.00024057494
529	Self-tuning Histograms: Building Histograms Without Looking at Data	1999	SIGMOD	0.00020828852
553	Bifocal Sampling for Skew-Resistant Join Size Estimation	1996	SIGMOD	0.00020272061
842	Independence is Good: Dependency-Based Histogram Synopses for High-Dimensional Data	2001	SIGMOD	0.00016031973
1,064	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00014356481
3,419	Approximate XML Query Answers	2004	SIGMOD	7.1173416e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,510	Summarizing Relational Databases	2009	VLDB	0.00011606901
1,509	Discovering Queries based on Example Tuples	2014	SIGMOD	0.00011612727
3,511	Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs	2022	VLDB	7.0254052e-05
372	Selectivity Estimation using Probabilistic Models	2001	SIGMOD	0.00025354779
3,954	Efficiently Approximating Selectivity Functions using Low Overhead Regression Models	2020	VLDB	6.5926838e-05
3,143	Extracting and Analyzing Hidden Graphs from Relational Databases	2017	SIGMOD	7.4804326e-05
211	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00033981214
10,927	Computing A Well-Representative Summary of Conjunctive Query Results	2024	PODS	4.1945683e-05
1,796	Summary Graphs for Relational Database Schemas	2011	VLDB	0.00010524897
1,981	Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses	2018	VLDB	9.8687545e-05