PaperlayerView exact revision on arXiv

Source-linked AI summary

Joining Large String Collections with Jaro-Winkler Similarity

Manuel Lankes, Daniel Kocher, Daniel Schmitt, Willi Mann, Thomas Samy Dafir, Bin Shen, Yujian Xu, Nikolaus Augsten

arXiv:2610.23652v1cs.DB

TL;DR

Efficient Jaro-Winkler joins remain challenging on large string collections because verification can be slow for short strings or quadratic for long ones. The paper combines prefix-aware filtering, adaptive bitmap overlap bounds, and fast verification; it reports speedups of up to three orders of magnitude over the state of the art.

  • Problem

    Efficient Jaro-Winkler joins on large string collections remain challenging because existing verification methods can be slow for short strings or quadratic for long ones.

    Source: §1 · p. 3, §6.2 · p. 13

  • Method

    The approach groups strings by prefix, uses cost-model-adapted fixed-size bitmaps to bound overlap, and verifies candidates with JUMP.

    Source: §1 · p. 3

  • Results

    The approach outperforms the state of the art by up to three orders of magnitude across a wide range of thresholds and datasets of up to one million strings.

    Source: §1 · p. 3, §10 · p. 23

  • Takeaways & Limitations

    The approach is reported to scale to long strings while remaining fast for short strings, and DIB also applies to set similarity queries beyond strings.

    Source: §1 · p. 3, §10 · p. 23

    The bitmap cost optimization targets the distribution of pairs reaching overlap verification after size filtering.

    Source: §5.2 · p. 10

Abstract

from arXiv · show

The Jaro-Winkler measure, originally developed for U.S.\ Census record linkage, captures similarities between strings and accounts for common typographical variations. Despite its widespread use, finding all string pairs that exceed a given Jaro-Winkler threshold remains challenging as the string collection grows large. Existing algorithms for computing the Jaro-Winkler similarity between two strings are either slow for short strings or require quadratic time and fail to scale to long strings. To reduce the number of string comparisons, state-of-the-art techniques perform an index-nested-loop join on trie-based indexes; however, they have only been evaluated on small datasets and high similarity thresholds. For lower similarity thresholds that are relevant in practice, these techniques incur an excessive number of costly Jaro-Winkler computations. We present a novel approach for efficient Jaro-Winkler similarity joins on large string collections. Our solution is based on three key techniques: (1) JUMP is a fast algorithm for computing the Jaro-Winkler similarity between two strings that runs in linear time for bounded alphabets. (2) Dual-bound intersection bitmaps encode strings -- represented as character sets -- into fixed-size bitmaps, which are used to prune candidate string pairs by providing effective bounds on their character overlap; unlike prior bitmap techniques, our bitmaps are equipped with a cost model and adapt to the input data. (3) Our PUMA framework groups strings by prefix to tighten filter conditions, thereby reducing the number of similarity computations. Extensive experiments on large string collections demonstrate that our approach consistently outperforms the state of the art, achieving speedups of up to three orders of magnitude.

1 Introduction

Jaro-Winkler joins are difficult to scale, particularly because existing approaches struggle at lower thresholds and similarity computation is costly. The paper combines prefix-aware filtering, adaptive overlap bounds, and fast verification to address this challenge.

1 Introduction

  • PUMA groups strings by common prefixes to tighten filter conditions and uses traversal to avoid duplicate candidate pairs.This removes the need for an expensive final deduplication step.Source: §1 · p. 3
  • DIB encodes strings as fixed-size bitmaps, using frequent-character bits for a lower overlap bound and hashed remaining characters for an upper bound.Its cost model adapts the bitmap to the input data, and the technique also applies to set similarity queries.Source: §1 · p. 3
  • JUMP verifies candidate pairs in linear time for bounded alphabets, avoiding the quadratic window search used by most prior methods.The paper reports that it outperforms all linear competitors in practice.Source: §1 · p. 3
  • Up to three orders of magnitude speedup over the state of the art is reported across thresholds and datasets of up to one million strings.The comparison includes low similarity thresholds and large datasets.Source: §1 · p. 3

2 Preliminaries

The preliminaries define Jaro-Winkler similarity and its join objective, then derive a prefix-dependent Jaro threshold and two filters for pruning candidate pairs.

2.1 Jaro-Winkler Similarity

  • Jaro-Winkler combines Jaro similarity, based on matching characters and transpositions, with a boost for a common prefix.The standard setting limits the prefix length to four and uses a scaling factor of 0.1.Source: §2.1 · pp. 3–4

2.2 Problem Definition & Objective

  • The join returns string pairs whose Jaro-Winkler similarity meets the user-defined threshold; the stated objective is to scale efficiently to large collections and a wide threshold range.The section focuses on self-joins and discusses R-S joins separately.Source: §2.2 · p. 4

2.3 Jaro Threshold and Filters

  • For each common-prefix length, the method derives an equivalent Jaro threshold; when the Winkler threshold is at least 0.7, the derived threshold is capped at 0.7 if needed.Below a Winkler threshold of 0.7, the equivalent Jaro threshold is unchanged.Source: §2.3 · p. 4

2.4 Jaro Filters

  • The overlap filter tokenizes character occurrences and rejects pairs whose token-set intersection cannot provide enough matched characters for the Jaro threshold.The size filter bounds the maximum string-length difference using the shorter string as an upper bound on matching characters.Source: §2.4 · p. 5

3 Algorithm Outline

The algorithm is a three-stage filter-and-verify pipeline: PUMA generates pre-candidates, DIB refines them, and JUMP verifies the remaining pairs.

3 Algorithm Outline

  • PUMA groups strings to enable tighter Jaro thresholds for index-based filtering, producing pre-candidates and reducing comparisons.A traversal strategy avoids duplicate candidate pairs.Source: §3 · p. 5
  • DIB applies lower and upper bounds on character overlap to refine pre-candidates into candidates that pass the overlap filter.Source: §3 · p. 5
  • JUMP verifies candidate pairs against the Jaro-Winkler threshold in linear time for bounded alphabets.Source: §3 · p. 5

4 The Puma Framework

The PUMA framework exploits common prefixes because they affect the overlap needed to meet a Jaro-Winkler threshold. Its trie uses prefix-specific thresholds and processes each pair at its longest shared prefix.

4 The Puma Framework

  • Required overlap depends on common-prefix length and can be low: for length-eight strings at threshold 0.85, it ranges from seven characters with no shared prefix to five with a four-character prefix.The latter corresponds to a Jaccard threshold as low as 0.46.Source: §4 · pp. 5–6
  • PUMA groups strings by common-prefix length so each group can use its corresponding Jaro threshold to tighten the overlap filter.The required overlap is derived from that threshold.Source: §4 · p. 6
  • The prefix trie stores strings sharing each prefix at its node, and each node produces a partial self-join using the Jaro threshold for its depth.The overall result is the union of these partial joins.Source: §4 · p. 6
  • Pairs are processed at the deepest node containing both strings, corresponding to their longest common prefix, rather than repeatedly at shorter-prefix nodes.If the next character is shared, processing is pushed down; failure at the deeper node implies failure at the stricter threshold above.Source: §4 · p. 6

5 Fast and Robust Overlap Filtering

Large-universe exact bitmaps and approximate bitmaps with skew and false-positive tradeoffs make overlap filtering challenging. Dual-bound intersection bitmaps (Dibs) combine exact and hashed encodings, while a cost model selects a layout for the input data.

5 Fast and Robust Overlap Filtering

  • Prior approximate bitmaps assume uniform token frequencies, and their filtering effectiveness can degrade as the token universe grows.Larger bitmaps also increase memory footprint and can cause more memory accesses and cache misses.Source: §5 · p. 7

5.1 Dual-Bound Intersection Bitmaps

  • Dibs encode frequent tokens exactly and remaining tokens with hashing, yielding overlap bounds and an exact fallback when the bounds are inconclusive.The exact part gives a lower bound; the combined exact and hashed parts give an upper bound.Source: §5.1 · p. 8

5.2 Optimal Bitmap Layout

  • A cost model selects bitmap sizes and collision policy by balancing bound checks against fallback costs.It estimates upper-bound pruning and inconclusive-pair probabilities; bitmap-check costs depend on the underlying architecture.Source: §5.2 · pp. 9–10
  • For DBLP Titles at τW=0.85, the lower bound is particularly effective, favoring higher n than k.Expected cost first drops sharply as bitmap size increases, then rises as base cost grows without meaningfully reducing fallback probability.Source: §5.2 · p. 12

6 Practical Linear-Time Jaro-Winkler Similarity

The section defines Jaro mappings to establish a unique Jaro similarity, then presents Jump, a merge-based algorithm for computing Jaro-Winkler similarity in linear time for bounded alphabets.

6.1 Declarative Jaro Mapping

  • A Jaro mapping is a maximum-cardinality valid character match that minimizes its matching cost, and all such mappings yield identical matched substrings and a unique Jaro similarity.The original technique computes a Jaro mapping.Source: §6.1 · p. 12

6.2 Jump: Jaro Using Merge Pass

  • Jump computes Jaro-Winkler similarity in linear time for bounded alphabets, replacing the quadratic character-window comparisons of the original greedy approach.It sorts character-position pairs and uses merge-like matching and transposition phases; the preprocessing cost is O(min {n + |Σ|, n log n}).Source: §6.2 · pp. 13–14
  • Jump sorts character-position pairs and processes them in merge-like matching and transposition phases to compute the similarity.For joins, preprocessing each string once reduces subsequent similarity computations to O(n) time and space; positional filters can terminate matching or transposition work when the threshold cannot be met.Source: §6.2 · pp. 13–15

7 Extension to 𝑹-𝑺Joins

The section adapts the join components to two distinct collections and describes preprocessing that can be reused across joins involving the same collection.

7 Extension to 𝑹-𝑺Joins

  • The extension covers joins between distinct collections and reuse of a preprocessed R relation across multiple joins.Source: §7 · p. 15

7.1 Adapting the Components to 𝑹-𝑺Joins

  • For R-S joins, PUMA traverses the two prefix tries in parallel and performs partial Jaro joins for matching-prefix nodes before verifying pre-candidates.Pre-candidate generation and size filtering are adapted to the two-collection setting; unmatched trie nodes are skipped.Source: §7.1 · pp. 15–16

7.2 Preprocessing Reuse Across Joins

  • Preprocessing on R can be reused across joins: its PUMA trie, Jump data, and cost-model statistics are computed once.For each new S, R and S statistics are merged to choose bitmap layouts; some pre-candidate indexes are also reusable across thresholds.Source: §7.2 · p. 16

8 Experiments

The experiments evaluate PUMA, Dib, and Jump separately and in end-to-end joins across four string collections and multiple similarity thresholds. The proposed join is fastest overall in the reported comparisons, while the relative benefit of its components varies with workload and threshold.

8 Experiments

  • The evaluation uses four string collections with average lengths below 100 characters and samples of 10^6 strings for most experiments.The datasets cover company names, DBLP titles and authors, and job titles; preprocessing removes non-alphanumeric characters and exact duplicates.Source: §8 · pp. 17–18, Figure 8 · p. 17, Table 1 · p. 18

8.1 Evaluation of Puma

  • PUMA makes sfDibJump+, PalDibJump+, and PreDibJump+ 1.5×, 13.0×, and 2.8× faster than their non-PUMA counterparts on average.Their pre-candidate counts fall by 1.5×, 20×, and 2.9×, respectively; at τW=0.95 on DBLP Authors, however, PUMA makes PalDibJump 20% slower.Source: Figure 9 · p. 18, §8.1 · p. 18

8.2 Evaluation of Dibs

  • Across datasets and thresholds, sfDib+ is 71% faster than sfSand+, with near-identical runtimes at thresholds of at least 0.92.At lower thresholds, Dib's lower bound handles 22% of generated pre-candidates on DBLP Titles, while its fallback probability is 0.3% versus 28% on Job Titles and 0.5% versus 18% on DBLP Authors.Source: Figure 10 · p. 19, §8.2 · p. 19
  • On average across thresholds and string lengths, Dib is 1.7×, 9.0×, 9.6×, and 2.3× faster than Fallback, Merge, Roar, and Sib, respectively.Dib correctly decides the overlap result for 98.7% of pairs and uses slower exact overlap computation for the remaining 1.3%.Source: Figure 11 · p. 19, §8.2 · pp. 19–20

8.3 Evaluation of Jaro-Winkler Verification

  • DibJump outperforms non-filtered verification by 8×, 10.7×, 55.9×, and 203× over Jump, Rfuzz, BasakList, and Quad, respectively.Only 2.7% of verifications require Jump after Dib filtering; Jump and Rfuzz perform similarly on strings up to 64 characters, while Jump is 3.2× faster on longer strings.Source: Figure 12 · p. 20, §8.3 · p. 20

8.4 Evaluation of Jaro-Winkler Similarity Join

  • On average across all datasets and thresholds, sfDibJump+ is fastest, beating PreDibJump+, PalDibJump+, Dressler, Keil, and sfRfuzz by 1.7×, 1.9×, 612×, 260×, and 16×, respectively.Dressler and Keil were tested on 10^5-string samples; Fig. 13 compares runtime across datasets and thresholds.Source: §8.4 · p. 20, Figure 13 · p. 21
  • Across all datasets, sfDibJump+ is 2.7× faster than PreDibJump+ and 1.6× faster than PalDibJump+ on average, but PalDibJump+ is 2.5× faster at thresholds above 0.9.Pre and Pal generate fewer pre-candidates than sf but incur more index reads; Jump and Rfuzz perform similarly overall, with Jump 15% faster on DBLP Titles and 13% slower on Job Titles.Source: Figure 14 · p. 21, §8.4 · pp. 21–22

9 Related Work

Related work covers trie-based Jaro-Winkler joins, string-verification algorithms, and set-intersection methods. The paper distinguishes its approach by combining scalable verification with data-adaptive overlap filtering and prefix-based grouping.

Jaro-Winkler Similarity Joins

  • Trie-based Jaro-Winkler joins have shown poor performance at thresholds ≤0.85 or were evaluated only at high thresholds, small query sets, or large target sets [19].The paper reports poor performance for similarly sized query and target sets in its experiments.Source: §9 · p. 22

Jaro-Winkler Verification

  • Jump avoids per-character position lists and runs in O(min{n + |Σ|, nlogn}) time under the stated alphabet condition, outperforming Basak et al. by 6.9× on average.Basak et al. use character-position lists and have an optimized implementation requiring O(|Σ| · n) space.Source: §9 · p. 22

Set Similarity Joins

  • Dibs add an exact part that supplies a lower overlap bound to the hashed bitmap's upper bound, and the experiments report that Dibs outperform Sandes et al..Dibs are described as adaptable to input data; known set-similarity join algorithms are stated to be orthogonal and integrable into PUMA.Source: §9 · p. 23

Efficient Overlap Computation

  • Set-intersection alternatives include merge-based scanning, SIB trees, and BigSet; the paper excludes graph-specific RCode and SIMD-powered methods from evaluation for stated scope or comparison reasons.Merge scanning takes O(|r| + |s|) time; BigSet's reported speedup on small sets is limited to 2× over merge-based methods.Source: §9 · p. 23

10 Conclusion

The paper concludes that its PUMA, Dib, and Jump components form a scalable approach to Jaro-Winkler similarity joins. Experiments report performance gains of up to three orders of magnitude over the state of the art.

10 Conclusion

  • The approach combines PUMA prefix grouping, data-adaptive dual-bound intersection bitmaps, and Jump verification, with experiments showing up to three orders of magnitude improvement over the state of the art.PUMA tightens filter conditions, Dibs encode strings into fixed-size exact and hashed bitmap parts, and Jump runs in linear time for bounded alphabet sizes.Source: §10 · p. 23

A Quadratic-Time Jaro-Winkler Verification

The appendix presents a greedy Jaro-similarity verification procedure. It records matched character positions, forms matched subsequences in string order, and outputs a Jaro similarity score.

A Quadratic-Time Jaro-Winkler Verification

  • During greedy matching, it takes the first qualifying character match and records the matched indices.The original verification scans the two strings greedily for identical characters satisfying the window constraint.Source: A Quadratic-Time Jaro-Winkler… · p. 27
  • The procedure takes strings r and s and outputs the Jaro similarity score SJ(r,s).It maintains sets of matched indices for each string during matching.Source: A Quadratic-Time Jaro-Winkler… · p. 27
  • After matching, it forms each matched substring from the recorded indices sorted by position in that string.Source: A Quadratic-Time Jaro-Winkler… · p. 27

B Proofs

The proofs establish correctness properties for the greedy Jaro-mapping algorithms, uniqueness of the mapping's index sets, and sound overlap bounds for dual-bound intersection bitmaps.

B Proofs

  • Two minimum-cost Jaro mappings must have the same matched row and column index sets.The proof uses an alternating path in the symmetric difference of the mappings to derive a contradiction if their index sets differ.Source: B Proofs · p. 29
  • The greedy algorithms produce valid, maximal matchings, and the original greedy algorithm also produces a minimum-cost mapping.The original algorithm's validity uses window size ⌊max{|r|,|s|}/2⌋−1.Source: B Proofs · pp. 27–29
  • The proof partitions tokens into exact and hashed subsets: exact bits yield a lower overlap bound, while hashed-bit collisions are accounted for in an upper bound.Together, these establish the lower and upper bounds on |r ∩ s|.Source: B Proofs · p. 29

C Further Experimental Results

The further experiments compare overlap-verification and Jaro-Winkler verification runtimes across algorithms and thresholds; the supplied text does not report their outcomes.

C Further Experimental Results

  • Figure 15 compares runtime for five overlap-verification algorithms across set sizes on the length-partitioned dataset at τW values 0.85, 0.9, and 0.95.The comparison covers Dib, Fallback, Merge, Sib, and Roar.Source: C Further Experimental Results · p. 30
  • Both figures report runtime comparisons over 107 verifications at three Jaro-Winkler thresholds.Figure 15 varies set size; Figure 16 reports average verification time.Source: C Further Experimental Results · p. 30
  • Figure 16 compares average runtime for five Jaro-Winkler verification algorithms at τW values 0.85, 0.9, and 0.95.The comparison covers Jump, Quad, Rfuzz, BasakList, and DibJump.Source: C Further Experimental Results · p. 30
Loading 2610.23652v1…