PaperlayerView exact revision on arXiv

Source-linked AI summary

LSH Ensemble: Internet-Scale Domain Search

Erkang Zhu, Fatemeh Nargesian, Ken Q. Pu, Renée J. Miller

arXiv:1603.07410v4cs.DB

TL;DR

The paper addresses domain search over massive, heterogeneous Web and Open Data collections where relevant domains should contain a query domain despite skewed sizes. It introduces LSH Ensemble, combining MinHash sketches, partitioning, and a cost model, and reports scalable, accurate search at up to 262 million domains.

  • Problem

    Domain search must identify domains that contain a query domain across hundreds of millions of domains, unseen values, skewed sizes, and limited Web data access.

  • Method

    LSH Ensemble uses MinHash-based indexing, domain partitioning, and a cost model that optimizes partitioning for set-containment search.

  • Results

    LSH Ensemble consistently improves accuracy and performance over alternatives, sustains query times of a few seconds at 262 million domains, and is sometimes ∼15 times faster than MinHash LSH.

  • Takeaways & Limitations

    For power-law domain-size distributions, equi-depth partitioning approximates the optimal partitioning and supports efficient Internet-scale containment search.

  • Takeaways & Limitations

    The optimal partitioning is query dependent, and dynamic LSH assumes a Jaccard-similarity-threshold search algorithm for each partition.

Abstract

from arXiv · show

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.

1. INTRODUCTION

The paper defines domain search for discovering joinable Open Data and Web data despite heterogeneous formats, limited access, and highly skewed domain sizes. It introduces LSH Ensemble, combining MinHash-based indexing with partitioning and a cost model for Internet-scale containment search.

  • Data setting: Open Data and Web repositories contain massive, heterogeneous collections of relational, semi-structured, graph-based, and geo-spatial datasets.The paper describes domains as sets of values within well-structured attributes and notes large public Web-table collections.
  • Motivation: Limited schema descriptions, bulk-only access, and low Web bandwidth make relevant datasets difficult to identify and access.These constraints make conventional sorting, scanning, joining, and ad hoc data access impractical over the Web.
  • Domain search: Domain search finds domains that contain as much of a query domain as possible, supporting discovery of tables that can join on shared attributes.The motivating example searches for tables containing much of an industry-partner domain.
  • Requirements: The problem must handle hundreds of millions of domains, unseen values, skewed domain sizes, compact indexes, and small query representations.Observed domain-size distributions in the Canadian Open Data and WDC corpora follow power-law patterns.
  • Approach: LSH Ensemble uses set containment, MinHash sketches, domain partitioning, and a partitioning cost model to support scalable search over skewed data.The paper formulates partitioning as an optimization problem and proves an optimal scheme exists for any distribution.
  • Evaluation: Experiments report consistently better accuracy and performance than leading alternatives, including query times of a few seconds at hundreds of millions of domains.The conclusion also reports cases where LSH Ensemble is approximately 15 times faster than MinHash LSH for containment queries.

2. PROBLEM DEFINITION

The paper formalizes domain search as approximate threshold search using asymmetric Jaccard set containment rather than Jaccard similarity. The formulation targets Internet-scale collections with skewed domain sizes and arbitrarily large query domains.

  • Definitions: A domain is a set of values, and a relational table’s domains are projections of its attributes.A dataset may contain multiple domains, represented as dom(R).
  • Relevance measure: Set containment measures overlap relative to the query domain, making it asymmetric and suitable for finding domains that mostly contain the query.For join discovery, high |X ∩ Y|/|X| indicates that a source domain X is highly contained by Y.
  • Problem formulation: Domain search seeks domains whose set containment with a query domain meets a specified threshold.The task is formalized as an R-nearest neighbor problem over a collection of domains.
  • Relevance measure: Jaccard similarity can favor smaller domains when compared with much larger domains, whereas set containment is agnostic to domain-size differences.In the example, similarity ranks Provinces above Locations, while containment ranks Locations above Provinces.
  • Constraints: The search setting includes hundreds of millions of domains, highly skewed domain sizes, and query domains with arbitrarily large cardinality.The desired approximate solution should provide efficient indexing and search with compact growth and sublinear domain search.
  • Search objective: Threshold search is preferred for join discovery because top-k results are not guaranteed to provide sufficient overlap with the query domain.The paper treats threshold and top-k formulations as related and complementary.

3. PRELIMINARIES

The preliminaries explain MinHash and LSH as compact approximate-search tools, then establish how their collision behavior supports candidate retrieval. Standard MinHash LSH is naturally tied to Jaccard similarity.

  • MinHash: Minwise hashing converts each domain into a compact signature using independently generated hash functions and minimum hash values.Each hash function returns the minimum hash value observed over a domain.
  • MinHash: The probability that two domains share a minimum hash value equals their Jaccard similarity, enabling an unbiased collision-based estimate.Similarity is estimated by counting corresponding minimum-hash collisions divided by the signature length.
  • LSH: LSH maps similar signatures to common buckets with higher probability than dissimilar signatures, supporting approximate R-near-neighbor search.The underlying distance measure for standard LSH is symmetric.
  • MinHash LSH: MinHash LSH divides signatures into b bands of r hash values and retrieves domains sharing at least one query bucket.The resulting search time depends on signature size and is sublinear in the number of indexed domains.
  • Parameterization: The candidate probability depends on Jaccard similarity and the parameters b and r, which can be tuned for a target similarity threshold.Tuning seeks high candidate probability above the threshold and low probability below it.

4. RELATED WORK

Related work spans keyword and vector-based indexes, containment-specific hashing, schema matching, and table search. The paper positions LSH Ensemble as a scalable set-containment method for domains with widely varying sizes.

  • Keyword search: Keyword-search indexes are related because results should contain query values, but domain search treats the entire domain as a potentially large query.Generating one keyword per domain value is therefore not a direct scalable solution.
  • Other LSH indexes: Many alternative LSH methods assume fixed-dimensional vectors, making binary-vector representations impractical when unique domain values define dimensions.SimHash avoids a prescribed value set and is applicable to domain search, but the paper uses MinHash LSH in evaluation.
  • Containment search: Asymmetric Minwise Hashing supports containment by padding indexed domains so they share the size of the largest domain, then applying MinHash LSH.The transformation makes Jaccard similarity between query and indexed signatures monotonic with set containment.
  • Notation: Table 2 summarizes the symbols used in the paper’s analysis.The table is presented as a notation reference rather than an algorithmic comparison.
  • Schema matching: LSH Ensemble targets matching one query domain against extremely large collections whose domain sizes range from a few values to millions.The paper notes possible applications in large-scale schema and ontology matching.
  • Table search: Semantic table-search systems use annotations, context, or metadata, whereas the paper’s approach searches using set containment over table content.These semantic approaches are described as complementary to the paper’s method.

5. LSH ENSEMBLE

LSH Ensemble addresses containment search by partitioning domains by size and applying dynamically tuned MinHash LSH indexes to each partition. Its conservative threshold conversion avoids false negatives, while cost-based partitioning controls false positives and equi-depth approximates the optimum for power-law domain sizes.

  • Index Structure: LSH Ensemble indexes domains in two stages: cardinality-based partitioning followed by a MinHash LSH index for each partition.Each partition's LSH index is dynamically tuned with a partition-specific Jaccard similarity threshold.
  • Threshold Conversion: Containment thresholds are conservatively converted to Jaccard similarity thresholds using the partition's upper domain-size bound, avoiding approximation-induced false negatives.The upper bound yields a threshold no greater than the exact threshold because the transformation decreases monotonically with domain size.
  • False-Positive Modeling: False positives arise when domains pass the approximated similarity threshold despite falling below the desired containment threshold.For a domain in [l,u), its true containment lies between an effective threshold and t∗.
  • False-Positive Modeling: Under uniform domain-size distributions within a partition, Proposition 2 gives an upper bound on the number of candidate domains that are false positives.The bound is tight when the upper domain-size bound is much larger than the query size.
  • Optimal Partitioning: The partitioning objective minimizes the false-positive cost, and an optimal partitioning exists with an equal number of false positives in every partition.This equi-FP property follows from Theorem 1 and supports optimization over partition boundaries.
  • Optimal Partitioning: For power-law domain-size distributions, equi-depth partitioning is an efficient approximation to the optimal partitioning.Theorem 2 connects equal-domain-count partitions with equi-Mi partitioning under the power-law assumption.

6. EXPERIMENTAL ANALYSIS

Experiments on Canadian Open Data and the WDC Web Table Corpus evaluate LSH Ensemble against MinHash LSH and Asymmetric Minwise Hashing for accuracy, robustness, and efficiency. Partitioning improves precision and query performance, while limiting recall trade-offs and reducing sensitivity to skew.

  • Experimental Setup: 65,533 Canadian Open Data domains support ground-truth accuracy evaluation, while the WDC corpus provides an Internet-scale test with 262 million domains.The Canadian corpus uses 3,000 sampled query domains; the WDC corpus contains 51 million relations and 262 million domains.
  • Accuracy: Equi-depth partitioning improves precision over the MinHash LSH baseline, with additional partitions increasing precision but diminishing relative gains.Partitioning also introduces a recall decrease of about 0.02 whenever the number of partitions doubles.
  • Accuracy: LSH Ensemble improves Fβ overall accuracy over the baseline by as much as 25%.The evaluation uses β=1 for equal weighting and β=0.5 for precision-biased scoring.
  • Skewness: As domain-size skew increases, precision decreases for all indexes, but LSH Ensemble is less affected because partition bounds better approximate domain sizes.Increasing the number of partitions further reduces the effect of skew; Asymmetric Minwise Hashing suffers substantial recall loss as skew increases because of padding.
  • Dynamic Data: Partitioning remains accurate under substantial distribution changes: precision stays almost unchanged until partition-size standard deviation exceeds 5,556, over 2.7 times the equi-depth size of 2,047.The authors conclude that rebuilding may be needed after drastic distribution changes, but such changes are expected to be rare.
  • Efficiency: LSH Ensemble has similar indexing cost across partition counts, while parallelism and improved selectivity make query cost significantly smaller than basic MinHash LSH.Indexing scales linearly with the number of domains, and query cost grows more slowly with more partitions because fewer candidates are returned.

7. CONCLUSION AND FUTURE WORK

The paper formulates domain search with set containment and presents LSH Ensemble as a scalable solution for highly skewed, Internet-scale domain collections. Evaluation shows strong accuracy and performance, including few-second queries over 262 million domains.

  • Contributions: LSH Ensemble uses MinHash LSH and domain partitioning to perform set-containment queries over hundreds of millions of skewed domains.Its cost model supports partitioning design, with optimal schemes characterized for arbitrary distributions and approximated by equi-depth for power-law data.
  • Evaluation: 262 million domains: LSH Ensemble sustains query times of a few seconds while consistently outperforming alternatives in accuracy and performance.The evaluation uses the Canadian Open Data repository and the English relational WDC Web Table Corpus.
  • Evaluation: ~15 times faster: LSH Ensemble outperforms a MinHash LSH index for set-containment queries in some cases.The reported speedup is part of the broader evaluation across real Open Data and Web Table collections.

Appendix Proof of Proposition 2

The proof derives false-positive probabilities for domain-size intervals under effective containment thresholds. It handles five interval configurations, using the domain-size distribution and a uniform-within-partition assumption for evaluation.

  • Setup: False-positive probability depends on domain size x, its distribution P(x), and the effective containment threshold for query size q.The threshold is defined for each domain size using the query-given containment threshold t∗.
  • Case analysis: For any domain of size x, containment is bounded by min {1.0, x/q}, so interval subranges can have different false-positive probabilities.The proof therefore separates the analysis into five cases based on interval boundaries and threshold locations.
  • Case analysis: Five cases cover all relative placements of interval bounds and effective thresholds, including intervals with zero false-positive probability.Cases include domains unable to meet the relevant threshold and complete intervals whose false-positive probability is zero.
  • Evaluation: Uniform domain-size distribution within a partition is assumed when evaluating the expected number of false positives.This assumption is used in the interval calculations for N_FP.

Proof of Theorem 1

The theorem proves that equalizing false positives across partitions yields an optimal partitioning under the stated monotonicity property. Moving a boundary changes the false-positive counts of adjacent partitions in opposite directions.

  • Monotonicity: False positives in a partition increase monotonically as its width increases by raising its upper bound, lowering its lower bound, or both.This monotonicity underpins the boundary-shifting argument.
  • Optimality: An n-partition scheme with equal false-positive counts across partitions is an optimal partitioning.The proof starts from an equi-N_FP partitioning and shows that any boundary change cannot reduce the maximum false-positive count.
  • Boundary argument: Changing the boundary between adjacent partitions decreases one partition’s false positives while increasing the other’s, preventing a lower-cost scheme.The argument compares the affected adjacent partitions after increasing their shared boundary.

Asymmetric Minwise Hashing

The paper reviews Asymmetric Minwise Hashing and explains why it is unsuitable for domain search when domain sizes are highly skewed.

  • Motivation: Asymmetric Minwise Hashing is discussed as a MinHash-based approach whose suitability is limited for highly skewed domain-size distributions.The section provides background and motivates the need for an alternative domain-search approach.

Preliminaries

Asymmetric Minwise Hashing pads domains to a common size while preserving containment, then uses the resulting monotonic Jaccard similarity in MinHash LSH candidate selection.

  • Asymmetric Minwise Hashing: Padding domains to the upper bound M preserves containment scores because added values do not overlap original domains or queries.The padded domains are made equal in size before insertion into the MinHash LSH index.
  • Asymmetric Minwise Hashing: The converted Jaccard similarity depends only on containment score t and query size q when M is fixed, and increases monotonically with t.This monotonicity enables containment-based ordering after conversion.
  • Candidate Selection: Because candidate probability in MinHash LSH depends on Jaccard similarity, padded-domain candidate probability is also monotonic in containment score.The method therefore links containment relevance to LSH candidate selection through the padded representation.

Impact of Skewed Domain Sizes

Skewed domain sizes can sharply reduce Asymmetric Minwise Hashing recall when large domains are padded, while compensating with more hash functions increases index cost.

  • Recall Impact: The candidate-selection probability decreases rapidly as M increases, even when MinHash LSH is tuned with r = 1 and b = 256.The example assumes q = 1 and 256 total hash functions.
  • Recall Impact: Very large upper bounds M relative to query size can make qualifying padded domains almost impossible to select, producing very low recall.This issue occurs in power-law domain-size distributions observed in Canadian Open Data and WDC Web Tables, and experiments confirm it.
  • Cost Trade-off: Maintaining candidate probability above 0.5 requires a minimum hash-function count m* that grows linearly with M.This relationship is shown in the right plot of Figure 10 and is derived from Equation 32.
  • Cost Trade-off: Increasing the number of hash functions can preserve probability but raises MinHash LSH construction and search costs, reducing performance when excessive.The hash-function increase is therefore a direct performance trade-off for mitigating skew-induced recall loss.
Loading 1603.07410v4…