CS Paper Radar

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

Michael T. Goodrich, Gonzalo Navarro, Claire A. To

cs.DS ·submitted 2026-08-25 21:52 UTC · v2

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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.99
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

Bounded Weighted Edit Distance with Metric Costs

cs.DS ·2026-11-10 ·Jihan Wang
similarity 0.66
Abstract

We give a deterministic $O(n+k^2)$-time algorithm for bounded weighted edit distance when the input costs form an integer metric on the alphabet extended by a gap symbol. Here $n$ is the total input length and $k$ is the given threshold on the distance. If the distance is at most $k$, the algorithm returns it with an optimal alignment. Otherwise, it reports that the distance exceeds $k$. The running time matches the classical unit-cost bound and is independent of the alphabet size and of the largest cost. The algorithm keeps only the farthest-reaching prefix alignment for each cost and each difference between the total gap costs of the aligned prefixes. For real metrics whose nonzero costs are at least one, scaling and upward rounding give a $(1+\varepsilon)$-approximation for the bounded problem in $\widetilde{O}(n+(k/\varepsilon)^2)$ time. If insertions and deletions have integer costs, the running time improves to $\widetilde{O}(n+k^2/\varepsilon)$.

0.20

Joining Large String Collections with Jaro-Winkler Similarity

cs.DB ·2026-10-16 ·Manuel Lankes, Daniel Kocher, Daniel Schmitt, Willi Mann, Thomas Samy Dafir +3 more
top venue similarity 0.66
Abstract · Accepted for publication in Proc. ACM Manag. Data (PACMMOD / SIGMOD 2027). Please cite the official version: https://doi.org/10.1145/3856354

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.

0.43

MacCorles: Minimum Alignment Cost Computation on Run-Length Encoded Strings

cs.DS ·2026-08-14 ·Wing-Kai Hon, Dominik Köppl, Jun-Hong Wang
similarity 0.65
Abstract

We study a tie-breaking variant of the longest common subsequence problem on run-length encoded strings. Given two strings, the goal is first to maximize the number of equal aligned character pairs, as in the classical longest common subsequence problem, and then, among all such alignments, to minimize the alignment length. Equivalently, after maximizing the number of equal pairs, we minimize the number of insertions and deletions. We show that this problem admits a simple block-boundary dynamic program. If the input strings have lengths $N$ and $M$, and their run-length encodings have $n$ and $m$ runs, respectively, the algorithm runs in $O(mN+nM)$ time using $O(nm)$ space. The algorithm treats every pair of runs as a homogeneous block with an explicit transfer function and stores dynamic-programming values only on run boundaries.

0.04

Faster Approximate Text-to-Pattern Hamming Distances via Near-Optimal Sumset Estimation

cs.DS ·2026-11-03 ·Nick Fischer, Yael Kirkpatrick, Vasileios Nakos
similarity 0.62
Abstract

\emph{Text-to-Pattern Hamming Distances} is one of the most studied problems in string algorithms: given a text $T$ of length~$n$ and a pattern~$P$, the task is to compute the Hamming distance between~$P$ and every length-$|P|$ substring of~$T$. As exact algorithms have been stuck at time~$\tilde O(n^{3/2})$ for decades, a long line of work has turned to the $(1+ε)$-approximate version of the problem. Milestones include Karloff's $\tilde O(ε^{-2} n)$-time algorithm [IPL '93], followed by randomized improvements to $\tilde O(ε^{-1} n)$ by Kopelowitz and Porat [FOCS '15] and recently to $\tilde O(ε^{-0.915} n)$ by Chan, Jin, Vassilevska W., and Xu [FOCS '23]. In this work, we significantly improve this bound to $\tilde O(ε^{-2/3} n)$, using a considerably simpler algorithm. Our algorithm follows the framework of Chan, Jin, Vassilevska W., and Xu, which reduces the problem to a variant of 3SUM that we call \emph{Sumset Estimation}. We solve Sumset Estimation optimally (up to logarithmic factors) by replacing their matrix multiplication techniques with ideas from sparse recovery. Specifically, we adapt the classic Count Sketch by replacing its random signs with random complex roots of unity---a simple idea that may find further applications for other additive problems. Finally, we give evidence that our running time might in fact be optimal: we show that the $ε^{-2/3}$ dependence is \emph{best possible} for a certain natural class of algorithms, including ours and all previous algorithms.

0.50

A Strongly Subquadratic $(3+\varepsilon)$-Approximation for Weighted Edit Distance over Arbitrary Metrics

cs.DS ·2026-09-14 ·Ethan Mader, Borna Tavasoli, Jihan Wang
similarity 0.60
Abstract

We study weighted edit distance between two strings of total length $n$, where edit costs are induced by an arbitrary metric. For equal-length inputs, Kuszmaul (2019) gave an $O(n^δ)$-approximation with $\widetilde{O}(n^{2-δ})$ running time for every fixed $0 < δ< 1$. We give the first constant-factor approximation for weighted edit distance over arbitrary metrics in strongly subquadratic running time. For every $0 < \varepsilon \le 1$, our randomized algorithm runs in $\widetilde{O}(n^{7/4}/\varepsilon^8)$ time and returns a $(3+\varepsilon)$-approximation with probability at least $1-n^{-10}$. The algorithm allows unequal input lengths and places no bound on the ratio between edit costs.

0.20

An Approximation Algorithm for Non-uniform Non-contiguous Translocation Distance

cs.DS ·2026-09-21 ·Maria Constantin, Adrian Miclăuş, Alexandru Popa
similarity 0.60
Abstract

Translocations are genome rearrangement operations that exchange prefixes of two chromosomes. We study the non-uniform non-contiguous translocation distance problem, where every string produced during the computation remains available for reuse. Given an initial set of strings $A$ and a target set $B$, the objective is to produce all strings in $B$ using as few translocations as possible. We present the first polynomial-time approximation algorithm for this problem. For a single target string of length $n$, we obtain an $O(\log n)$-approximation, and we extend the result to arbitrary finite target sets with an $O(\log N)$-approximation, where $N$ is the total length of the targets not already present in the initial set. This resolves the approximability question for the non-uniform non-contiguous case left open by Constantin and Popa (TCS 2025).

0.08

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