  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.
