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:
- Syntactic/Keyword Search: Great for finding exact matches (e.g., "Chicago Cubs"), but misses tables that are semantically related but use different terminology.
- 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?
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.
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.
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