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) [1]} has been used in previous studies of table search to find joinable [2]}, unionable [3]}, and related columns [4]} 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 [5]} 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) [6]}.
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.
