CS Paper Radar

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

cs.DB ·submitted 2026-10-16 15:49 UTC · v1
top venue

Abstract

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.

Comment
Accepted for publication in Proc. ACM Manag. Data (PACMMOD / SIGMOD 2027). Please cite the official version: https://doi.org/10.1145/3856354
DOI
10.1145/3856354

Closest papers

Nearest neighbours by meaning across the whole index.

Teach Your DBMS to LIKE Strings: Fast and General Pattern Matching for Wildcard Joins and Filters

cs.DB ·2026-08-24 ·Lam-Duy Nguyen, Pascal Ginter, Duc-Tam Nguyen, Thomas Neumann, Viktor Leis
benchmark similarity 0.67
Abstract · The invariant in this manuscript is wrong. Also, the author set is changed

Nowadays, modern applications do more than just store text -- they need to derive meaningful insights from it. To do that, they usually rely on wildcard queries with LIKE predicate to extract patterns. However, modern database management systems (DBMSs) handle these wildcard operations poorly, resorting to nested loops for joins and expensive interpreted evaluation for filters. To address the former, we propose a new join algorithm based on the Aho-Corasick algorithm, which significantly reduces the time complexity. For wildcard filtering, we leverage the code-generation infrastructure to improve performance: we generate specialized code for the LIKE predicate, eliminating the overhead of interpreting the pattern per tuple. Our experimental results show that the new wildcard join algorithm significantly outperforms both baseline DuckDB and Umbra, achieving speedups of up to 30.6x and 114.75x, respectively. The new wildcard filter approach likewise outperforms both baselines, achieving a speedup of 13.3x in a filter-focused stress benchmark. We believe these two techniques will play key roles for high-performance text analytics in modern query engines.

0.24

Improved Low-Overhead Communication-Efficient String Reconciliation and Edit Distance

cs.DS ·2026-08-25 ·Michael T. Goodrich, Gonzalo Navarro, Claire A. To
similarity 0.66
Abstract

Suppose two parties, Alice and Bob, hold long character strings, $X$ and $Y$, respectively, and they are interested in determining how similar $X$ and $Y$ are. {Moreover, they want to exchange the strings with cost proportional to their degree of dissimilarity.} Such problems arise, for example, in database and file system synchronization operations, as well as in DNA sequence comparisons. Since the strings are long, we are interested in methods that are communication-efficient and have low overhead in terms of the computations that Alice and Bob must perform, when the strings are similar enough. In this paper, we provide a simple low-overhead communication-efficient algorithms for such string reconciliation and edit distance problems, determining the edit distance $k$ between $X$ and $Y$ using only $O(k\log^3 n)$ bits of communication and $O(n\log k)$ time overhead, with high probability.

0.28

Simple Low-Overhead Communication-Efficient String Reconciliation and Edit Distance

cs.DS ·2026-08-19 ·Michael T. Goodrich, Gonzalo Navarro, Claire A. To
theory similarity 0.65
Abstract · Extended version of SPIRE'26 paper

Suppose two parties, Alice and Bob, hold long character strings, $X$ and $Y$, respectively, and they are interested in determining how similar $X$ and $Y$ are. {Moreover, they want to exchange the strings with cost proportional to their degree of dissimilarity.} Such problems arise, for example, in database and file system synchronization operations, as well as in DNA sequence comparisons. Since the strings are long, we are interested in methods that are communication-efficient and have low overhead in terms of the computations that Alice and Bob must perform, when the strings are similar enough. In this paper, we provide simple low-overhead communication-efficient algorithms for such string reconciliation and edit distance problems. In the general case, %where the only assumption we make is that we have an upper bound, $k$, on the edit distance between $X$ and $Y$, we show how to determine the edit distance $k$ between $X$ and~$Y$ using only $O(k^2\log n)$ bits of communication and optimal $O(n)$ time overhead, with high probability. For specialized cases, such as typical English text or DNA sequences, where we can make additional well-justified assumptions about the distribution of the input strings, we show how to achieve possibly better bounds, such as $O(k\log^5 n)$ bits of communication.

0.29

Real-Time String Indexing in Optimal Time

cs.DS ·2026-11-10 ·Gregory Kucherov, Yakov Nekrich
similarity 0.61
Abstract · 30 pages, 7 figures

In this paper we describe the first fully real-time indexing solution for pattern matching over an arbitrary integer alphabet. Our data structure spends $O(1)$ worst-case time w.h.p. for processing each new letter appended to $T$ and worst-case $O(|P|+occ)$ time for reporting all occurrences of $P$, where $T$ and $P$ are strings over an integer alphabet. The main idea of our solution is a novel representation of the suffix tree, the path-decomposed suffix tree, which does not store the full topology of the suffix tree but instead decomposes it into paths, each stored in a dictionary that encodes parent--child relationships indirectly.

0.39

ZigZag Trie: A Novel Index for Contextual Queries

cs.DS cs.DB ·2026-09-17 ·Ling Li, Daniel Gibney, Sharma V. Thankachan, Rahul Shah, Grigorios Loukides +1 more
similarity 0.61
Abstract · 29 pages

There is increasing interest in queries about the context of a string $P$ in a longer text $T$, i.e., the set of all string pairs $(L,R)$, with $|L|=|R|=q$, for a given $q$, such that the string $LPR$ occurs in $T$. Such contextual queries are important in several domains but are challenging to answer efficiently. This is because the length of $T$ in applications is massive and existing indexes do not directly encode the context of a given $P$, which is key for answering retrieval queries efficiently. Our work introduces the ZigZag Trie (ZZT), a new full-text index to specifically address these challenges. This index reorganizes the text so that, for any $P$, all possible strings $L$ and $R$ growing symmetrically around $P$ are grouped into a common subtree of the index, allowing their efficient retrieval. We show how to construct the ZZT of $T$, which has size $\mathcal{O}(n)$ where $n=|T|$, in $\mathcal{O}(n\log n)$ time and $\mathcal{O}(n)$ space. On top of ZZT, we design specialized indexes that, for a query pattern $P$, answer four new types of contextual queries: (I) finding the longest string $LPR$ that occurs at least $τ$ times in $T$, for a fixed $τ$; (II) finding the longest string $LPR$ that occurs in at least $τ$ texts of a text collection, for a fixed $τ$; (III) reporting the total number of distinct contexts of $P$ in $T$; and (IV) retrieving, for a given $q$, the $k$ pairs $(L,R)$ of $P$ with the highest scores according to a given scoring function. Our indexes answer queries of type I, II, and III in optimal time, and of type IV in near-optimal time. Moreover, their size, construction space, and construction time are linear or near-linear in $n$, given ZZT. Using real billion-letter datasets, we show that our indexes answer queries orders of magnitude faster than baselines and perform similarly or better in index size and construction space and time.

0.33

Practical Threshold-based Tree Edit Distance Lower-Bounds

cs.DB ·2026-09-02 ·Lukáš Moravec, Radim Bača
similarity 0.60
Abstract · Full version with 15 pages

Threshold-based similarity search over tree-structured data using tree edit distance (TED) is computationally intensive. Given a query tree and a database of trees, the goal is to retrieve all trees within a predefined TED threshold $τ$. Because exact TED computation is expensive, practical methods employ lower-bounds to prune dissimilar candidates before verification. Existing lower-bounds exhibit a fundamental trade-off: inexpensive statistical and structural bounds provide limited pruning power, whereas the more precise traversal-based string edit distance (SED) bound is expensive to compute using standard quadratic dynamic programming. Moreover, previous comparative studies do not cover recent structural filters or threshold-aware SED implementations, leaving their practical trade-offs unclear. In this article, we first provide a comprehensive experimental comparison of state-of-the-art TED lower-bounds in terms of pruning precision and computational cost. We then accelerate the SED lower-bound using Ukkonen's bounded string edit distance algorithm, substantially reducing its runtime without affecting its pruning power. Finally, we introduce the SED-struct threshold filter, which strengthens SED with axes-aware constraints capturing structural relationships among tree nodes. Experiments on synthetic and real-world datasets show that SED-struct consistently achieves the highest filtering precision while retaining practical filtering costs. The results suggest that SED-struct is particularly beneficial for heterogeneous tree collections in which the standard SED lower-bound achieves relatively low precision.

0.24

Efficient discovery of unique column combinations on disk-resident data with limited memory

cs.DB ·2026-09-01 ·Xiaolong Wan, Xixian Han
theory similarity 0.60
Abstract

The discovery of unique column combinations (UCCs) is a core task in data profiling, describing the key constraints of a table. The existing algorithms cannot deal with large-scale disk-resident data well due to high memory consumption and computational cost. In this paper, a novel DUD algorithm is developed to efficiently discover UCCs on disk-resident data with limited memory, which is inspired by the relationship between UCC discovery and transversal hypergraph. Rather than complete difference set generation of quadratic complexity, DUD only generates partial difference sets for hypergraph construction, followed by minimal hitting set enumeration to generate candidates and a validation process. DUD devises a strategy to generate full useful difference sets by pairwise comparisons of tuples having the same values with respect to some selected attributes. A novel theorem is developed and proved in this paper to report the candidates including the selected attributes as true UCCs directly without validation, which reduces the number of candidates to be validated significantly. A hash-based batch validation strategy is devised to validate a set of candidates on the relation instance, which only needs to maintain a small number of tuples in memory at a time. The extensive experimental results, conducted on synthetic and real-life data sets, show that DUD can discover UCCs on disk-resident data with high efficiency and low memory consumption.

0.25

Fast Label-Filtering Approximate Nearest Neighbor Search via Progressive Label Set Stratification

cs.DB ·2026-09-14 ·Ziqi Wang, Jingzhe Zhang, Shuo Shen, Wei Hu
top venuebenchmark similarity 0.59
Abstract · Accepted in the ACM SIGMOD/PODS International Conference on Management of Data (SIGMOD 2027)

Approximate nearest neighbor search (ANNS) retrieves the most similar vectors to a query vector in high-dimensional space. Label-filtering ANNS (LFANNS) extends ANNS with a label filter that the labels of base vectors must satisfy a set relation (e.g., equality, containment, or overlap) with the query labels. Existing LFANNS indices suffer from inconsistent performance across different filter types and degraded scalability under varying label scale and distribution. In this paper, we define label-stratified similarity graph (LSSG), where edges connect neighboring vectors whose label sets fall within stratified similarity thresholds. To implement LSSG efficiently, we design an incremental insertion algorithm to prune redundant edges in both vector and label spaces, and leverage a MinHash structure to ensure scalability for large-scale labels. We analyze stepwise probabilities under explicit label models and explain why stricter label tiers reduce ineffective in-filtering expansions. Benchmark experiments show that LSSG achieves ideal optimality for equality queries, and 1.06x-92.9x and 1.08x-84.1x faster than the best competing index for containment and overlap, respectively, in query speed with identical accuracy and 0.35x index size.

0.45