Correlation Sketches for Approximate Join-Correlation Queries

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 𝑄 and a join column 𝐾 𝑄 from a query table T 𝑄 , retrieve tables T 𝑋 in a dataset collection such that T 𝑋 is joinable with T 𝑄 on 𝐾 𝑄 and there is a column 𝐶 ∈ T 𝑋 such that 𝑄 is correlated with 𝐶. A naïve approach to evaluate these queries, which first finds joinable tables and then explicitly joins and computes correlations between 𝑄 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 joincorrelation 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.