We further conduct case studies to show the flexibility and generality of our proposed framework in other dataset discovery applications.
The rest of the paper is organized as follows.
Section  introduces the background and the overall architecture.
Section  proposes the contrastive learning based approaches to train the column encoders.
Section  develops the query processing techniques to retrieval top-k unionable tables.
Section  reports the experimental results.
We discuss related works in Section  and conclude in Section .
Overview
Problem definition
In this paper, we define the table union search problem following previous studies [1]}, [2]}, [3]}.
We start from the data model.
A data lake consists of a collection of tables \(\mathcal {T}\) .
Each table \(T \in \mathcal {T}\)  consists of several columns \(\lbrace t_1, \dots , t_m\rbrace \)  where each column \(t_i\)  can be from different domains.
Here \(m\)  is the number of columns in table \(T\)  (denoted as \(|T| = m\) ).
We will use the notation \(T\)  to denote both the table and its set of columns if there is no ambiguity.
If two columns are semantically close to each other, we regard them as unionable columns.
To determine the unionability between two columns, following previous studies, we employ column encoders to generate the representations of columns.
Then the column unionability score can be computed to measure the relevance between those representations.
A column encoder \(\mathcal {M}\)  takes a column \(t\)  as input and outputs \(\mathcal {M}(t)\)  as the representation.
Given two columns \(t_i\)  and \(t_j\) , the column unionability score is computed as \(\mathcal {F}(\mathcal {M}(t_i), \mathcal {M}(t_j))\) ,
where \(\mathcal {F}\)  is a scoring function between two column representations.
Take a previous study [2]} as an example, the column encoder \(\mathcal {M}\)  for the set, semantic and natural language domain is bag of tokens, bag of tokens plus a mapping from tokens to classes in a knowledge base, and bag of word embedding, respectively;
while the scoring function \(\mathcal {F}\)  is the Jaccard similarity between sets of tokens, that between sets of tokens after transformation and cosine similarity between average word embeddings, respectively.
We will show in Section  how \(\mathsf {Starmie}\)  leverages contrastive learning to obtain an encoder \(\mathcal {M}\) 
that captures richer semantics in columns in the form of contextualized column embeddings .
Based on the column unionability scores, we then compute the table unionability score between two tables, which is obtained by aggregating the column unionability scores introduced above.
Given two tables \(S\)  and \(T\) , we define a table unionability scoring function as \(U = \lbrace \mathcal {F}, \mathcal {M}, \mathcal {A}\rbrace \) , where \(\mathcal {M}\)  and \(\mathcal {F}\)  are the column encoder and scoring function for two column representations, respectively.
Here \(\mathcal {A}\)  is a mechanism to aggregate the column unionability scores between all pairs of columns from the two tables.
We will introduce the details of \(\mathcal {A}\)  later in Section .
Following the above discussions, we can formally define the table union search problem as a top-k search problem as Definition REF :
[Table Union Search] 
Given a collection of data lake tables \(\mathcal {T}\)  and a query table \(S\) , top-k table union search aims at finding a subset \(\mathcal {S}\subseteq \mathcal {T}\)  where \(|\mathcal {S}| = k\)  and \(\forall T \in \mathcal {S}\)  and \(T^{\prime } \in \mathcal {T}- \mathcal {S}\) , we have \(U(S, T) \ge U(S, T^{\prime })\) .

System architecture
<FIGURE>Figure REF  shows the overall architecture of \(\mathsf {Starmie}\)  that solves table union search in two stages: offline and online.
During the offline stage, \(\mathsf {Starmie}\)  pre-trains a column representation model that encodes columns
of data lake tables into dense high-dimensional vectors (i.e., column embeddings).
Then, we apply the trained model to all data lake tables to obtain the column embeddings via model inference.
We store the embedding vectors in efficient vector indices for online retrieval.
A key challenge for the offline stage is to train high-quality column encoders for capturing the semantics of tabular data.
In \(\mathsf {Starmie}\) , we follow a recent trend [5]}, [6]}, [7]} of
table representation learning that encodes tabular data using pre-trained language models (LMs).
Pre-trained LMs have achieved state-of-the-art performance on table understanding tasks
such as column type and relation type annotation [7]}.
However, the good performance of pre-trained LMs requires fine-tuning on high-quality labeled datasets, which are always not available in table search applications such as table union search.
Utilizing the pre-trained LMs off-the-shelf is also problematic as the column embeddings cannot capture (ir-)relevance between columns or the contextual information within tables.
To this end, in Section , we propose a contrastive learning framework for learning high-dimensional column representations in fully unsupervised manner.
We combine the framework with a multi-column table model that captures column semantics from the column values while taking the table context into account.
Then we apply the column encoder to all tables in the data lake to convert the table into a collection of embedding vectors.
During the online stage, Given an input query table, we retrieve a set of candidate tables from the vector indices by searching for data lake column embeddings of high column-level similarity with the input columns Following the settings of previous studies, we assume all embedding vectors (and the index if any) are in memory..
\(\mathsf {Starmie}\)  then applies a verification step for checking and ranking the candidates for the top-\(k\)  tables with the highest table-level unionability scores.
The first challenge for the online stage is how to efficiently search for unionable columns.
This is not a trivial task due to the massive size of data lakes.
We address this challenge by allowing different design choices of state-of-the-art high-dimensional vector indices.
Yet another challenge is designing a table unionability function that can effectively aggregate the column unionability scores.
We employ weighted bipartite graph matching as the solution for it.
To address its limitation of high computation complexity, we reduce the number of expensive calls to the exact matching algorithm by deducing lower and upper bounds of the matching score.
More details will be presented in Section .

Learning contextualized column embeddings
We now describe the offline stage for training high-quality column encoders.
The encoder pre-processes tables into sequence inputs and uses
a pre-trained LM to encode each column into a high-dimensional vector.
We describe a novel contrastive learning approach for training the encoder
in Section REF . We also generalize it to multi-column encoders
for contextualized embeddings in Section REF .
We then discuss how to optimize table pre-processing in Section REF .
Contrastive Learning Framework
Contrastive learning is a self-supervision approach that
learns data representations where similar data items are close while distinct data items are far apart.
In \(\mathsf {Starmie}\) , we adopt the SimCLR algorithm [9]}
which was recently shown to be effective in computer vision and NLP applications.
Figure REF  illustrates the high-level idea of the algorithm.
The goal is to learn a column encoder \(\mathcal {M}\)  for tables.
For simplicity, we first assume that \(\mathcal {M}\)  takes a single column as input at a time.
The high-level idea of the algorithm is to connect representations of the same or unionable columns in their representation space while separating representations of distinct columns.
To achieve the first goal, the algorithm leverages a data augmentation operator \(\mathsf {op}\) .
Intuitively, given a batch of columns \(X = \lbrace x_1, \dots , x_N\rbrace \)  where \(N\)  is the batch size, \(\mathsf {op}\)  transforms \(X\)  into a semantics-preserving view \(X_{\mathsf {aug}}\) .
For a single-column, one choice of the augmentation operator can be uniform sampling of the values from the original column.
Then \(\mathcal {M}\)  can encode the batches \(X\)  (also \(X_{\mathsf {ori}}\)  which is a copy of \(X\)  in the figure)
and \(X_{\mathsf {aug}}\)  into column embedding vectors \(\vec{Z}_{\mathsf {ori}}\)  and \(\vec{Z}_{\mathsf {aug}}\)  respectively.
Note that \(\vec{Z}_{\mathsf {ori}}\)  and \(\vec{Z}_{\mathsf {aug}}\)  are both matrices with size \(N\)  times
the dimension of embedding vector (e.g., 768 for BERT).
Next, the algorithm leverages a contrastive loss function to connect the semantics-preserving views of columns and separate representations of distinct columns.
More specifically, let \(\vec{Z} = \lbrace \vec{z}_i\rbrace _{1 \le i \le 2N}\)  be the concatenation of the two encoded views \(\vec{Z}_{\mathsf {ori}}\)  and \(\vec{Z}_{\mathsf {aug}}\)  of batch \(X\)  introduced above.
Here \(\vec{z}_i\)  is the \(i\) -th element of \(\vec{Z}_{\mathsf {ori}}\)  for \(i \le N\)  and the \((i-N)\) -th element of \(\vec{Z}_{\mathsf {aug}}\)  for \(i > N\) .
We first define a single-pair loss \(\ell (i, j)\)  for an element pair \((\vec{z}_i, \vec{z}_j)\)  to be Equation REF .
\(\ell (i, j)=-\log \frac{\exp \left(\operatorname{sim}\left(\vec{z}_{i}, \vec{z}_{j}\right) / \tau \right)}{\sum _{k=1}^{2 N} {1}_{[k \ne i]} \exp \left(\operatorname{sim}\left(\vec{z}_{i}, \vec{z}_{k}\right) / \tau \right)}\) 
where \(\operatorname{sim}\) is a similarity function such as cosine and \(\tau \)  is a temperature hyper-parameter in the range \((0, 1]\) .
We fix \(\tau \)  to be 0.07 empirically.
Intuitively, by minimizing this loss for a pair \((\vec{z}_i, \vec{z}_j)\)  that are views of the same columns, we
(i) maximize the similarity score \(\operatorname{sim}\left(\vec{z}_{i}, \vec{z}_{j}\right)\)  in the numerator and
(ii) minimize \(\vec{z}_i\) 's similarities with all the other elements in the denominator.
Note that one assumption that the algorithm relies on is that for (ii), the input batch \(X\)  is uniformly sampled from a large collection of columns.
Under this assumption, a random pair \((\vec{z}_i, \vec{z}_j)\)  from \(\vec{Z}\)  are distinct with high probability.
Next, we can obtain the contrastive loss by averaging all matching pairs shown in Equation REF :
\(\mathcal {L}_{\mathsf {contrast}} =\frac{1}{2 N} \sum _{k=1}^{N}[\ell (k, k+N)+\ell (k+N, k)]\) 
where each term \(\ell (k, k+N)\)  and \(\ell (k+N, k)\)  refers to pairs of views generated from the same column.
And the training process based on such a loss is illustrated in Algorithm REF .
ParameterVariables
[!t]
 A collection \(D\)  of data lake columns
 Number of training epochs \(\mathsf {n\_epoch}\) ;
Data augmentation operator \(\mathsf {op}\) ; Learning rate \(\eta \)  
 An embedding model \(\mathcal {M}\) 

Initialize \(\mathcal {M}\)  using a pre-trained LM
 \(\mathsf {ep} = 1\)  to \(\mathsf {n\_epoch}\) 
Randomly split \(D\)  into batches \(\lbrace B_1, \dots B_n\rbrace \) 
\(B \in \lbrace B_1, \dots B_n\rbrace \)  
augment and encode every item
\(B_{\mathsf {ori}}, B_{\mathsf {aug}} \leftarrow \mathsf {augment}(B, \mathsf {op})\) 
\(\vec{Z}_{\mathsf {ori}}, \vec{Z}_{\mathsf {aug}} \leftarrow \mathcal {M}B_{\mathsf {ori}}), \mathcal {M}(B_{\mathsf {aug}})\) 
Equation (REF ) and (REF )
\(\mathcal {L} \leftarrow \mathcal {L}_{\mathsf {contrast}}(\vec{Z}_{\mathsf {ori}}, \vec{Z}_{\mathsf {aug}})\) 
Back-prop to update \(\mathcal {M}\) 
\(\mathcal {M}\leftarrow \textsf {back-propagate}(\mathcal {M}, \eta , \partial \mathcal {L} / \partial \mathcal {M}) \) 


\(\mathcal {M}\) , discard \(g\) 
\(\textsf {SimCLR pre-training}\)


<FIGURE>
Multi-column Table Encoder
While the method shown in Algorithm REF  learns column representations based on values within a column itself, it cannot take the contextual information of a table into account, which is vitally important to understanding the semantics of a column.
For example, the single-column model can understand that a column consisting of values “1997 1998 ...”
is a column about years, but depending on the context of other columns present in the same table, the same column can represent
“years in which a species of bird was observed in a specific area” or “years of car production”, etc.
As illustrated in the example in Figure REF , such understanding is important for deciding whether two tables are unionable or not.
To address this problem, \(\mathsf {Starmie}\)  combines contrastive learning with a multi-column table encoder illustrated in Figure REF .
The model starts with serializing an input table into a string by concatenating cell values from each column and adding a special separator token “<s>” to indicate the start of each column.
Next, we feed the sequence as the input to a pre-trained LM such as RoBERTa [10]}.
<FIGURE>The pre-trained LM first converts the input sequence into a sequence of token embeddings independent
of their context then applies 12 or more Transformer layers [11]} on top.
The self-attention mechanism in the Transformer layers convert the word embeddings into a sequence of contextualized embeddings.
These vector representations depend not only on the tokens themselves (e.g., “1797”) but also their context (e.g., “Albany”).
As such, we can extract the representations of the separator tokens (i.e., “<s>”) to be the contextualized column embeddings to capture the meaning of each column that takes the table context into account.
To apply contrastive learning using the multi-column model, we adapt the SimCLR
algorithm (Algorithm REF ) as follows.
First, we create the batches of columns (Line 3) by uniformly sampling a batch of tables from all data lake
tables and form each batch of columns \(B\)  using all columns from the sampled tables.
To augment the batch \(B\) , instead of transforming each column independently, we apply table-level
augmentation operators such as row sampling and column sampling (Line 5).
Note that in the multi-column setting, the augmentation operators produce views of tables with pairs of columns that align
with each other.
These pairs form the positive pairs in the contrastive loss as we illustrate in Figure REF .
We summarize the supported augmentation operators in Table REF .
While there is a large design space of the operators, we summarize them
by the levels (e.g., cell, row, column) of the table that the operators apply.
One can also perform more complex transformations by applying multiple operators simultaneously.
<TABLE><FIGURE>We then apply the multi-column model on the original and augmented views of tables to obtain the contextualized
column embeddings \(\vec{Z}_{\mathsf {ori}}\)  and \(\vec{Z}_{\mathsf {aug}}\)  (Line 6) and compute the contrastive loss (Line 7).
Note that in the multi-column setting, the positive pairs
(for which we maximize the similarity)
consist of the aligned pairs of columns generated by the augmentation operators.
We minimize the similarity of all other pairs which include (i) pairs of unaligned columns from the same table and
(ii) all pairs of columns from two distinct tables.
By doing so, the algorithm learns representations that can distinguish columns with the same/different table contexts.
More formally, let \(P\)  be the set of indices of all aligned pairs of columns in the batch \(B\) , we minimize the multi-column contrastive loss shown in Equation REF :
\(\mathcal {L}_{\mathsf {multi\text{-}column}} =\frac{1}{2|P|} \sum _{(i, j)\in P}[\ell (i, j)+\ell (j, i)] .\vspace{-5.69054pt}\) 
<FIGURE>
Optimizing Table Preprocessing
Typical pre-trained LMs like BERT support an input length of at most 512 sub-word tokens,
while a column in real-world tables such as those in Open Data may contain thousands or even millions of tokens.
As such, the default table preprocessing method can fail to capture the most relevant information from the input table for the downstream tasks.
To address this issue, in \(\mathsf {Starmie}\) , we explore a design space for tuning and optimizing this process to make hyper-parameter tuning and future exploration easier.
To start, we first determine whether to read the table horizontally (row by row) or vertically (column by column).
Since table union search typically relies on column alignment, we assume that
the column-ordered method will achieve better performance, which is verified empirically in Section .
We assume the column-order approach for the rest of the design options.
Next we explore a reasonable solution from the following three aspects.
Token/cell scoring functions.  First of all we need to decide how to score the importance of each token or cell for each column.
Here we consider the TF-IDF method for token scoring, where the importance of each token is computed as its inverse document frequency \(\log (M) / |\lbrace t \ | \ \mathsf {token} \in t\rbrace |\) , where \(t\)  is a column and \(M\)  is the number of all data lake columns.
Then the cell score is obtained by summing or averaging the TF-IDF scores of tokens in it.
Deterministic vs. non-deterministic.  After obtaining the score of each cell, we sort cells in the descending order of importance scores for each column.
Next, we can select and concatenate the tokens/cells either in a deterministic manner, e.g., in the descending order of the importance score, until we reach the token budget for each column (the max length uniformly distributed among columns), or a non-deterministic one by sampling the tokens/cells with probability proportional to their importance scores.
We try both ways in our experiments.
Row alignment.  Finally, we need to align the selected cells in a column.
If we simply concatenate the top-ranked tokens or cells, the row-alignment information from the original table might be lost after preprocessing.
In other words, the order of cells in the serialized columns may not follow the same order of the rows.
Row alignment information can be useful, e.g., (“California”, “Sacramento”) and (“New York”, “Albany”) as in our example for capturing the state-capital relation.
We propose another option that ranks all the rows by their average cell-level scores and then selects the rows to be included in the serialization result in either deterministic or non-deterministic ways.

Online query processing
In this section, we introduce how to find unionable tables based on contextualized column embeddings.
We first the table unionability scores and introduce the overall workflow of online query processing in Section REF .
Then we discuss the design choices for reducing the number of candidates using vector indices
and deducing bounds for more efficient verification in Sections REF  and REF , respectively.
Note that the online processing techniques explored here are not limited to any specific column encoders, they are also applicable to other dense-vector column representation methods [12]}, [13]}.
Table-level Matching Score
After training a column encoder \(\mathcal {M}\)  using techniques from Section , we can then obtain the embedding vectors for all columns in data lake tables via model inference.
The column unionability score between two columns \(s\)  and \(t\)  can be calculated by using cosine similarity as \(\mathcal {F}\)  between those embedding vectors.
Next, we define the function \(\mathcal {A}\)  for aggregating the column unionability scores to compute the table unionability.
Motivated by the idea of \(c\) -alignment [2]} that aims to find a maximum set of one-to-one alignment between columns in two tables, we propose modeling table unionability as a weighted bipartite graph matching problem.
More formally, given two tables \(S\)  and \(T\)  with \(m\)  and \(n\)  columns respectively, we construct a bipartite graph \(G = \langle S, T ,E\rangle \)  where the nodes \(S\)  and \(T\)  are the two sets of columns.
The edges in \(E\)  denote the column unionability score between each pair of columns.
Then table unionability score \(U(S,T)\)  can be calculated by finding the maximum bipartite matching of graph \(G\) .
In order to remove the noise caused by dissimilar pairs of columns, we follow the de-noising strategy from fuzzy string matching [15]} by introducing a hyper-parameter \(\tau \)  as the
similarity lower bound: given two columns \(s \in S\)  and \(t \in T\) , there is an edge \(\langle s, t\rangle \in E\)  iff \(\mathcal {F}(s, t) \ge \tau \) .
<FIGURE>We show an example of computing the table unionability score in Figure REF .
Suppose there are two tables \(S\)  and \(T\)  with 4 and 3 columns respectively and the threshold \(\tau \)  for column unionablity score is 0.5.
Since the cosine similarity between \(s_3\)  and \(t_3\)  is 0.3 (\(<\tau \) ), the edge between them is discarded (denoted with a dash line).
For the ease of presentation, we omit the remaining dash lines between other nodes in the figure.
The maximum bipartite matching of this graph consists of the edges in red (solid lines), which are \(\langle s_1, t_1 \rangle \) , \(\langle s_2, t_2 \rangle \)  and \(\langle s_4, t_3 \rangle \)  with a score of 2.15.
In order to find the tables with top-k highest table unionability scores with the given query table \(S\) , a straightforward method is to conduct a linear scan: we use a min-heap with cardinality of \(k\)  to keep the results of top-k search, then for each table \(T\)  in the data lake, we directly compute \(U(S,T)\) ; and if the score is higher than the top element of the min-heap, we replace the top element with it and adjust the min-heap accordingly.
However, since the time complexity of weighted bipartite matching is \(\mathcal {O}(n^3 \log n)\) , where \(n\)  is the total number of columns in two tables, it is rather expensive to traverse all tables in a data lake.
A scalable solution requires reducing (i) the number of accessed tables and (ii) the computational overhead of verifying each pair of tables.
ParameterVariables
[!t]
\(S\) : the query table; \(\mathcal {T}\) : the set of data lake tables;

\(k\) : the number of desired results;
\(\tau \) : threshold of column unionable score;

 \(\mathcal {H}\) : The top-k unionable tables
Initialize \(\mathcal {H}\)  and \(\mathcal {C}\)  as \(\emptyset \) ;
all columns \(s \in S\) 
\(\mathcal {C}= \mathcal {C}\cup \mathsf {findCandidates}(s, \tau , \mathcal {T})\) ;

all tables \(T \in \mathcal {C}\) 
\(|\mathcal {H}| < k\) 
Compute \(\mathsf {Verify}(S, T)\)  and add \(T\)  into \(\mathcal {H}\) ;


\(X \leftarrow \)  the score of top element of \(\mathcal {H}\) ;
\(\textbf {LB}(S,T) > X\) 
Replace the top element of \(\mathcal {H}\)  with \(T\) ;

\(\textbf {UB}(S,T) \le X\) 
Discard \(T\) ;

\(\mathsf {Verify}(S, T) > X\) 
Replace the top element of \(\mathcal {H}\)  with \(T\) ;



\(\mathcal {H}\) ;
Online Query Processing


We propose a filter-and-verification framework to address this issue as illustrated in Algorithm REF .
Instead of doing a linear scan over all data lake tables, it employs filter mechanisms to identify a set of candidate tables \(\mathcal {C}\)  for further verification (line: 3).
As a result, it can reduce the number of expensive verification operations \(\mathsf {Verify}(S, T)\) .
This is realized by the function findCandidates (Section REF ).
Then for all the candidate tables, we further come up with a pruning mechanism to estimate the lower bound \(\textbf {LB}(S,T)\)  and upper bound \(\textbf {UB}(S,T)\)  of \(U(S,T)\) .
If the lower bound is larger than the current lowest score, we can directly replace it with the top element without further verification (line: 10).
Similarly, if the upper bound is no larger than the current lowest score, we can directly discard it (line: 12).
This pruning mechanism is effective since \(\textbf {LB}\)  and \(\textbf {UB}\)  are much more efficient to estimate than the exact verification \(\mathsf {Verify}(S, T)\)  (Section REF ).

Reducing the Number of Candidates
Given a column with its embedding vector, we need to quickly identify tables from the data lake that contain unionable columns, which is realized by the findCandidates function in Algorithm REF .
This is a problem of similarity search over high-dimensional vectors.
Locality Sensitivity Hashing (LSH) [16]} has been used in previous studies of table search to find joinable [17]}, unionable [2]}, and related columns [1]} in sub-linear time.
The basic idea is to use a family of hash functions to map high-dimensional vectors into a number of buckets, where the probability that two vectors are hashed into the same bucket is correlated to the value of a certain similarity metric between them.
Following this work, we build a simHash [20]} LSH index to estimate the cosine similarity between column embedding vectors.
Then for each query column vector \(s\) , we can quickly find a set of similar column vectors via an index lookup.
Then the candidate set \(\mathcal {C}\)  can be obtained by the union of candidates returned by utilizing each column vector \(s\)  to query the index.
In addition to LSH, we also explore the more recent HNSW (Hierarchical Navigable Small World) [21]}.
HNSW is a proximity graph with multiple layers where two vertices are linked based on their proximity.
It supports fast nearest neighbor search with high recall.
We find that HNSW improves the query time by orders of magnitude and thus allows \(\mathsf {Starmie}\)  to support querying over the WDC corpus with 50M tables, which is much larger than the previously supported datasets for table union search.
Since such index structures return approximate instead of exact results, there might be some false negatives in the top-k results.
Nevertheless, we find in the experiments that the effectiveness loss caused by the false negatives is within a reasonable range.
Meanwhile, the query time can be reduced by one to three orders of magnitude (details in Section REF ).

Pruning Mechanism for Verification
Once a candidate table is found, we can reduce the expensive verification cost by quickly computing lower and upper bounds on the table unionability score.
To this end, we first look at how to estimate the upper bound \(\textbf {UB}(S,T)\)  between two tables \(S\)  and \(T\) .
Recall that in maximum weighted bipartite matching, each column/node in both \(S\)  and \(T\)  can be covered by at most 1 edge in the edges of the maximum matching.
If we remove this constraint, since nodes can appear in multiple edges, the new optimal matching is easy to compute.
Moreover, as it allows edges with greater weights, the total score forms an upper bound of the true table unionability score \(U(S, T)\) .
To compute the upper bound \(\textbf {UB}(S,T)\) , we first sort the edges by their weights in descending order.
Then we add edges with the largest weights into the matching in a greedy manner.
This process is repeated until all columns in \(S\)  or \(T\)  are covered or all edges are used.
The time complexity of the above process for calculating \(\textbf {UB}(S,T)\)  is \(\mathcal {O}(|E| \log |E| + n)\) , where \(|E|\)  is the number of edges in \(G\) .
It is much cheaper to compute than the real table unionability score.
Next, we introduce how to quickly estimate a meaningful lower bound \(\textbf {LB}(S,T)\) .
For lower bounds, we would like to find a set of edges that do not violate the constraint of bipartite matching, i.e., each column in the two tables is covered by one edge.
We can also achieve this goal via a greedy algorithm.
Similar to computing the upper bound, we sort the edges by weight in descending order and pick edges with the largest weights.
After that, we remove edges that are associated with the columns in the selected edges so as to avoid violations.
The termination condition of this process is also the same as that of calculating the upper bound.
Since the resulting matching does not necessarily cover all nodes in \(S\)  or \(T\) , the total weight \(\textbf {LB}(S,T)\)  is a lower bound of the maximum matching.
The time complexity of calculating \(\textbf {LB}(S,T)\)  is also \(\mathcal {O}(|E| \log |E| + n)\) .
We use the example in Figure REF  to illustrate the upper and bound computation.
We fetch edges in the descending order of weight:
\(\langle s_1, t_2 \rangle \) , \(\langle s_1, t_1 \rangle \) , \(\langle s_2, t_2 \rangle \) , and \(\langle s_4, t_3 \rangle \) . At this point, since all nodes \(\lbrace t_1, t_2, t_3\rbrace \)  in \(T\)  are covered, we stop here.
The upper bound is \(0.85+0.8+0.7+0.65 = 3\) , larger than the exact value 2.15.
To compute the lower bound, we start from edge \(\langle s_1, t_2 \rangle \)  and then remove all edges associated with \(s_1\)  and \(t_2\) .
The remaining edge with maximum weight is \(\langle s_4, t_3 \rangle \) .
After involving this edge into the matching, there is no remaining one and the algorithm stops here.
Hence, the lower bound is \(0.85+0.65 = 1.5\) , which is smaller than the exact value 2.15.

Experiments
In this section, we present empirical evaluations of \(\mathsf {Starmie}\)  on real-world data lake corpora.
First, we show that \(\mathsf {Starmie}\)  achieves new state-of-the-art results on table union search by outperforming the previous best methods by 6.8% in MAP and Recall.
Next, our scalability experiments show that \(\mathsf {Starmie}\)  (especially with the HNSW index) achieves significant performance gain (up to 3,000x) while preserving reasonable performance of effectiveness.
Lastly, we conduct case studies to show how \(\mathsf {Starmie}\)  can generalize to another two dataset discovery applications: column clustering and table discovery for downstream machine learning tasks.
Due to the space limitation, we include additional results and discussions in the online appendix https://github.com/megagonlabs/starmie/blob/main/appendix.pdf.
Experiment Setup
Environment
We implement \(\mathsf {Starmie}\)  in Python using Pytorch and the Hugging Face Transformers library [22]}.
For contrastive learning, we use RoBERTa [10]} as the base language model.
We set the hyper-parameters batch size to 64, learning rate to 5e-5, and max sequence length to 256 across all the experiments.
All experiments are run on a server with configurations similar to those of a p4d.24xlarge AWS EC2 machine with 8 A100 GPUs.
The server has 2 AMD EPYC 7702 64-Core processors and 1TB RAM.

Datasets
We use five benchmarks with statistics detailed in Table REF .
Specifically, we evaluate the effectiveness on the first three benchmarks that are subsets of real Open Data with manually labeled ground truth.
The SANTOS Small benchmark [3]} consists of 550 real data lake tables drawn from 296 Canada, UK, US, and Australian open datasets, and 50 query tables.
From Table Union Search [2]}, there are two available benchmarks:
TUS Small and TUS Large.
TUS Small benchmark consists of 1,530 data lake tables that are derived from 10 base tables from Canada open data.
We also use the larger benchmark, TUS Large, which consists of \(\sim \) 5,000 data lake tables derived from 32 base tables from Canada open data.
For these two benchmarks, we randomly select 150 and 100 query tables, respectively, following previous studies [3]}, [2]}.
The SANTOShttps://github.com/northeastern-datalab/santos and TUS https://github.com/RJMillerLab/table-union-search-benchmark benchmarks, along with their ground truth of unionable tables, are publicly available.
The last two benchmarks are utilized in the experiments for efficiency and scalability.
The SANTOS Large benchmark contains \(\sim \) 11K raw data lake tables from Canada and UK open data, and 80 query tables.
We also run experiments on the WDC web tables corpus [28]} which contains 50.8 million relational web tables in English extracted from the Common Crawl.
We randomly select 30 tables as the query.
Note that since these two large benchmarks do not have labeled ground truth, we are not able to evaluate
the effectiveness on them and thus just perform experiments for efficiency.
<TABLE>
Metrics
For effectiveness, we perform evaluation based on the ground truth from the first three benchmarks.
For the TUS benchmarks, the tables are synthetically-partitioned from tables of distinct domains, so the ground truth is created in a generative manner.
As for the SANTOS Small benchmark, the tables have been manually-annotated to create a ground truth listing expected unionable tables to each query table.
Then we follow previous studies [3]}, [2]}, [1]}, [32]} and use the Mean Average Precision at k (MAP@k), Precision at k (P@k) and Recall at k (R@k) to evaluate the effectiveness in returning the top-k results.
We compute each score by averaging 5 repeated runs.
Note that a perfect recall is unattainable when the ground truth contains fewer than k results for the query table.
For efficiency, we measure the average time per query.

Baselines
For effectiveness experiments, we compare our approach, \(\mathsf {Starmie}\) , with the following methods.
\(D^3\) L  [1]} extends Table Union Search [2]} for the problem of finding related tables by using table features such as column names, value overlap, and formatting.
To compare fairly with \(\mathsf {Starmie}\) , we omit the column name feature.

SANTOS  [3]} proposes an approach that leverages both columns and relationships between columns by using external and self-curated knowledge bases.

\(\mathsf {Sherlock}\)   [12]} is a representation learning method that leverages several column features such as table statistics and word embeddings to learn the embedding vector of a column.

\(\mathsf {SATO}\)   [13]} extends \(\mathsf {Sherlock}\)  by capturing the table context using LDA, and thus performing a form of multi-column prediction.

\(\mathsf {SingleCol}\)  is a basic column encoder proposed in Section REF  that uses the encoder to only encode a single column.
For efficiency experiments, we aim at exploring the benefits brought by different design choices in the \(\mathsf {Starmie}\)  framework.
Thus we compare the performance of 4 methods: basic linear search (Linear), pruning based on estimated bounds (Pruning), search with an LSH index (LSH), and search with an HNSW index (HNSW).
Column encoder settings
We empirically choose the most suitable sampling method (Section REF ) and augmentation operator (introduced in Section REF  and more details in Appendix A).
For sampling methods, on the SANTOS Small and TUS Large benchmark, we find that \(\mathsf {Starmie}\)  achieves the best performance when pre-training it with the column-ordered sampling method with cell-level TF-IDF scoring function.
On TUS Small, we find that a special column-ordered sampling method, alphaHead, that sorts
tokens in alphabetical order performs the best.
For augmentation operators, we find that the drop_col operator performs the best on SANTOS Small while
drop_cell achieves the best performance on the two TUS benchmarks.

Main results
Table REF  reports the results of MAP@k and R@k on the three benchmarks for all methods.
Note that the results for SANTOS are unavailable for TUS Large because SANTOS, which requires the labeled query table intent columns [3]}, have not been evaluated on this benchmark due to the absence of annotated intent columns.
We run the experiments up to k=10 on SANTOS Small following [3]}, and up to k=60 on the TUS benchmarks, which is consistent with [2]}.
<TABLE>We can observe that \(\mathsf {Starmie}\)  outperforms the baselines across all three benchmarks.
On the SANTOS Small benchmark, \(\mathsf {Starmie}\)  achieves the highest MAP@10 of 99.3% and highest R@10 of 73.7%, outperforming \(\mathsf {SATO}\) , \(\mathsf {Sherlock}\) , SANTOS, \(D^3\) L baselines by large margins of 13%, 27%, 6.8%, and 90% respectively.
Specifically, \(\mathsf {Starmie}\)  outperforms the \(\mathsf {SingleCol}\)  variation by 11%, showing that a multi-column approach is necessary.
Similarly, on the TUS Small benchmark, \(\mathsf {Starmie}\)  outperforms the highest-achieving baseline, \(\mathsf {Sherlock}\) , by 0.7% and \(\mathsf {SingleCol}\)  variation by 4% in MAP@k.
On the TUS Large benchmark, \(\mathsf {Starmie}\)  outperforms \(\mathsf {SATO}\)  by 4% and \(\mathsf {SingleCol}\)  by 7% in MAP@k.
Thus, the \(\mathsf {Starmie}\)  approach, by capturing column context and leveraging contrastive learning in pre-training, is very effective in solving the table union search problem.
<FIGURE>Figure REF  shows the comparison of P@k and R@k \(\mathsf {Starmie}\)  with the baselines as k increases (with the same respective k's), on all benchmarks.
Throughout all values of k, \(\mathsf {Starmie}\)  outperforms all baselines for both P@k and R@k.
Since the recall might be limited to the available ground truth, we also plot the IDEAL lines denoting the maximum recall that a method can achieve on a dataset.
In Figures REF (b), (d), and (f), \(\mathsf {Starmie}\)  is closest to IDEAL, with R@10 only 1.8% below IDEAL on SANTOS Small, R@60 18.8% below IDEAL on TUS Small, and R@60 14.1% below IDEAL on TUS Large.
<FIGURE>To better understand the influence of datasets on the performance of \(\mathsf {Starmie}\) , we conduct in-depth analysis experiments to look at its performance for different settings of arity, cardinality, and percentage of numerical columns in query tables.
We evenly split the query tables into five groups, from one with the smallest numbers to that with the most.
Here we compare \(\mathsf {Starmie}\)  with alternative representation methods \(\mathsf {SATO}\)  and \(\mathsf {Sherlock}\)  that also encode columns into high-dimensional vectors.
As shown in Figure REF , as the number of rows increases, the results of \(\mathsf {Starmie}\)  remain consistently high while the performance of \(\mathsf {Sherlock}\)  and \(\mathsf {SATO}\)  decreases.
Since \(\mathsf {Starmie}\)  is unaffected by the increasing number of rows due to our efforts in exploring the table preprocessing techniques (Section REF ).
Besides, \(\mathsf {Starmie}\)  performs consistently well as the percentage of numerical columns increases, showing that \(\mathsf {Starmie}\)  can differentiate even between the semantics of numerical values.
The methods have similar trends on the TUS Small and TUS Large benchmarks as shown in Appendix B.

Scalability
<TABLE>Impacts on effectiveness. 
First of all, since some design choices might result in performance loss of effectiveness, we report their results of three evaluation metrics on the SANTOS Small benchmark.
As shown in Table REF , we compare the basic linear scan with another three design choices (above the horizontal line), as well as baselines \(\mathsf {SATO}\) , \(\mathsf {Sherlock}\) , and \(\mathsf {SingleCol}\)  (full experiment results are shown in Appendix C).
The main takeaway is that HSNW index preserves the effectivenss as much if not better than the LSH index that is widely used in previous studies about table union search, while having tremendous speed improvement.
This suggests a very promising direction for providing real-time search over massive data lakes.
Preprocessing time. 
Since \(\mathsf {Starmie}\)  requires model pre-training and model inference, in addition to possibly indexing, we provide some insights of such overhead by comparing its preprocessing time with existing systems \(D^3\) L and SANTOS that are not based on pre-trained LMs . The preprocessing time of \(\mathsf {Starmie}\)  consists of the following parts: pre-training taking 3.1 hours, model inference taking 4.4 min, and indexing taking 10-30 sec.
Meanwhile, \(D^3\) L takes 7.6 hours to create four indexes for each column feature and SANTOS takes 17 hours to create indexes using a knowledge base and the data lake.
Thus, pre-training a language model in \(\mathsf {Starmie}\)  does not incur too much overhead compared to existing systems.
<FIGURE>Time efficiency. 
We have observed that the employed design choices can speed up the online query time while sufficiently preserving the effectiveness scores.
Next we evaluate the scalability of different design choices.
In Figure REF (a), we first evaluate the four variations of \(\mathsf {Starmie}\)  on the SANTOS Large benchmark, as we increase the number of returned unionable tables k from 10 to 60.
We then evaluate their query times as the data lake size grows to its full size of \(\sim \) 11K tables / \(\sim \) 120K columns.
We also experiment on the WDC benchmark, specifically when the data lake grows to 1M tables / 5M columns (Figure REF (b)) to show the trend of each method , and when the data lake grows to 50M tables / 250M columns (Figure REF (c)).
For each method, if a data point's query time does not finish within 24 hours, then we consider it as timeout and omit the result from the corresponding figures.
Throughout all these experiments, we see that the design choice with the HNSW index leads to the best performance.
On the SANTOS Large benchmark in Figure REF (a), the k-scalability experiment shows that Pruning is 2X faster than Linear, while LSH index is 20X faster than Linear.
Meanwhile, HNSW index, which leads to an average query time of around 300 ms, is 220X faster than Linear and 11X faster than the popular LSH index.
As the data lake grows to its full size, there is a steady increase in query time of Linear and Pruning; while that of LSH index and HNSW index remain stable, with the query time of HNSW index remaining around 400 ms.
On the WDC benchmark in Figure REF (b), there is a similar trend as the data lake grows to 1M tables.
Here, the query time of HNSW index remains around 270 ms as the data lake grows, even as the other methods have a steady or slight increase in query time.
At the data lake size of 1M tables, Pruning is 2.5X faster than Linear while LSH index is 8X faster than Linear. Notably, HNSW index is 3000X faster than Linear, and 400X faster than the widely-used LSH index.
On the full WDC benchmark in Figure REF (c), Linear and Pruning time out after 1M tables, while LSH index times out after having an average query time of 2,520 sec on 10M tables.
Meanwhile, HNSW index stays consistent throughout the experiment, with the query time staying around 60 ms even as the data lake grows to its full size of 50M tables / 250M columns.
The reason is that the hierarchical graph-based structure of HNSW allows it to locate to the nearest neighbors much faster than hash-based indexes [21]}.
Overall, the design choices explored in this paper, especially HNSW index, show a great improvement in the average query time, even when the data lake grows to an immense size of 50M tables.
Meanwhile, to the best of our knowledge, the largest dataset that are evaluated by existing solutions of table union search is with only 5,000 tables / 1M columns [2]}, which has 250 times smaller number of columns.
Memory overhead. 
Lastly, we examine the relative memory overhead of \(\mathsf {Starmie}\)  with different design choices (No index denotes linear scan and pruning methods in Table REF ).
In Table REF , we report the memory usage of \(\mathsf {Starmie}\)  relative to the total data lake size (11 GB) of
SANTOS Large.
The results show that \(\mathsf {Starmie}\)  is not only scalable but also memory efficient: its variations take up around 3-7% space overhead.
The memory saving is mainly due to the condensed vector column representations of \(\mathsf {Starmie}\)  which take up only 3% of the original data lake size.
<TABLE>

Data discovery for ML tasks
Next, we conduct a case study to show that \(\mathsf {Starmie}\)  can be applied to another application scenario of dataset discovery, i.e. retrieving relevant tables to improve
the performance of downstream ML tasks.
For this case study, we consider a subset of 78k WDC tables
used in the evaluation of \(\mathsf {SATO}\)   [13]}, from which
we collect all the 4,130 tables of at least 50
rows as the data lake tables. Among these tables, we find that 25 tables of at least 200 rows
contain a numeric column called “Rating”. These 25 tables contain various types of ratings
including those for sportsmen, TV shows, US congress members, etc.
From these tables, we construct 25 regression tasks with the goal of training an ML model that predicts
“Rating” as the target column.
Since the ratings are from different domains, we normalize their values to the range \([0, 1]\) .
More details about the setting can be found in Appendix D.
For each task, we train a Gradient-Boosted Tree model [44]} with all non-target
columns as features. We featurize the textual columns using Sentence Transformers [45]}. We split each dataset into training and test sets at a ratio of 4:1. Note that the original dataset may not contain informative features.
Figure REF  shows such a dataset of US congress members.
Without useful features, the model only achieves a Mean Squared Error (MSE) of 0.1598.
To improve the model's performance on these downstream tasks, we leverage \(\mathsf {Starmie}\)  to retrieve relevant tables from the data lake to join with the datasets (i.e., the query tables) to provide additional features.
To showcase the effectiveness of \(\mathsf {Starmie}\) , we use \(\mathsf {Starmie}\) 's contextualized column embeddings to retrieve from the data lake table that contains a column having the highest cosine similarity with a non-target column of the query table.
Finally, we augment the query table by performing
a left-join with the retrieved table to ensure that the size of the augmented table stays unchanged.
We also consider two popular similarity methods for this task, Jaccard and Overlap [46]}, [47]}, as baselines
by replacing the cosine similarity scores with the corresponding similarity functions.
Table REF  summarizes the results of the 3 evaluated methods. While all 3 methods result in
performance improvement (i.e., reduction of MSE), \(\mathsf {Starmie}\)  achieves significantly better
overall improvements with a 14.75% MSE reduction, on 15/25 tasks improved, and by an average of 20.64%.
By inspecting the retrieved tables, we find that \(\mathsf {Starmie}\)  indeed retrieves qualitatively better candidate
tables. As Figure REF  shows, for the same US congress members table,
Jaccard similarity may retrieve an irrelevant table of dog competitions that also contains
a similar “State” column, but the two tables are not semantically relevant.
On the other hand, \(\mathsf {Starmie}\)  retrieves a table consisting of the amount of money raised from different
interest groups, which is a potentially relevant feature to “Rating”. Indeed, by joining
with the retrieved table by \(\mathsf {Starmie}\) , the MSE of the model drops from 0.1598 to 0.1198 (by \(>\) 25%).
<TABLE><FIGURE>
Case study: Column clustering
<TABLE>Finally we show another application scenario of \(\mathsf {Starmie}\)  in dataset discovery: column clustering.
Specifically, we apply \(\mathsf {Starmie}\)  as a column encoder to provide embeddings
for clustering all the 119,360 columns from the 78k WDC tables
used in the experiments of \(\mathsf {Sherlock}\) , \(\mathsf {SATO}\) , and others [12]}, [13]}, [7]}. These columns are annotated with 78 ground truth semantic types
such as population, city, name, etc.
The goal of column clustering is to discover clusters
of columns that are semantically relevant.
The task of semantic type detection has traditionally been solved as
a supervised multi-class classification problem
which requires significant annotated training data [7]}.
\(\mathsf {Starmie}\)  provides an unsupervised solution.
From the contextualized column embeddings, we can construct a similarity graph over all data lake columns as nodes.
We can then add undirected edges between all pairs of columns having cosine similarities above a
threshold \(\theta \)  (e.g., 0.6).
Next the column clusters can be generated via any graph clustering algorithm. We choose the connected component algorithm for efficiency and simplicity.
With \(\mathsf {Starmie}\) , the clustering algorithm generates 2,297 clusters with an average cluster size of 51.96.
We measure the quality of the clusters by the purity score, which
is
the percentage of columns assigned with the same semantic type as the majority ground truth
type of each cluster. The discovered clusters are generally of high quality as
they achieve a purity score of 51.19 while using baselines such as
\(\mathsf {Sherlock}\)  and \(\mathsf {SATO}\)  only achieves 30.5 or 37.36 purity scores when generating a similar number of clusters.
We further inspect the column values within each cluster and find that \(\mathsf {Starmie}\)  discovers
clusters of finer-grained semantic types not present in the original 78 types (more results in Appendix E).
Table REF  shows 3 such example clusters. The majority types (from the 78 original types) of columns in the 3 clusters
are “type”, “name”, and “artist” respectively. After inspecting the column values,
we can interpret the types of the 3 clusters as names of schools, names of food/grocery stores,
and names of songs.
It is difficult to discover such fine-grained types by existing methods based on supervised classification.

Related Work
Dataset Discovery
Dataset Discovery has been a hot topic in the data management community.
Earlier studies [52]}, [53]}, [54]} relied on keyword search over web tables to identify essential information.
Octopus [55]} and InfoGather [56]} focused on the problem of schema complement, an important topic in exploring web tables.
Aurum [57]}, S3D [58]} and Tableminer+ [59]}, [60]} utilized knowledge bases to identify relationship between datasets.
SemProp [61]} followed this route by leveraging ontologies and word embeddings, and Leva [62]} solved a similar problem with graph neural networks.
\(D^4\) [63]} addressed the problem of column clustering in data lake tables.
Valentine [64]} provided resources for evaluating column matching tasks.
DomainNet [65]} studied the problem of disambiguation in data lakes.
Finding related tables from data lakes is an essential task in dataset discovery.
There are two sub-tasks in this application, namely finding joinable tables and table union search [66]}.
To support finding joinable tables, earlier studies utilized syntactic similarity metrics that are widely used in the applications of string similarity search and join [67]}, [68]}, [69]}.
LSH Ensemble used containment (overlap) [17]} as the similarity metric and provided a high-dimensional similarity search based solution.
Josie [46]} employed overlap over tokens and developed an exact data-optimized solution.
PEXESO [47]} relied on cosine similarity over word embeddings and proposed indexing techniques to improve performance.
The table union search problem has been well explored recently.
Ling et al. [73]} and Lehmberg et al. [74]} illustrated the importance of finding unionable tables.
Nargesian et al. [2]} proposed the first definition and comprehensive solution for the table union search problem.
Bogatu et al. [1]} proposed the \(D^3\) L system by dividing columns into different categories.
The SANTOS  [3]} system utilized knowledge base along with binary relationships in the data lake to identify tables that share unionable columns and relationships, and it is the state-of-the-art approach in this field.
To the best of our knowledge, our work is the first solution to utilize contrastive learning techniques in table union search.

Representation Learning for Tables
Recently there are many efforts that use representation learning techniques to address problems related to tabular data.
Sherlock [12]} and Sato [13]} utilized a feature based approach to learn vector representations for tables and columns.
TURL [6]} proposed to use a pre-trained language model for web table related tasks and to come up with benchmark datasets for several tasks.
And pre-trained language models have been widely applied to different table-related applications, including entity matching [5]}, [82]}, [83]}, column type detection [84]}, [7]}, and question answering [86]}, [87]}.
Our work follows this line of study and proposes the first solution that employs a pre-trained language model in a fully unsupervised way for the problem of table union search.

Conclusion
In this paper, we mainly focused on the problem of table union search, an essential application in dataset discovery from data lakes.
We argued that it is crucial to utilize contextual information to determine whether two columns are unionable and proposed \(\mathsf {Starmie}\) , an end-to-end framework as the solution.
\(\mathsf {Starmie}\)  utilized pre-trained language model as the column encoder and employed contrastive representation learning to pre-train the model in a fully unsupervised manner.
We also developed a multi-column table Transformer encoder that can capture the contextual information from a table so as to learn contextualized column embeddings.
Moreover, we came up with a scalable search framework for aggregating column unionability scores into a table unionability score, which can make use of multiple design choices in filtering and indexing to accelerate query processing.
Experimental results on popular benchmark datasets demonstrated that \(\mathsf {Starmie}\)  significantly outperformed existing solutions for table union search.
Besides, we also showed that by leveraging efficient indexing techniques, our proposed framework can scale well to datasets that are 250 times larger than those can be supported by existing solutions so far.

Comparing different operators
Augmentation Operators
<FIGURE>To find the most effective augmentation operator used in pre-training (Section
REF ) on the SANTOS Small benchmark, we conduct experiments
comparing the MAP@k scores of different \(\mathsf {op}\) 's, shown in Figure
REF .
Specifically, we experiment with augmentation operators at different table levels, including some of the operators listed in Table REF :
Cell-Level: 

drop_cell: drops a random cell in a column

Row-Level: 

sample_row: samples a random percentage of the rows

sample_row_ordered: samples random percentage of the rows, while preserving the original order of the rows

shuffle_row: shuffles the row order

Column-Level: 

shuffle_col: shuffles the column order

drop_col: drops a random subset of column

drop_nan_col: drops columns consisting mostly of NaN's

drop_num_col: drops a random subset of numeric columns

From this ablation study, we find that the column-level operator drop_col leads to the highest MAP@k of 98%, and thus conduct the effectiveness experiments with the drop_col \(\mathsf {op}\) .

Sampling Methods
<FIGURE>We also conduct an empirical study comparing different sampling methods to find the method that best preserves the most meaningful tokens in table preprocessing. Specifically, we experiment with the following sampling methods, categorized by the level of the table. Note that all methods preserve the original order of the tokens/cells/rows, while taking unique samples:
Column-Based, Token-Level: 

head: sample first N tokens

random: randomly sample tokens

everyN: sample every Nth token

uniform: sample most frequently-occurring tokens

tfidf_token: sample tokens with highest TF-IDF

alphaHead: sample first N tokens sorted alphabetically scores

Column-Based, Cell-Level: 

tfidf_entity: sample cells in a column with highest average TF-IDF scores over its tokens

Row-Level: 

tfidf_row: samples rows with highest average TF-IDF scores over tokens in a row

row_ordered: sample and serialize tokens in a row

For the design space listed in Section REF , we reach the following conclusions from the results shown in Figure REF :
Row-ordered vs. column-ordered:  Out of all the sampling methods, the only row-ordered method is “row_ordered" (tfidf_row is column-ordered but selects cells based on the highest average TF-IDF score across the row). The column-ordered methods outperform row_ordered, with the highest column-ordered method tfidf_entity achieving a MAP@k of 99.2% while row_ordered has a MAP@k of 97.9%, thus confirming the original hypothesis.
Token/cell scoring functions:  So far we have experimented with simple scoring functions (e.g. head, random), with the most complex scoring function being TF-IDF. However, we can see that the TF-IDF-based methods, specifically tfidf_entity performs the best.
Deterministic vs. non-deterministic:  All methods except for “random" are deterministic. Since the best-performing deterministic method, tfidf_entity, outperforms the non-deterministic method “random" (which achieves a MAP@k of 97.3%) we conclude that deterministic methods are more effective.
Row alignment:  Methods tfidf_row and row-ordered preserve the row alignment. We can see that column alignment is still more effective, but this design space requires further experimentation.
All in all, this ablation study on the SANTOS Small benchmark shows that the sampling method tfidf_entity performs the best, with a MAP@k of 99.2%. Thus, we conduct our effectiveness experiments on the SANTOS Small benchmark with tfidf_entity as the sampling method.

In-depth Analyses on Effectiveness
<FIGURE>Similar to the in-depth analyses conducted for SANTOS Small benchmark, shown in Figure REF , we conduct experiments on both TUS benchmarks to analyze \(\mathsf {Starmie}\) 's performance compared to the baselines SATO and Sherlock. With the same three analyses per benchmark, and the same division of tables into 5 buckets, we first explore the MAP@k results on the TUS Small benchmark. In Figure REF , \(\mathsf {Starmie}\)  again outperforms the baselines and is robust to data containing large numbers of columns, rows, and high percentage of numeric columns. The baselines also show relatively consistent results across all buckets in the three analyses, which can be attributed to the fact that the TUS Small benchmark is derived from only 10 seed tables, and thus may not exhibit much heterogeneity. This hypothesis requires further analysis.
<FIGURE>Conducting the same analyses on the TUS Large benchmark, we see in Figure REF  that \(\mathsf {Starmie}\)  also outperforms the baselines and is consistent across all buckets. On this larger benchmark, even when the baselines' MAP@k performance drops as the number of rows increases or as the percentage of numeric columns increases, \(\mathsf {Starmie}\)  MAP@k remains consistently high, proving again that \(\mathsf {Starmie}\)  performs well across tables of various sizes and columns of different types.

Full results for Efficiency experiments
Efficiency Techniques impact on Performance
<TABLE>As we experiment with different efficiency techniques in Section REF , we also explore their effects on not only the runtimes but also the effectiveness scores. Table REF  explores the different efficiency techniques for the \(\mathsf {Starmie}\)  method, showing that they lead to great speedup while preserving the \(\mathsf {Starmie}\)  performance. In Table REF , we expand on this experiment and apply the efficiency techniques to other embeddings, specifically those of the baselines SATO, Sherlock, and SingleCol. We see that the Pruning technique speeds up the query time by 1.1-2X, while consistently preserving the performance scores perfectly. For indexing techniques, LSH index and HNSW index speed up the query times by 2.6-10X and 2-24X, respectively. Even with the fastest speedup from HNSW index, the baselines SATO and Sherlock are still slower than \(\mathsf {Starmie}\)  while having worse performance scores. As expected, SingleCol is faster as it does not have the cost from the table context. However, even with the fastest query times from the approximation technique HNSW index, \(\mathsf {Starmie}\)  still outperforms all baselines.

k-Scalability on WDC Benchmark
<FIGURE>For the scalability experiments, in Section REF  we experiment with the 4 efficiency techniques on \(\mathsf {Starmie}\)  on the SANTOS Large and WDC benchmarks. In Figure REF (a), we show the experiment on SANTOS Large as we increase k from 10 to 60. In Figure REF , we show the same experiment on 1M of the WDC tables. The trends across both figures are similar, with the HNSW index having the fastest query time, followed by LSH index, Pruning, then Linear. However here, HNSW index has a much more impressive performance with the query time remaining around 250 ms as k increases to 60, which is 3000X faster than Linear and 400X faster than LSH index. Thus, \(\mathsf {Starmie}\)  is generally robust in query time as the number of results to return increases, and is sped up the most with HNSW index.

Details of column clustering
Table REF  shows the full results
of column clustering. We use Sherlock, Sato, \(\mathsf {Starmie}\) ,
and its single-column version to generate the column
embeddings. After obtaining the column embeddings,
we construct a similarity graph by adding edges
between pairs of columns with similarity above a threshold
\(\tau = 0.6\) .
We then cluster the columns by computing their connected
components. Note that for fair comparison,
we restrict the size of clusters to be around 50
so that different methods generate similar numbers of
clusters. We measure the quality of clusters by their
purity scores, which measure how likely a column is
assigned to a cluster with the same majority semantic type
as that of the column.
Among the 4 methods, \(\mathsf {Starmie}\)  generates
clusters with the highest purity score of 51.19%.
<TABLE>
Full results for data discovery for ML
Table REF  shows the full results
of the 25 rating prediction tasks created from
4,130 WDC web tables of \(\ge \) 50 rows.
Each dataset is split into a training and a testing set
at a 4:1 ratio. The baseline methods are:
NoJoin:  Train a XGBoost model with numeric and
textual features from the original table \(S\)  only.
We featurize text attributes using
the Sentence Transformers
library [45]}.
Jaccard:  Perform an equal left-join with
a table that contains a column with the highest Jaccard
similarity with any column in the query table. Namely,
given a query table \(S = \lbrace s_1, \dots , s_n\rbrace \)  of \(n\) 
non-target columns and a data lake \(\mathcal {T}\) , we join \(S\) 
with the data lake table
\(\operatornamewithlimits{\arg \!\max }_{T \in \mathcal {T}}\left(\max _{s_i \in S, t_j \in T}(\mathsf {Jaccard}(s_i, t_j))\right) \) 
where \(\mathsf {Jaccard}(s_i ,t_j)\)  is the token-level Jaccard
similarity over tokens in query column \(s_i\)  and
data lake column \(t_j\) . Note that we exclude “rating” columns
from \(T\)  to avoid any potential label leakage.
Overlap:  In this baseline, we simply replace Jaccard
similarity from above with the overlap score, i.e.,
\(\mathsf {Overlap}(s_i, t_j) :=|\mathsf {tokens}(s_i) \cap \mathsf {tokens}(t_j)|\) .
Starmie:  For \(\mathsf {Starmie}\) , we use the learned contextualized
embeddings for measuring similarities of columns.
Since the embeddings capture the table context of each column,
we expect the resulting data tables to be semantically relevant
to the query table. More formally, let \(\mathcal {M}\)  be the learned
column encoder, \(\mathsf {Starmie}\)  joins \(S\)  with the table

*T T(si S, tj T(cos(M(si), M(tj))) +
tj T(cos(M(starget), M(tj))) ) .

Note that we use the second term with the source
target column \(s_\mathsf {target}\)  (i.e., “Rating”) to take into account
the similarity between the target column with columns from the data lake table
\(T\) .
Lastly, an important implementation detail is to make sure
that the join result has the exact same number of rows with
the query table \(S\) . This is done by properly left-joining with
the data lake table \(T\) . This is done via the pandas
DataFrame command:
  # de-duplicate table T on column t_j
  T = T.drop_duplicates(subset=[t_j]).set_index(t_j)
  # left-join on the column pair (s_i, t_j)
  S.join(T, on=s_i)
<TABLE>