# LSH Ensemble: Internet-Scale Domain Search

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Mar 2016.

## Built on by (most cited first, 24 of 24)

- [DeepJoin: Joinable Table Discovery with Pre-trained Language Models](https://mlsanity.com/paper/2212.07588/) (2022)
- [Tabular Data Augmentation for Machine Learning: Progress and Prospects of Embracing Generative AI](https://mlsanity.com/paper/2407.21523/) (2024)
- [Observatory: Characterizing Embeddings of Relational Tables](https://mlsanity.com/paper/2310.07736/) (2023)
- [Cross Modal Data Discovery over Structured and Unstructured Data Lakes](https://mlsanity.com/paper/2306.00932/) (2023)
- [Retrieve, Merge, Predict: Augmenting Tables with Data Lakes](https://mlsanity.com/paper/2402.06282/) (2024)
- [LSHBloom: Memory-efficient, Extreme-scale Document Deduplication](https://mlsanity.com/paper/2411.04257/) (2024)
- [METAM: Goal-Oriented Data Discovery](https://mlsanity.com/paper/2304.09068/) (2023)
- [Snoopy: Effective and Efficient Semantic Join Discovery via Proxy Columns](https://mlsanity.com/paper/2502.16813/) (2025)
- [Empowering Tabular Data Preparation with Language Models: Why and How?](https://mlsanity.com/paper/2508.01556/) (2025)
- [Senatus -- A Fast and Accurate Code-to-Code Recommendation Engine](https://mlsanity.com/paper/2111.04473/) (2021)
- [Serving Deep Learning Model in Relational Databases](https://mlsanity.com/paper/2310.04696/) (2023)
- [Model Lakes](https://mlsanity.com/paper/2403.02327/) (2024)
- [DALL-M: Context-Aware Clinical Data Augmentation with LLMs](https://mlsanity.com/paper/2407.08227/) (2024)
- [HyperJoin: LLM-augmented Hypergraph Link Prediction for Joinable Table Discovery](https://mlsanity.com/paper/2601.01015/) (2026)
- [TabSketchFM: Sketch-based Tabular Representation Learning for Data Discovery over Data Lakes](https://mlsanity.com/paper/2407.01619/) (2024)
- [MYCROFT: Towards Effective and Efficient External Data Augmentation](https://mlsanity.com/paper/2410.08432/) (2024)
- [Something's Fishy In The Data Lake: A Critical Re-evaluation of Table Union Search Benchmarks](https://mlsanity.com/paper/2505.21329/) (2025)
- [DeKeyNLU: Enhancing Natural Language to SQL Generation through Task Decomposition and Keyword Extraction](https://mlsanity.com/paper/2509.14507/) (2025)
- [LSH methods for data deduplication in a Wikipedia artificial dataset](https://mlsanity.com/paper/2112.11478/) (2021)
- [Conceptual Schema Inference for Tabular Datasets using Large Language Models](https://mlsanity.com/paper/2509.04632/) (2025)
- [MetaJoin: Adaptive Join Selections for Heterogeneous Tables](https://mlsanity.com/paper/2512.02444/) (2025)
- [ModelTables: A Corpus of Tables about Models](https://mlsanity.com/paper/2512.16106/) (2025)
- [Nexus: Inferring Join Graphs from Metadata Alone via Iterative Low-Rank Matrix Completion](https://mlsanity.com/paper/2602.08186/) (2026)
- [MosaicJoin: Compact Semantic Sketches for Value-Level Join Discovery](https://mlsanity.com/paper/2607.21781/) (2026)

## Abstract (arXiv)

We study the problem of domain search where a domain is a set of distinct values from an unspecified universe. We use Jaccard set containment, defined as |Q cap X|/|Q|, as the relevance measure of a domain X to a query domain Q. Our choice of Jaccard set containment over Jaccard similarity makes our work particularly suitable for searching Open Data and data on the web, as Jaccard similarity is known to have poor performance over sets with large differences in their domain sizes. We demonstrate that the domains found in several real-life Open Data and web data repositories show a power-law distribution over their domain sizes. We present a new index structure, Locality Sensitive Hashing (LSH) Ensemble, that solves the domain search problem using set containment at Internet scale. Our index structure and search algorithm cope with the data volume and skew by means of data sketches (MinHash) and domain partitioning. Our index structure does not assume a prescribed set of values. We construct a cost model that describes the accuracy of LSH Ensemble with any given partitioning. This allows us to formulate the partitioning for LSH Ensemble as an optimization problem. We prove that there exists an optimal partitioning for any distribution. Furthermore, for datasets following a power-law distribution, as observed in Open Data and Web data corpora, we show that the optimal partitioning can be approximated using equi-depth, making it efficient to use in practice. We evaluate our algorithm using real data (Canadian Open Data and WDC Web Tables) containing up over 262 M domains. The experiments demonstrate that our index consistently outperforms other leading alternatives in accuracy and performance. The improvements are most dramatic for data with large skew in the domain sizes. Even at 262 M domains, our index sustains query performance with under 3 seconds response time.