PaperlayerView exact revision on arXiv

Source-linked AI summary

Semantics-aware Dataset Discovery from Data Lakes with Contextualized Column-based Representation Learning

Grace Fan, Jin Wang, Yuliang Li, Dan Zhang, Renée Miller

arXiv:2210.01922v2cs.DB

TL;DR

Table union search in data lakes needs semantic, contextual representations that do not depend on scarce labeled data. Starmie learns contextualized column embeddings with unsupervised contrastive learning, retrieves candidates through indexed similarity search, and verifies table-level unionability; it significantly outperforms existing solutions while accelerating query processing.

  • Problem

    Table union search must identify unionable tables despite incomplete metadata, limited contextual understanding, expensive verification, and the scarcity of labeled training data.

  • Method

    Starmie uses a pre-trained language-model encoder with multi-column contrastive learning, cosine-based column unionability scoring, and filter-and-verification search.

  • Results

    Starmie significantly outperforms existing table union search solutions, achieving a 6.8% improvement in both MAP and recall over the best state-of-the-art method.

  • Takeaways & Limitations

    Self-supervised contrastive learning improves table union search accuracy, while HNSW indexing supports the development of real-time data-lake search solutions.

Abstract

from arXiv · show

Dataset discovery from data lakes is essential in many real application scenarios. In this paper, we propose Starmie, an end-to-end framework for dataset discovery from data lakes (with table union search as the main use case). Our proposed framework features a contrastive learning method to train column encoders from pre-trained language models in a fully unsupervised manner. The column encoder of Starmie captures the rich contextual semantic information within tables by leveraging a contrastive multi-column pre-training strategy. We utilize the cosine similarity between column embedding vectors as the column unionability score and propose a filter-and-verification framework that allows exploring a variety of design choices to compute the unionability score between two tables accordingly. Empirical evaluation results on real table benchmark datasets show that Starmie outperforms the best-known solutions in the effectiveness of table union search by 6.8 in MAP and recall. Moreover, Starmie is the first to employ the HNSW (Hierarchical Navigable Small World) index for accelerate query processing of table union search which provides a 3,000X performance gain over the linear scan baseline and a 400X performance gain over an LSH index (the state-of-the-art solution for data lake indexing).

1 INTRODUCTION

Starmie addresses table union search in data lakes, where incomplete metadata and insufficient contextual understanding make it difficult to identify genuinely unionable tables. It combines unsupervised contextualized column representation learning with table-level scoring and scalable search.

  • Table union search aims to find all tables unionable with a query table, supporting dataset discovery beyond unreliable metadata keyword search.
  • Existing methods can misalign semantically similar columns because they often assess columns or relationships without sufficient whole-table context.
  • Starmie uses contrastive learning with pre-trained language models to learn contextualized column representations without labeled training instances.
  • Starmie computes column unionability from embedding similarity, aggregates it into table-level scores, and uses filter-and-verification to reduce expensive computations.
  • 6.8% improvement in both MAP and recall over the best state-of-the-art method, with a MAP of 99%.
  • HNSW indexing provides up to three orders of magnitude faster query time than linear scanning, while experiments report effectiveness, scalability, and memory efficiency.

2 OVERVIEW

Starmie solves table union search through an offline-to-online architecture: it learns and indexes column embeddings, retrieves candidate tables, and verifies their table-level unionability. The system supports top-k search while addressing the computational cost of matching tables at data-lake scale.

  • Starmie defines table unionability by combining a column encoder, a scoring function for column representations, and an aggregation mechanism across column pairs.
  • Table union search returns the top-k data-lake tables with the highest unionability scores relative to a query table.
  • Offline stage: Offline processing pre-trains a column representation model, embeds all data-lake columns, and stores the vectors in efficient indices for retrieval.
  • Representation learning: Starmie uses contrastive learning to train contextualized column encoders and stores their embeddings in vector indices such as HNSW.
  • Online stage: Online processing retrieves candidate tables through similar column embeddings and verifies and ranks them using table-level unionability scores.

3 LEARNING CONTEXTUALIZED COLUMN EMBEDDINGS

Starmie learns contextualized column embeddings with contrastive pre-training over augmented table views, using multi-column context to distinguish aligned, unaligned, and cross-table columns. It also preprocesses long tables to fit language-model input limits while preserving column semantics.

  • Contrastive learning: Starmie pretrains a column encoder with SimCLR-style contrastive learning, using semantics-preserving augmented views to bring related representations closer and separate distinct columns.The encoder is initialized from a pre-trained language model and produces high-dimensional column vectors.
  • Multi-column table encoder: The multi-column encoder serializes tables with separator tokens and extracts contextualized separator representations as column embeddings.Transformer self-attention makes each column representation depend on tokens from the surrounding table context.
  • Multi-column table encoder: Table-level augmentation samples rows or columns while preserving aligned column pairs for contrastive positive examples.The batch is formed from all columns in uniformly sampled tables, rather than independently augmenting each column.
  • Augmentation design: The drop_col augmentation operator performs best in the reported ablation study.The study compares augmentation operators applied at different table levels.
  • Multi-column table encoder: The multi-column objective treats aligned columns as positive pairs and unaligned same-table or cross-table columns as negative pairs, learning sensitivity to table context.This directly addresses the limitation that identical-looking values can have different meanings in different tables.
  • Table preprocessing: Because language models typically accept at most 512 sub-word tokens, Starmie selects rows, cells, or tokens to shorten long table inputs while preserving semantics.The preprocessing modes include row, cell, and token selection, with cell and token choices based on scoring procedures such as TF-IDF.

4 ONLINE QUERY PROCESSING

Starmie’s online query processing computes table unionability from column similarities and accelerates search through filtering, approximate indexing, and bound-based verification. The workflow replaces exhaustive matching with candidate generation and cheaper pruning steps while retaining exact verification for selected pairs.

  • Table-level matching: Column embeddings yield cosine-based column unionability scores, which are aggregated as a maximum weighted bipartite matching between table columns.A threshold τ removes edges between sufficiently dissimilar columns before matching.
  • Verification pruning: In the illustrative example, the exact maximum matching scores 2.15, whereas the greedy upper bound is 3.The example uses a threshold τ of 0.5 and matches three column pairs for the exact score.
  • Query-processing challenge: Linear scanning is expensive because weighted bipartite matching costs O(n^3 log n) for each table pair.Scalable search must reduce both the number of accessed tables and the cost of verifying each pair.
  • Filter and verification: The filter-and-verification framework first identifies candidate tables, then prunes or verifies candidates to reduce expensive unionability computations.Algorithm 3 outputs the top-k unionable tables using the query table, data lake, desired result count, and similarity threshold.
  • Candidate generation: LSH and HNSW indexes support approximate high-dimensional similarity search for retrieving tables containing columns similar to query columns.Approximate indexes may introduce false negatives, but experiments report effectiveness loss within a reasonable range and query-time reductions of one to three orders of magnitude.
  • Verification pruning: Greedy upper and lower bounds avoid full bipartite matching when estimating whether candidate tables merit exact verification.Both bounds use descending edge weights and cost O(|E| log |E| + n), while the upper bound relaxes matching constraints and the lower bound preserves them.

5 EXPERIMENTS

Across real-world benchmarks, Starmie improves table-union effectiveness, scalability, and downstream data discovery, with HNSW providing substantial query-speed gains while preserving effectiveness.

  • Effectiveness: Starmie outperforms prior methods across all three ground-truth benchmarks, achieving highest MAP@10 of 99.3% and R@10 of 73.7% on SANTOS Small.It also surpasses Sherlock by 0.7% on TUS Small and SATO by 4% on TUS Large in MAP@k.
  • Effectiveness: Starmie consistently leads baselines across precision and recall as k increases, remaining closest to IDEAL on all benchmarks.R@10 is 1.8% below IDEAL on SANTOS Small, while R@60 is 18.8% and 14.1% below IDEAL on TUS Small and TUS Large.
  • Robustness: Starmie remains strong across table arity, cardinality, and numerical-column settings, while SingleCol performs substantially worse under all settings.As row counts increase, competing methods generally decline, whereas Starmie remains consistently high.
  • Scalability: HNSW achieves around 300 ms average query time on SANTOS Large, running 220X faster than Linear and 11X faster than LSH.The HNSW design preserves effectiveness as much as, or better than, LSH; Starmie variants use around 3-7% space overhead.
  • Downstream applications: Starmie improves downstream machine-learning feature discovery, producing a 14.75% MSE reduction across 15/25 tasks and an average 20.64% improvement.In one case, joining a Starmie-retrieved table reduces MSE from 0.1598 to 0.1198.
  • Downstream applications: Starmie produces higher-quality semantic column clusters, reaching purity 51.19 versus 30.5 for Sherlock and 37.36 for SATO.The clustering output contains 2,297 clusters with an average size of 51.96.

6 RELATED WORK

Related work spans keyword-based dataset search, schema and relationship discovery, table union search, and learned table representations. Existing systems use syntactic similarity, knowledge bases, ontologies, word embeddings, or supervised representation learning across these tasks.

  • Dataset discovery: Earlier dataset-discovery systems primarily used keyword search, schema complement, or knowledge bases to identify information and relationships among datasets.Examples include Octopus and InfoGather for schema complement, and Aurum, S3D, and Tableminer+ for dataset relationships.
  • Related-table search: Related-table discovery includes joinable-table search and table union search, with prior methods using syntactic similarity, overlap, word embeddings, and optimized indexing.Table union search has been addressed by systems including D3L and SANTOS, with SANTOS described as state of the art in this area.
  • Representation learning: Representation-learning approaches include supervised table and column encoders, pretrained language models, and benchmark datasets for table-related tasks.Sherlock and Sato learn vector representations using supervised features, while TURL applies pretrained language models to web-table tasks.

7 CONCLUSION AND FUTURE WORK

Starmie uses contextualized column representations and contrastive learning for table union search, with experiments showing improved accuracy and efficient preprocessing choices. The conclusion also identifies a limitation in default table preprocessing and motivates further exploration.

  • Contributions: Starmie combines contrastive representation learning with a multi-column Transformer encoder to capture contextual information for table union search.The framework learns contextualized column embeddings without labeled training instances.
  • Findings: Self-supervised contrastive learning improves table union search accuracy and shows promise for joinable table search and column clustering.The authors connect this promise to settings where labeled training data is expensive to collect and generalize.
  • Future work: Default table preprocessing can fail to capture the most relevant information for downstream tasks, motivating a tunable design space for optimization.The paper assumes column ordering because table union search typically relies on column alignment, then explores alternative preprocessing choices.
  • Ablation study: The drop_col augmentation operator achieves a MAP@k of 98% on the SANTOS Small benchmark and is used for effectiveness experiments.The study compares augmentation operators at different table levels.

B.2 Sampling Methods

The sampling study favors column-ordered, TF-IDF-based preprocessing, with tfidf_entity achieving the strongest reported MAP@k on SANTOS Small. These results support using deterministic column-oriented sampling for the effectiveness experiments.

  • Row-ordered vs. column-ordered: Column-ordered sampling outperforms row_ordered sampling, with tfidf_entity reaching 99.3% MAP@k versus 97.9% for row_ordered.The comparison confirms the study’s original column-ordering hypothesis.
  • Token/cell scoring functions: TF-IDF-based methods, particularly tfidf_entity, outperform simpler scoring methods such as head and random.The study compares token and cell scoring functions across the sampling design space.
  • Deterministic vs. non-deterministic: tfidf_entity outperforms random, which achieves a MAP@k of 97.3%, supporting the conclusion that deterministic methods are more effective.All evaluated methods except random are deterministic.
  • Row alignment: Column alignment remains more effective than row alignment, although the design space requires further experimentation.tfidf_row and row_ordered preserve row alignment in the comparison.
  • Sampling performance: tfidf_entity achieves the best MAP@k of 99.3% among the evaluated sampling methods on SANTOS Small.The method samples cells in a column using average TF-IDF scores over their tokens.

C IN-DEPTH ANALYSIS ON EFFECTIVENESS

In-depth analyses on the TUS benchmarks show that Starmie outperforms the baselines across table characteristics. On TUS Large, its MAP@k remains consistently high as baseline performance declines for some table conditions.

  • TUS Small: Starmie outperforms SATO and Sherlock on TUS Small and remains robust across buckets containing different table characteristics.The analyses divide tables into five buckets and examine MAP@k across conditions.
  • TUS Large: On TUS Large, Starmie outperforms the baselines consistently across buckets and table sizes and column types.Baseline MAP@k drops as rows or numeric-column percentages increase, while Starmie MAP@k remains consistently high.

D FULL RESULTS FOR EFFICIENCY EXPERIMENTS

The efficiency experiments show that indexing and pruning techniques substantially reduce query time while preserving Starmie’s performance, and they are also evaluated with baseline embeddings.

  • Starmie efficiency: Efficiency techniques provide substantial speedups while preserving Starmie’s performance.Table 5 evaluates their effects on both runtime and effectiveness scores.
  • Baseline embeddings: The expanded experiment applies the efficiency techniques to SATO, Sherlock, and SingleCol embeddings on the SANTOS labeled benchmark.Table 8 reports their impact on query time and performance.

D.2 k-Scalability on WDC Benchmark

Across SANTOS Large and 1M WDC tables, HNSW provides the fastest query times as k increases, while Starmie remains generally robust to larger result sets.

  • HNSW has the fastest query time as k increases, followed by LSH, Pruning, and Linear across the scalability experiments.The experiments cover SANTOS Large and 1M WDC tables, with k increasing from 10 to 60 on SANTOS Large.
  • Figures 14 and 15 analyze Starmie, SATO, and Sherlock while varying columns, rows, and numerical-column percentages on TUS Small and TUS Large.
  • Figure 16 evaluates scalability on 1M WDC tables while varying k.
  • Starmie is generally robust in query time as the number of results to return increases.

E DISCOVERED COLUMN CLUSTERS

Starmie discovers column clusters with finer-grained semantic types than the original 78-type taxonomy, including distinct clusters for schools, grocery stores, and songs.

  • Starmie discovers finer-grained semantic clusters that are not present in the original 78 types.The example clusters correspond to names of schools, food or grocery stores, and songs.
  • The three example clusters have majority original types of type, name, and artist, respectively.
  • Cluster quality is evaluated by purity after constructing a similarity graph and clustering connected components.Columns are connected when similarity exceeds τ = 0.6, with cluster sizes restricted to around 50 for comparison.

F FULL RESULTS FOR DATA DISCOVERY FOR ML

The data-discovery experiments evaluate Starmie and alternative methods on rating-prediction tasks using WDC tables, with contextualized column embeddings used to select semantically relevant data.

  • Table 11 reports MSE scores for 25 rating-prediction tasks built from 4,130 WDC tables with at least 50 rows.Each dataset uses a 4:1 training-to-testing split, and reductions measure improvement against NoJoin.
  • The baselines include NoJoin, Jaccard similarity, and token overlap for selecting data to join with the query table.
  • Starmie’s discovered clusters contain finer-grained examples such as school names, grocery-store names, and song names than the original ground-truth types.
  • Starmie uses learned contextualized column embeddings to measure similarities and identify semantically relevant tables for the query.The embeddings capture the table context of each column.
  • Starmie accounts for similarity between the target column and columns from the data-lake table.This uses the source target column, “Rating,” in the similarity computation.
  • The implementation de-duplicates the data-lake table on the join column before performing a left join.This preserves the exact number of rows in the query table.
Loading 2210.01922v2…