Source-linked AI summary
Improved Low-Overhead Communication-Efficient String Reconciliation and Edit Distance
Michael T. Goodrich, Gonzalo Navarro, Claire A. To
TL;DR
The paper studies how parties can reconcile long, similar strings without knowing where their differences are, while keeping communication and local computation low. It introduces a randomized IBLT-chunking approach for string reconciliation. The method exchanges O(k log^3 n) bits with high probability, with time overhead stated as O(n log k) in the abstract.
Problem
The problem is to reconcile distributed strings whose differences are small but unknown, avoiding whole-string transmission while limiting communication and computational overhead.
Method
The paper uses an IBLT-based algorithm combined with recursive chunking and randomized perfect hashing to reconcile the strings.
Results
O(k log^3 n) bits of communication are sufficient with high probability for strings of length Θ(n).
Takeaways & Limitations
The approach improves the authors’ earlier IBLT-based result while targeting communication proportional to edit distance.
Takeaways & Limitations
The analysis assumes high-probability randomized guarantees and, in parts of the algorithm, an a-priori upper bound on edit distance.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper addresses reconciling similar strings when the parties know differences are small but not their locations, targeting low communication and computational overhead. It presents a randomized IBLT-based algorithm with communication proportional to edit distance.
- 1 Introduction: Distributed string reconciliation supports database consistency, file synchronization, and DNA-sequence exchange without retransmitting entire strings.The motivating setting involves parties holding similar strings while seeking to minimize communication and computation.
- 1 Introduction: The central challenge is finding and reconciling unknown differences using communication that depends only on their amount.The parties lack shared strings or edit information but know their strings are similar.
- 1 Introduction: The problem seeks distributed algorithms with linear computational overhead and small communication complexity for computing edit distance.Communication is measured as bits exchanged when neither party initially knows the other’s string.
- 1 Introduction: The algorithm achieves O(k log^3 n) bits of communication and O(n log k) time overhead with high probability.Here k is the edit distance, and the success probability is over 1 − 1/n^c for any constant c.
- 1 Introduction: The method uses the invertible Bloom lookup table data structure in a non-trivial way.The paper presents this as an improvement over the authors’ earlier IBLT-based technique.
2 Related Work
Prior distributed edit-distance protocols achieve communication efficiency or improved computational overhead, but the paper characterizes existing methods as lacking the combination of simplicity, communication efficiency, and low overhead. Specialized reconciliation methods can also incur exponential computational burden.
- 2 Related Work: Existing general methods do not, according to the authors, combine simplicity, communication efficiency, and low computational overhead.The paper defines computational overhead as local RAM operations excluding time spent transmitting bits.
- 2 Related Work: Orlitsky’s O(k log n)-communication method requires n^O(k) computational overhead, which is exponential in k.Subsequent work reduces overhead, but the paper describes the best methods as requiring O(n polylog(n)) overhead and remaining complicated.
- 2 Related Work: A protocol by Chakraborty, Goldenberg, and Koucký uses O(k^2 log n) bits and O(n polylog(n)) overhead after embedding strings into Hamming space.Its communication operates in the embedded Hamming space using random walks.
- 2 Related Work: Specialized reconciliation based on masks, shingling, and Eulerian paths has communication linear in edit distance but may enumerate exponentially many paths.The resulting number of paths can make the reconstruction computationally burdensome.
3 Invertible Bloom Lookup Table (IBLT)
IBLTs encode sets with XOR-based summaries that can be subtracted to expose their symmetric difference. When the resulting table is sparse enough, peeling decodes differing elements with high probability and linear-time processing.
- IBLT representation: IBLTs are probabilistic data structures that support set reconciliation through XOR-based operations.They encode elements into hashed cells and support insertion and deletion using XOR.
- IBLT subtraction: Alice and Bob subtract their tables to obtain an IBLT representing the symmetric difference between their sets.Both parties build same-sized tables with identical hash functions before combining them by XOR.
- Peeling decode: Decoding is a destructive O(m)-time peeling procedure that recovers all keys or reports failure when the table is too full.Pure entries are identified, extracted, deleted, and propagated through their hashed cells.
- Purity test: 2^-b is the false-positive probability for a cell containing at least two keys under the purity test.The bound follows from the b-bit random checksum hash.
- Purity test: m2^-b bounds the probability that any of m cells produces a false positive.This union-bound error estimate controls checksum-related decoding errors.
- Decoding guarantee: With m = cd log n cells and λ = (c/2) log n hash functions, an IBLT holding at most d elements decodes with probability at least 1 −1/n^(c/2−1).The peeling guarantee applies for c ≥4.
4 Our Algorithm
The algorithm hierarchically chunks strings using locally consistent parsing, names chunks across logarithmically many levels, and reconciles the resulting rule sets with IBLTs. This limits edit propagation while achieving low communication and near-linear computational overhead.
- Locally consistent parsing: Locally consistent parsing divides a string into contiguous chunks at local minima of a random symbol permutation.Runs are collapsed before chunking, and every chunk has length at least 2.
- Locally consistent parsing: With high probability, the longest chunk has length O(log |X′|).A union-bound analysis controls distances between local minima.
- Hierarchical representation: Repeated LCP rounds replace chunks by names, producing sequences X0, X1, …, Xr until the final sequence has length 1.Each level records name-to-chunk mappings in sets Ai and uses fresh parsing and naming functions.
- Hierarchical representation: The total representation has O(n) size and at most log2 n levels, enabling linear-time reconstruction from the recorded mappings and hash functions.Reconstruction proceeds by expanding named chunks from the root sequence back to the original string.
- Edit sensitivity: A single edit alters at most 2 log2 n elements in the corresponding rule sets.An edit propagates to no more than two altered chunks at each level.
- Communication and computation: O(k log3 n) bits suffice for reconciliation with high probability.The bound combines IBLT communication across levels with the transmission of explicit chunks.
- Communication and computation: Theorem 2 gives O(n) time for determining the other string with probability at least 1 −1/η, for n < η ≤n^c.The result assumes strings of length Θ(n), alphabet size O(n), and an a-priori upper bound k on edit distance.
- Edit-distance computation: O(n + k2) additional time computes edit distance after both parties obtain both strings, while unknown k increases overhead to O(n log k).The unknown-bound version applies exponentially increasing guesses for k.
5 Conclusions
The paper introduces an IBLT-based reconciliation algorithm that exchanges compact representations of strings, while randomized grammars offer additional compression for repetitive data.
- O(k log^3 n) bits are exchanged with high probability for reconciling two strings of size Θ(n).The method improves the authors’ recent IBLT-based result.
- The technique generates a randomized grammar and exchanges grammars whose differences remain localized under edits.Each edit alters only O(log n) nonterminals for the specified grammar construction.
- O(γ log(n/γ)) grammar size supports reconciliation of highly repetitive texts without time or space proportional to n.A more complex grammar instead achieves O(δ log(n/δ)), where δ ≤ γ.
A Maximum Number of Affected Chunks
The analysis proves that a single edit affects at most two consecutive chunks after one LCP transformation, and that this bound persists inductively across subsequent layers.
- Base case: A single insertion, deletion, or substitution in X0 induces at most 2 consecutive changes in X1.The proof analyzes edits through local sign sequences and chunk boundaries.
- No-run case: Local minima correspond to -+ patterns in the sign sequence, so edit effects can be bounded by counting changed chunk boundaries.Insertions, deletions, and substitutions alter or remove at most one relevant -+ pattern in the no-run case.
- Run case: Edits within runs either change run symbols or fuse adjacent runs, altering or removing chunk boundaries rather than causing broad disruption.The run representation maps equal-symbol runs to a common value.
- Inductive step: At most 2 consecutive changes in Xi imply at most 2 consecutive changes in Xi+1, preserving the bound by induction.The inductive step covers windows modified by deletions, substitutions, and one or two insertions.
- Locality bound: At most 3 signs are added within the affected region, and a five-sign extended window contains at most 2 -+ endpoints.Signs outside this window remain unchanged, preventing additional chunk boundaries from being created or displaced.