# MosaicJoin: Compact Semantic Sketches for Value-Level Join Discovery

arXiv: https://arxiv.org/abs/2607.21781 · HTML: https://mlsanity.com/paper/2607.21781/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 35 of its 75 references that are in the map.
- First posted on arXiv 23 Jul 2026.

## Builds on (most cited first, 30 of 35)

- [Gemini 2.5: Pushing the Frontier with Advanced Reasoning, Multimodality, Long Context, and Next Generation Agentic Capabilities](https://mlsanity.com/paper/2507.06261/) (2025)
- [ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT](https://mlsanity.com/paper/2004.12832/) (2020)
- [MPNet: Masked and Permuted Pre-training for Language Understanding](https://mlsanity.com/paper/2004.09297/) (2020)
- [C-Pack: Packed Resources For General Chinese Embeddings](https://mlsanity.com/paper/2309.07597/) (2023)
- [Matryoshka Representation Learning](https://mlsanity.com/paper/2205.13147/) (2022)
- [EmbeddingGemma: Powerful and Lightweight Text Representations](https://mlsanity.com/paper/2509.20354/) (2025)
- [Semantics-aware Dataset Discovery from Data Lakes with Contextualized Column-based Representation Learning](https://mlsanity.com/paper/2210.01922/) (2022)
- [Dataset search: a survey](https://mlsanity.com/paper/1901.00735/) (2019)
- [SANTOS: Relationship-based Semantic Table Union Search](https://mlsanity.com/paper/2209.13589/) (2022)
- [MUVERA: Multi-Vector Retrieval via Fixed Dimensional Encodings](https://mlsanity.com/paper/2405.19504/) (2024)
- [Dataset Discovery in Data Lakes](https://mlsanity.com/paper/2011.10427/) (2020)
- [LSH Ensemble: Internet-Scale Domain Search](https://mlsanity.com/paper/1603.07410/) (2016)
- [Efficient Joinable Table Discovery in Data Lakes: A High-Dimensional Similarity-Based Approach](https://mlsanity.com/paper/2010.13273/) (2020)
- [Auctus: A Dataset Search Engine for Data Augmentation](https://mlsanity.com/paper/2102.05716/) (2021)
- [Auto-FuzzyJoin: Auto-Program Fuzzy Similarity Joins Without Labeled Examples](https://mlsanity.com/paper/2103.04489/) (2021)
- [DeepJoin: Joinable Table Discovery with Pre-trained Language Models](https://mlsanity.com/paper/2212.07588/) (2022)
- [ArcheType: A Novel Framework for Open-Source Column Type Annotation using Large Language Models](https://mlsanity.com/paper/2310.18208/) (2023)
- [WarpGate: A Semantic Join Discovery System for Cloud Data Warehouses](https://mlsanity.com/paper/2212.14155/) (2022)
- [Pylon: Semantic Table Union Search in Data Lakes](https://mlsanity.com/paper/2301.04901/) (2023)
- [Correlation Sketches for Approximate Join-Correlation Queries](https://mlsanity.com/paper/2104.03353/) (2021)
- [AutoDDG: Automated Dataset Description Generation using Large Language Models](https://mlsanity.com/paper/2502.01050/) (2025)
- [SilkMoth: An Efficient Method for Finding Related Sets with Maximum Matching Constraints](https://mlsanity.com/paper/1704.04738/) (2017)
- [MATE: Multi-Attribute Table Extraction](https://mlsanity.com/paper/2110.00318/) (2021)
- [Retrieve, Merge, Predict: Augmenting Tables with Data Lakes](https://mlsanity.com/paper/2402.06282/) (2024)
- [Data Polygamy: The Many-Many Relationships among Urban Spatio-Temporal Data Sets](https://mlsanity.com/paper/1610.06978/) (2016)
- [Table Enrichment System for Machine Learning](https://mlsanity.com/paper/2204.08235/) (2022)
- [Snoopy: Effective and Efficient Semantic Join Discovery via Proxy Columns](https://mlsanity.com/paper/2502.16813/) (2025)
- [DTT: An Example-Driven Tabular Transformer for Joinability by Leveraging Large Language Models](https://mlsanity.com/paper/2303.06748/) (2023)
- [FREYJA: Efficient Join Discovery in Data Lakes](https://mlsanity.com/paper/2412.06637/) (2024)
- [Efficiently Transforming Tables for Joinability](https://mlsanity.com/paper/2111.09912/) (2021)

## Abstract (arXiv)

Join discovery is a core task in dataset search, enabling users to find columns that can be joined with a given query column. Early approaches focused on equi-joins, but data lakes and open-data repositories often contain columns whose values refer to the same entity but use different syntactic representations. To address this challenge, recent approaches discover semantically joinable columns but face a fundamental trade-off: methods that perform value-level comparisons accurately identify joinable columns but scale poorly to columns with high cardinality; column-level methods that encode an entire column into a single embedding are efficient but do not capture the fine-grained value alignment that determines whether a join is possible. We present MosaicJoin, a value-level semantic join discovery method that balances this trade-off. MosaicJoin achieves scalability through a novel sketching strategy that approximates the joinability of a column pair without having to compare all values. At query time, MosaicJoin scores each candidate sketch using a joinability score at a cost bounded by the sketch size, making retrieval efficient even for high-cardinality columns. A query subsampling operator further reduces online search time with provable accuracy guarantees, enabling robust retrieval for large query columns. Extensive experiments show that MosaicJoin outperforms previously published methods across all benchmarks while running up to 66 times faster than other value-level methods. MosaicJoin requires no training or fine-tuning, and it scales robustly to query columns containing up to 57K values and data lake columns containing up to 1M values.