Correlation Sketches for Approximate Join-Correlation Queries

Summary: Introduces join-correlation queries for data augmentation: find TX joinable with TQ on KQ where a TX column C correlates to Q. Proposes correlation sketches to index tables with estimates and scoring to rank results; experiments validate accuracy. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6323
Venue: SIGMOD
Year: 2021
Pagerank: 7.6215176e-05
Overall Rank: 3,228 | 77.86%
DOI: 10.1145/3448016.3458456

Incoming Non-self Citations Over Time

Authors

1. Aécio Santos (New York University)
2. Aline Bessa (New York University)
3. Fernando Chirigati (Springer Nature)
4. Christopher Musco (New York University)
5. Juliana Freire (New York University)

BibTeX Citation

@inproceedings{santos_sigmod21,
        title = {{Correlation Sketches for Approximate Join-Correlation Queries}},
        author = {Santos, Aécio and Bessa, Aline and Chirigati, Fernando and Musco, Christopher and Freire, Juliana},
        series = {{SIGMOD} '21},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3448016.3458456},
        url = {https://dl.acm.org/doi/10.1145/3448016.3458456},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,735	Leva: Boosting Machine Learning Performance with Relational Embedding Data Augmentation	2022	SIGMOD	6.5315782e-05
5,300	Towards Distribution-aware Query Answering in Data Markets	2022	VLDB	6.2751506e-05
5,479	MATE: Multi-Attribute Table Extraction	2022	VLDB	6.204351e-05
5,510	Responsible Data Integration: Next-generation Challenges	2022	SIGMOD	6.1919207e-05
6,054	Causal Data Integration	2023	VLDB	5.9932261e-05
7,498	Stingy Sketch: A Sketch Framework for Accurate and Fast Frequency Estimation	2022	VLDB	5.6031077e-05
7,716	Double-Anonymous Sketch: Achieving Top-K-fairness for Finding Global Top-K Frequent Items	2023	SIGMOD	5.5605526e-05
8,252	Sampling Methods for Inner Product Sketching	2024	VLDB	5.4574671e-05
8,658	Nexus: Correlation Discovery over Collections of Spatio-Temporal Tabular Data	2024	SIGMOD	5.3904679e-05
8,801	Effective Entity Augmentation By Querying External Data Sources	2023	VLDB	5.3687048e-05
9,773	Fair and Actionable Causal Prescription Ruleset	2025	SIGMOD	5.2209769e-05
10,431	AutoDDG: Automated Dataset Description Generation using Large Language Models	2026	SIGMOD	5.093636e-05
10,882	CatDB: Data-catalog-guided, LLM-based Generation of Data-centric ML Pipelines	2025	VLDB	5.093636e-05
11,062	Data Discovery in Data Lakes: Operations, Indexes, Systems	2025	VLDB	5.093636e-05
11,262	Enriching Relations with Additional Attributes for ER	2024	VLDB	5.093636e-05
11,303	Navigating Data Repositories: Utilizing Line Charts to Discover Relevant Datasets	2024	VLDB	5.093636e-05
11,374	Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation	2023	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 23 of 23 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
75	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00037277061
76	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00037054261
84	Learned Cardinalities: Estimating Correlated Joins with Deep Learning	2019	CIDR	0.00035838391
91	WebTables: Exploring the Power of Tables on the Web	2008	VLDB	0.00034838835
136	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00030123303
257	The History of Histograms (abridged)	2003	VLDB	0.00023154793
288	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.00022296371
401	Deep Unsupervised Cardinality Estimation	2020	VLDB	0.00019092557
689	On Synopses for Distinct-Value Estimation Under Multiset Operations	2007	SIGMOD	0.00014940023
694	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR	0.00014911698
730	Bifocal Sampling for Skew-Resistant Join Size Estimation	1996	SIGMOD	0.00014539362
737	Join Size Estimation Subject to Filter Conditions	2015	VLDB	0.00014490983
779	JOSIE: Overlap Set Similarity Search for Finding Joinable Tables in Data Lakes	2019	SIGMOD	0.00014092047
878	Table Union Search on Open Data	2018	VLDB	0.00013463374
963	The Data Civilizer System	2017	CIDR	0.00012935145
1,121	ARDA: Automatic Relational Data Augmentation for Machine Learning	2020	VLDB	0.00012093059
1,303	Finding Related Tables in Data Lakes for Interactive Data Science	2020	SIGMOD	0.0001123653
1,495	LSH Ensemble: Internet-Scale Domain Search	2016	VLDB	0.00010571481
1,516	Cardinality Estimation: An Experimental Survey	2018	VLDB	0.00010520885
1,664	Two-Level Sampling for Join Size Estimation	2017	SIGMOD	0.00010070362
2,197	Multi-Dimensional Clustering: A New Data Layout Scheme in DB2	2003	SIGMOD	8.9684812e-05
3,481	Tighter Estimation using Bottom k Sketches	2008	VLDB	7.376137e-05
5,743	Joins on Samples: A Theoretical Guide for Practitioners	2020	VLDB	6.1025457e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,040	Leveraging Set Relations in Exact Set Similarity Join	2017	VLDB
2	4,114	Optimizing Machine Learning Inference Queries with Correlative Proxy Models	2022	VLDB
3	12,386	Efficient Rank Join with Aggregation Constraints	2011	VLDB
4	739	Finding Related Tables	2012	SIGMOD
5	10,438	CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations	2026	SIGMOD
6	8,965	Sharing-Aware Horizontal Partitioning for Exploiting Correlations During Query Processing	2010	VLDB
7	9,882	Demonstration of Accelerating Machine Learning Inference Queries with Correlative Proxy Models	2022	VLDB
8	10,186	Accelerating Approximate Analytical Join Queries over Unstructured Data with Statistical Guarantees	2026	SIGMOD
9	2,302	Correlation Maps: A Compressed Access Method for Exploiting Soft Functional Dependencies	2009	VLDB
10	9,724	Approximate Sketches	2024	SIGMOD