Exploring Semantic Table Search in Data Lakes

Martin Pekár Christensen, Matteo Lissandrini, Katja HosearXiv 2026 · arXiv

TL;DR

Thetis++ is a novel framework that bridges the gap between keyword-based and semantic table search in massive, heterogeneous data lakes. By combining Knowledge Graph-driven entity relevance with traditional keyword matching and introducing a high-performance HNSW-based indexing strategy, it achieves a 4.7x speedup in search time while significantly improving the recall of relevant datasets.

What Problem Does This Paper Address?

Data lakes have become the go-to repository for organizations to store vast amounts of diverse data. However, finding the "right" table for a specific data science task is like finding a needle in a haystack.

Existing methods generally fall into two camps:

  1. Syntactic/Keyword Search: Great for finding exact matches (e.g., "Chicago Cubs"), but misses tables that are semantically related but use different terminology.
  2. Join/Union Search: Effective for augmenting existing tables, but requires strict structural overlap, which is often absent in exploratory search.

The authors identify a "semantic gap": how do we find tables that are topically relevant to a user's intent—expressed through a few example entities—even when those tables don't share exact keywords or structure? Furthermore, how do we do this at the scale of millions of tables without the system grinding to a halt?

The relationship between different table search paradigms.

Methods

The authors propose Thetis++, a multi-criteria ranking system that fuses two distinct signals:

  • Semantic Relevance (SemRel): This component treats the user's query as a set of "exemplar tuples" (Query-by-Example). It links entities in the query and the target tables to a reference Knowledge Graph (KG). It then uses the Hungarian Method to find the optimal mapping between query entities and table columns. Relevance is calculated based on the weighted Euclidean distance between entity embeddings in a vector space.
  • Keyword Search (BM25): A standard, high-performance text retrieval algorithm used to capture exact syntactic matches.
  • Ranking Fusion: To combine these signals, the authors explore several techniques, ultimately favoring a combination of Pareto optimality (to identify tables that are strong in at least one dimension) and TOPSIS (Technique for Order of Preference by Similarity to Ideal Solution) to produce a final, unified ranking.
The architecture of Thetis++, showing the parallel semantic and keyword search pipelines.

To solve the scalability issue, the paper moves beyond standard Locality-Sensitive Hashing (LSH). They implement Hierarchical Navigable Small Worlds (HNSW), a graph-based index for approximate nearest neighbor search, to pre-filter the search space. This allows the system to quickly prune millions of irrelevant tables before performing the expensive semantic ranking.

Datasets

The authors evaluated Thetis++ using a mix of real-world and synthetic benchmarks:

  • WikiTables (2015 & 2019): A corpus of ~238k and ~457k tables extracted from Wikipedia, complete with ground-truth relevance annotations.
  • GitTables: A massive collection of ~864k tables from GitHub, used primarily to test scalability and runtime.
  • Synthetic Dataset: A stress-test corpus of up to 1.7 million tables generated to evaluate the linear scaling of the pre-filtering techniques.
  • DBpedia (2021): Used as the reference Knowledge Graph for entity linking and embeddings.

Key Insights and Ideas

  • Complementarity is Key: Keyword and semantic search find remarkably different sets of relevant tables. By merging them, Thetis++ captures "the best of both worlds"—exact matches and deep topical relevance.
  • HNSW vs. LSH: While LSH is a standard for vector search, HNSW is significantly more efficient for this specific task. It provides a much higher search space reduction while maintaining (and sometimes even improving) ranking quality by removing "false positive" tables early.
  • Robustness to Incomplete Data: A major "aha moment" is that semantic search works even with low entity-linking coverage. Even if only 20-30% of a table's cells are linked to the KG, the system can still infer enough context to rank it accurately.
  • Pareto-TOPSIS Fusion: The authors found that a simple weighted average isn't enough. Using Pareto fronts ensures that a table isn't penalized too harshly for having a low score in one dimension if it is exceptionally strong in the other.

Key Results

  • Efficiency: HNSW pre-filtering improved the runtime of semantic table search by 4.7x on average (and up to 28x in some cases) compared to exhaustive search, outperforming LSH by a wide margin.
  • Effectiveness: Combining keyword and semantic signals led to a massive boost in recall. For 5-tuple queries, the combined approach improved recall by 156.6% over using BM25 alone.
  • Scalability: The system demonstrated near-linear runtime scaling as the data lake size increased from 500k to 1.7M tables.
The semantic table search algorithm: from column mapping to final scoring.

Limitations and Future Work

  • Knowledge Graph Dependency: The system's semantic "intelligence" is bound by the quality and coverage of the underlying Knowledge Graph (e.g., DBpedia). Future work could explore using larger KGs like Wikidata or integrating multiple KGs.
  • Learning-to-Rank (LTR): While the authors tested a supervised LTR approach, it proved unstable for very small queries. They suggest that more sophisticated models or larger training sets might be needed to make LTR the dominant fusion method.
  • Reciprocal Rank Fusion (RRF): The authors identify RRF as a promising alternative for multi-criteria ranking that warrants future investigation.

Summary updated

Abstract

Discovery of relevant datasets within data lakes remains a key challenge. Union and join search are effective techniques for discovering data when augmenting an existing table. In exploratory search, instead, keyword search is commonly adopted to find a relatively small set of highly relevant tables matching some search terms. In this context, semantic search is a new technique that exploits the presence of named entities in exemplar tuples used as queries and in target tables. Hence, keyword search and entity search are able to find a diverse set of tables. In this work, we propose \texttt{Thetis++}, which combines keyword and semantic table search to discover relevant tables that combine the semantic signal with the presence of exact keyword matches. Incorporating multiple paradigms and sources of information allow us to combine the best of multiple worlds. Therefore, we study many alternative techniques for combining rankings and evaluate these for the table search task in data lakes. We explore both unsupervised and supervised techniques, including TOPSIS. Finally, alternative to Thetis++ combining keyword and semantic relevance signals, we study a variant of learning-to-rank for the table search task in data lakes. Our evaluation highlights both the limitations of many standard approaches along with some promising directions offered by learned approaches. Furthermore, while indexes for keyword search are quite efficient, here we provide insights into how to improve the scalability of prefiltering techniques for semantic search, comparing LSH indexes with Hierarchical Navigable Small Worlds. Our experiments show that HNSW drastically improves the runtime of semantic table search by 4.7X on average whilst retaining the high-quality tables. Together, our findings plot the line for effective and efficient data discovery techniques for semantic data lakes.
BibTeX
@misc{christensen2026exploring,
  author = {Martin Pekár Christensen and Matteo Lissandrini and Katja Hose},
  title = {{Exploring Semantic Table Search in Data Lakes}},
  year = {2026},
  eprint = {2611.25691},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.25691},
}
Figure