PaperlayerView exact revision on arXiv

Source-linked AI summary

PASS-JOIN: A Partition-based Method for Similarity Joins

Guoliang Li, Dong Deng, Jiannan Wang, Jianhua Feng

arXiv:1111.7171v1cs.DB

TL;DR

Edit-distance similarity joins must efficiently find similar pairs across large string collections, but existing methods support short or long strings rather than both adaptively. Pass-Join partitions strings, indexes segments, selects substrings for candidate generation, and verifies candidates with pruning techniques. Experiments report efficiency on both short and long strings and improved performance over state-of-the-art methods on real datasets.

  • Problem

    Existing algorithms are efficient either for short strings or for long strings, creating a need for one adaptive method that supports both.

  • Method

    Pass-Join partitions strings into segments, builds inverted indices, selects substrings for candidate generation, and verifies candidates using pruning techniques.

  • Results

    Experiments show that Pass-Join is efficient for both short and long strings and outperforms state-of-the-art methods on real datasets.

  • Takeaways & Limitations

    Pass-Join provides a partition-based similarity-join framework intended to efficiently handle both short-string and long-string datasets.

  • Takeaways & Limitations

    The paper uses an even-partition scheme and leaves selecting good partition strategies as future work.

Abstract

from arXiv · show

As an essential operation in data cleaning, the similarity join has attracted considerable attention from the database community. In this paper, we study string similarity joins with edit-distance constraints, which find similar string pairs from two large sets of strings whose edit distance is within a given threshold. Existing algorithms are efficient either for short strings or for long strings, and there is no algorithm that can efficiently and adaptively support both short strings and long strings. To address this problem, we propose a partition-based method called Pass-Join. Pass-Join partitions a string into a set of segments and creates inverted indices for the segments. Then for each string, Pass-Join selects some of its substrings and uses the selected substrings to find candidate pairs using the inverted indices. We devise efficient techniques to select the substrings and prove that our method can minimize the number of selected substrings. We develop novel pruning techniques to efficiently verify the candidate pairs. Experimental results show that our algorithms are efficient for both short strings and long strings, and outperform state-of-the-art methods on real datasets.

1. INTRODUCTION

String similarity joins find string pairs whose edit distance is within a threshold, supporting applications such as data cleaning. Pass-Join addresses the lack of one efficient method for both short and long strings with a partition-based framework, optimized substring selection, candidate verification, and pruning.

  • String similarity joins identify pairs across two string sets whose edit distance does not exceed a specified threshold.The operation supports data integration and cleaning, near-duplicate detection, and collaborative filtering.
  • Existing filter-and-refine methods are inefficient for short strings because they cannot select high-quality signatures.Supporting both short and long strings otherwise requires separate implementations and parameter tuning.
  • Pass-Join partitions strings into segments and uses inverted indices to locate candidate pairs through selected substrings.If two strings are similar, one substring of one string must match a segment of the other.
  • The method develops substring-selection techniques that generate candidate pairs while minimizing the number of selected substrings.The contributions include position-aware and multi-match-aware selection strategies.
  • Pass-Join develops extension-based verification, pruning, and early-termination techniques to improve candidate checking.These techniques target the cost of verifying candidate pairs after filtering.
  • Experiments show that the algorithms are efficient for both short and long strings and outperform state-of-the-art methods on real datasets.The paper reports extensive experiments supporting this result.

2. PROBLEM FORMULATION

The paper formalizes similarity joins over string collections using edit distance as the similarity measure. A pair is reported when its edit distance is at most the threshold τ, with self-joins treated as the primary case.

  • Edit distance is the minimum number of single-character insertions, deletions, and substitutions needed to transform one string into another.For example, the paper gives an edit distance of 4 for “kaushic chaduri” and “kaushuk chadhui”.
  • A similarity join returns all pairs ⟨r, s⟩ from R × S whose edit distance satisfies ed(r, s) ≤ τ.The threshold τ determines which string pairs are considered similar.
  • The primary formulation focuses on self-joins, where the two input collections are identical, R = S.The paper notes that joins between distinct sets are discussed separately.
  • For τ=3, “kaushik chakrab” and “caushik chakrabar” form a similar pair because their edit distance is no larger than the threshold.

3. PARTITION-BASED SIMILARITY JOINS

Pass-Join partitions strings into segments, indexes those segments, and uses matching substrings to generate and verify candidate pairs for edit-distance joins.

  • 3.1 Partition Scheme: Each string is partitioned into τ + 1 disjoint segments, subject to a minimum string-length condition.The paper uses an even-partition scheme whose segments have nearly equal lengths.
  • 3.1 Partition Scheme: If two strings are within edit distance τ, the candidate string must contain a substring matching a segment of the other string.This pigeonhole-based property enables pruning pairs without such a matching substring.
  • 3.2 Partition-based Framework: Pass-Join builds inverted indices for segment positions and uses them to find candidate strings among length-compatible records.Strings are processed in sorted order, with indices maintained for previously visited strings.
  • 3.2 Partition-based Framework: For each string, Pass-Join selects substrings, looks them up in inverted lists, and treats associated strings as candidates before verification.The baseline algorithm can enumerate all substrings, while the paper develops more efficient selection techniques separately.
  • 3.2 Partition-based Framework: Candidate verification computes the real edit distance, while extension-based and pruning techniques improve verification efficiency.The algorithm then partitions the processed string and inserts its segments into the corresponding inverted indices.
  • 3.2 Partition-based Framework: The framework maintains at most (τ + 1)^2 inverted indices and focuses on datasets whose index fits in memory.Space analysis accounts for τ + 1 segments generated per string.

4. IMPROVING SUBSTRING SELECTION

The substring-selection methods progressively reduce the number of substrings while preserving completeness for finding similar pairs under the edit-distance threshold.

  • 4. Improving Substring Selection: Selecting fewer substrings improves performance, motivating methods that construct smaller complete substring sets.Enumerating every substring is especially expensive for long strings.
  • Length-based Method: The length-based method selects every substring whose length matches a segment, yielding (τ + 1)(|s| + 1) − l selected substrings.It is complete because it includes all substrings of the required length.
  • Shift-based Method: The shift-based method selects substrings of the segment length whose start positions lie within [p_i − τ, p_i + τ], yielding (τ + 1)(2τ + 1) selections.It uses segment positions but can still retain unnecessary substrings.
  • Multi-match-aware Substring Selection: Multi-match-aware selection can discard a matching substring when the remaining portions must contain another matching segment under the pigeonhole argument.The rule considers both left- and right-side segment matches when narrowing positions.
  • Position-aware Substring Selection: The position-aware method restricts possible matching starts using edit-distance bounds while preserving completeness.Its selected-substring count is (τ + 1)^2, and Theorem 1 establishes completeness.
  • Position-aware Substring Selection: For a string r = “vankatesh” and s = “avataresha” with τ = 3, the position bounds reduce the first segment’s candidates to “av”, “va”, and “at”.This example illustrates pruning beyond the shift-based selection range.

4.2 Multi-match-aware Substring Selection

The multi-match-aware method removes redundant matching substrings while preserving completeness. It combines left- and right-side position constraints to reduce the selected substring set.

  • Multi-match-aware selection: Multiple substrings of s can match segments of r, so some matches can be discarded while retaining a later matching segment.The method uses remaining edit-error budgets and the pigeon-hole principle to discard earlier matches when a later segment must match.
  • Left-side constraint: A matching substring is retained when its left-side positional deviation satisfies Δ_l ≤ i − 1; otherwise a later matching segment can be used.The bound follows from the number of preceding segments and the edit distance needed to align the left parts.
  • Right-side constraint: The method also applies a right-side positional constraint, using the remaining τ + 1 − i segments to restrict possible matches.From the right-side perspective, position p_i in r aligns with p_i + Δ in s, and deviation is bounded by the right-part edit distance.
  • Combined selection: Combining both techniques selects substrings whose start positions lie within the jointly constrained interval for each segment length.The selected sets are denoted W_m(s, L_i^l), with bounds determined by the left and right constraints.
  • Selection size: ⌊τ^2 − Δ^2⌋ + τ + 1 selected substrings are used according to the stated size analysis.The supplied passages present this expression as the number of selected substrings for W_m(s, l).
  • Correctness: The multi-match-aware substring selection method satisfies completeness.Thus, every similar pair retains at least one selected substring capable of identifying it.

4.3 Comparison of Selection Methods

The multi-match-aware selection method produces nested, no-larger substring sets than the alternatives and has minimum size among complete selection methods. Under stated length conditions, it also satisfies minimality.

  • Set comparison: W_m(s, l) ⊆ W_p(s, l) ⊆ W_f(s, l) ⊆ W_ℓ(s, l), establishing nested selection sets across the methods.The corresponding sizes satisfy |W_m(s, l)| ≤ |W_p(s, l)| ≤ |W_f(s, l)| ≤ |W_ℓ(s, l)|.
  • Size optimality: W_m(s, l) has the minimum size among substring sets generated by methods that satisfy completeness.This result compares the multi-match-aware set against all complete selection methods, not only the three named alternatives.
  • Method comparison: The method’s minimum-size result is used to establish the superiority of its multi-match-aware selection strategy.The paper introduces minimality as an additional property after proving minimum cardinality.
  • Minimality: Minimality means W(s, l) is a subset of every substring set generated by a complete method.This definition formalizes minimality through set inclusion rather than only cardinality.
  • Minimality condition: If l ≥ 2(τ + 1) and |s| ≥ l, W_m(s, l) satisfies minimality.The length condition ensures each segment has at least two characters; examples give l ranges for τ = 4 and τ = 5.

4.4 Substring-selection Algorithm

The substring-selection algorithm improves candidate generation by avoiding unnecessary substrings and using multi-match-aware selection. Verification is further accelerated through length-aware pruning and early termination.

  • Substring selection: The improved SubstringSelection algorithm avoids unnecessary substrings and uses multi-match-aware selection with complexity O(τ).The method selects substrings for inverted-index lookup while reducing selection work.
  • Substring selection: For s2 = “avataresha”, the multi-match-aware method selects 8 substrings to search inverted indices for similar strings.The example illustrates how selected substrings generate candidate matches.
  • Length-aware verification: Length pruning computes only matrix cells satisfying |i −j| ≤τ, excluding cells whose edit distance must exceed τ.This reduces verification work because excluded cells cannot contribute to an acceptable transformation.
  • Length-aware verification: Length-aware verification uses the length difference Δ=|s|−|r| to omit matrix cells whose prefix and suffix length costs already exceed τ.The method assumes |s| ≥|r| and Δ≤τ; otherwise the pair cannot satisfy the threshold.
  • Early termination: The method computes a bounded matrix region and can terminate when every expected minimal edit distance in a row exceeds τ.Lemma 4 establishes that such a row proves the full edit distance exceeds the threshold.
  • Early termination: In the illustrated case with τ = 3, computation stops after row M(6, ∗) because every expected edit distance there exceeds 3.This avoids computing subsequent rows.

5.2 Extension-based Verification

Extension-based verification exploits a shared substring to align candidate strings and verify their left and right parts separately. Tighter thresholds enable additional pruning while preserving correctness.

  • Extension-based verification: For a candidate pair sharing substring w, extension-based verification partitions each string into left, matching, and right parts around w.The shared segment provides the alignment used for subsequent verification.
  • Correctness: The extension-based verification method satisfies correctness, so accepted pairs are similar and similar pairs pass verification.This is stated in Theorem 5.
  • Threshold pruning: The algorithm first verifies the left parts and then verifies the right parts using the remaining edit-distance threshold.The right-side threshold is τr = τ −dl after computing the left-side distance dl.
  • Threshold pruning: For the example with τ = 3, a right-part length difference of 2 gives the left-part threshold τl = 1.The left parts are therefore checked only against threshold 1.
  • Threshold pruning: The method tightens thresholds using segment position, setting τl=i−1 and τr=τ+1−i under the stated pruning conditions.These bounds combine multi-match-aware pruning with the remaining verification budget.

5.3 Sharing Computations

Sharing computations reduces repeated edit-distance work across candidates in the same inverted list. The improved verification algorithm combines shared-prefix reuse with tighter bounds and retains completeness and correctness.

  • Sharing computations: Large inverted lists may contain many candidate strings, motivating shared edit-distance computations for common prefixes.The strings are visited in alphabetical order to expose reusable prefixes.
  • Sharing computations: For consecutive candidates, the algorithm reuses the stored dynamic-programming matrix for their longest common prefix.It computes the remaining portion after identifying the shared prefix.
  • Improved verification: The improved Verification algorithm sets τl=i−1 and τr=τ+1−i before checking candidate pairs.These thresholds support early termination during left- and right-part verification.
  • Correctness and completeness: Theorem 6 states that the algorithm is both complete and correct: it finds every similar pair and returns only similar pairs.This establishes the required answer-set guarantees.

6. EXPERIMENTAL STUDY

Experiments evaluate Pass-Join's datasets, substring selection, verification, comparisons with existing methods, index sizes, and scalability. Pass-Join performs well across short and long strings, with efficient selection and verification and nearly linear scaling.

  • Experimental Setup: Experiments use three real datasets covering short strings, long strings, and query logs.The datasets are DBLP Author, DBLP Author+Title, and AOL Query Log.
  • Substring Selection: Multi-match selected about half as many substrings as Position, while Position selected roughly one-tenth to one-fourth as many as Length.For |s|=15 and τ=1, the four methods selected 17, 6, 4, and 2 substrings, respectively.
  • Verification: The length-aware method was 2–5 times faster than the naive verifier, and Extension was 2–4 times faster than length-aware verification.SharePrefix performed best by avoiding duplicated computations and exploiting common prefixes.
  • Comparison with Existing Methods: On long strings, Pass-Join outperformed ED-Join and Trie-Join by 2–3 orders of magnitude.For τ=8, Trie-Join took 15,000 seconds, ED-Join 5,000 seconds, and Pass-Join 130 seconds on Author+Title.
  • Index Size: Pass-Join used a 2.1 MB index on Author+Title, compared with 335 MB for ED-Join and 90 MB for Trie-Join.The smaller index reflects maintaining τ+1 segments and restricting indexed string lengths.

7. RELATED WORK

Related work includes filter-and-refine, q-gram, trie-based, signature-based, metric-space, and approximate-search approaches. The paper distinguishes similarity joins from approximate string-searching tasks and compares against the strongest relevant methods.

  • Similarity-Join Methods: All-Pairs-Ed uses q-grams and gram prefixes, while ED-Join adds location-based and content-based mismatch filtering.The paper states that ED-Join outperforms All-Pairs-Ed.
  • Similarity-Join Methods: Trie-Join performs similarity joins with prefix filtering through a trie structure, and Part-Enum uses signatures for Hamming-distance joins.The paper reports that All-Pairs-Ed and Part-Enum are worse than ED-Join and Trie-Join.
  • Comparison Basis: The paper compares Pass-Join with ED-Join and Trie-Join because they outperform the other selected similarity-join methods.This comparison choice is stated explicitly in the related-work discussion.
  • Problem Scope: Other studies address metric-space joins, token-error similarity, or approximate searching rather than the paper's two-set edit-distance join problem.Approximate string searching finds strings or substrings similar to a query, whereas similarity joins find pairs across two sets.

8. CONCLUSION

The conclusion presents Pass-Join as a partition-based approach for efficient edit-distance similarity joins. Its selection and verification techniques support strong performance on both short and long strings.

  • Method: Pass-Join partitions strings, builds inverted indices, and selects substrings to generate candidate pairs.The method uses position-aware and multi-match-aware selection techniques.
  • Techniques: The multi-match-aware method minimizes the number of selected substrings.Verification combines length-difference techniques, extension, and shared-prefix computation.
  • Results: Experiments show that Pass-Join outperforms state-of-the-art studies on both short and long strings.The conclusion attributes the result to the combined selection and verification techniques described above.
Loading 1111.7171v1…