# Correlation Sketches for Approximate Join-Correlation Queries

arXiv: https://arxiv.org/abs/2104.03353 · HTML: https://mlsanity.com/paper/2104.03353/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Apr 2021.

## Built on by (most cited first, 8 of 8)

- [TabLib: A Dataset of 627M Tables with Context](https://mlsanity.com/paper/2310.07875/) (2023)
- [Retrieve, Merge, Predict: Augmenting Tables with Data Lakes](https://mlsanity.com/paper/2402.06282/) (2024)
- [METAM: Goal-Oriented Data Discovery](https://mlsanity.com/paper/2304.09068/) (2023)
- [Snoopy: Effective and Efficient Semantic Join Discovery via Proxy Columns](https://mlsanity.com/paper/2502.16813/) (2025)
- [TabSketchFM: Sketch-based Tabular Representation Learning for Data Discovery over Data Lakes](https://mlsanity.com/paper/2407.01619/) (2024)
- [MYCROFT: Towards Effective and Efficient External Data Augmentation](https://mlsanity.com/paper/2410.08432/) (2024)
- [Exploiting LLMs for Automatic Hypothesis Assessment via a Logit-Based Calibrated Prior](https://mlsanity.com/paper/2506.03444/) (2025)
- [MosaicJoin: Compact Semantic Sketches for Value-Level Join Discovery](https://mlsanity.com/paper/2607.21781/) (2026)

## Abstract (arXiv)

The increasing availability of structured datasets, from Web tables and open-data portals to enterprise data, opens up opportunities~to enrich analytics and improve machine learning models through relational data augmentation. In this paper, we introduce a new class of data augmentation queries: join-correlation queries. Given a column Q and a join column KQ from a query table TQ, retrieve tables TX in a dataset collection such that TX is joinable with TQ on KQ and there is a column C ∈ TX such that Q is correlated with C. A na"ive approach to evaluate these queries, which first finds joinable tables and then explicitly joins and computes correlations between Q and all columns of the discovered tables, is prohibitively expensive. To efficiently support correlated column discovery, we 1) propose a sketching method that enables the construction of an index for a large number of tables and that provides accurate estimates for join-correlation queries, and 2) explore different scoring strategies that effectively rank the query results based on how well the columns are correlated with the query. We carry out a detailed experimental evaluation, using both synthetic and real data, which shows that our sketches attain high accuracy and the scoring strategies lead to high-quality rankings.