Hamming Distance Oracles

We first present a simple dynamic programming algorithm, which proves the theorem for $x=1$. We then show how we can compute only a portion of the dynamic programming table, and then bound the time the data structure needs for answering a query.

Let $𝖣$ be a matrix of size $n\times m$ such that $𝖣[i,j]=\mathrm{𝖧𝖣}(S[i..n],T[j..m])$, i.e. the Hamming distance of the $i$-th suffix of $S$ and the $j$-th suffix of $T$. Then, the matrix $D$ satisfies the following recursion:

Notice that by Equation 1 one can compute each value $𝖣[i,j]$ in $O(1)$ time (assuming a right order of computation). Thus, filling the dynamic programming table takes $O(nm)=O(n\cdot T_{\mathrm{𝖧𝖣}}(m,1,\mathrm{\Sigma }))$ time in total²²2Notice that for every alphabet $\mathrm{\Sigma }$ satisfying $|\mathrm{\Sigma }|\ge 2$, it holds that $T_{\mathrm{𝖧𝖣}}(m,x,\mathrm{\Sigma })=\mathrm{\Omega }(m)$ as the input must be read.. Having constructed $𝖣$, we have random access to the answers of all possible queries, and the data structure can answer every query in $O(1)$ time, concluding the proof of Lemma 10 for $x=1$.

We proceed to describe our construction for any $x\ge 1$.

The data structure maintains a small portion of the table $𝖣$: For each $i\in [1..\lfloor \frac{n}{x}\rfloor ]$, the algorithm computes and stores the $i\cdot x$-th row, i.e. for each $(i,j)\in [1..\lfloor \frac{n}{x}\rfloor ]\times [m]$ the data structure computes the cell $𝖣[i\cdot x,j]$. Notice that (by Fact 9), the value of any cell $𝖣[i,j]$ is the sum of the Hamming distance $\mathrm{𝖧𝖣}(S[i..i+\mathrm{\ell }),T[j..j+\mathrm{\ell }))$ and $𝖣[i+\mathrm{\ell },j+\mathrm{\ell }]$ (if the indices of the cell are not in the table, we consider the cell value as $0$). In particular,

Therefore, by computing the rows in decreasing order (and using cells from rows already computed), the data structure is able to compute each row with a single invocation of a text-to-pattern Hamming distance algorithm with text $T$ and pattern $S[i\cdot x..(i+1)x)$. In every such invocation, the text’s size is $|T|=m$, the pattern size is $x$, and the strings are over alphabet $\mathrm{\Sigma }$. Therefore the running time per computed row is $T_{\mathrm{𝖧𝖣}}(m,x,\mathrm{\Sigma })$. Thus, the preprocessing time is $O(\frac{n}{x}\cdot T_{\mathrm{𝖧𝖣}}(m,x,\mathrm{\Sigma }))$ as required.

Let $i,j$ be an input query. Without loss of generality, we focus on the case $x\le m$, since otherwise one can answer a query in $O(m)\subseteq O(x)$ time naïvely by comparing up to $m$ pairs of characters, even without preprocessing. Let $i^{\prime }$ be the minimal integer multiple of $x$ larger or equal to $i$ and let $j^{\prime }=j+i^{\prime }-i$. The algorithm first computes $\mathrm{𝖧𝖣}(S[i..i^{\prime }),T[j..j^{\prime }))$ naïvely by comparing pairs of corresponding characters. Then the algorithm returns $\mathrm{𝖧𝖣}(S[i..i^{\prime }),T[j..j^{\prime }))+𝖣[i^{\prime },j^{\prime }]$. Since $i^{\prime }$ is an integer multiple of $x$, we have that $𝖣[i^{\prime },j^{\prime }]$ is accessible in $O(1)$ time after the preprocessing (if $(i^{\prime },j^{\prime })$ is outside the boundaries of $𝖣$, then either $i>n-x+1$ or $j>m-x+1$. In either case, the answer to the query can be naively computed in $O(x)$ time). Therefore the running time of the query is $O(i^{\prime }-i+1)=O(x)$. The correctness follows immediately from Fact 9 (see Figure 2).

$◀$

Our reduction is based on an idea attributed to Ely Porat and Piotr Indyk [8] that was later generalized by Gawrychowski and Uznanski [12]. Assume by contradiction that there exists some $\epsilon >0$ such that $p(n,m)\cdot q(n,m)=O({(nm)}^{1-\epsilon })$. Let $x=q(n,m)\cdot {(nm)}^{\epsilon /2}$ and note that $q(n,m)=\frac{x}{{(nm)}^{\epsilon /2}}$. Let $A$ and $B$ be two Boolean matrices of sizes $\frac{n}{x}\times x$ and $x\times \frac{m}{x}$, respectively. The idea is to create a string $S$ representing the rows of $A$ and a string $T$ representing the columns of $B$. We transform each row of $A$ and each column of $B$ such that the Hamming distance between the row’s string and the column’s string indicates the Boolean product of the corresponding row and column. We first show a construction using ternary alphabet, and then explain how one can convert it into a binary alphabet.

We define encoding of values into characters, which is as follows:

• $\mathrm{■}$

  each $1$ is encoded by the character ${}_{}{}^{\prime }1_{}^{\prime }$.

• $\mathrm{■}$

  each $0$ from $A$ is encoded by the character ${}_{}{}^{\prime }a_{}^{\prime }$.

• $\mathrm{■}$

  each $0$ from $B$ is encoded by the character ${}_{}{}^{\prime }b_{}^{\prime }$.

For each $i\in [\frac{n}{x}]$ the algorithm encodes the $i$th row of $A$ as $A_i$, and for each $j\in [\frac{m}{x}]$ the algorithm encodes the $j$th column of $B$ as $B_j$. Then $S$ is the concatenation of $A$’s rows (i.e. $S=A_1\cdot A_2\cdot \mathrm{\dots }{A}_{n/x}$), and $T$ is the concatenation of $B$’s columns ($T=B_1\cdot B_2\cdot \mathrm{\dots }{B}_{m/x}$). The resulted strings $S$ and $T$ have length of $n$ and $m$ (respectively), and then the algorithm creates the Hamming Distance Oracle data structure $𝒬$ of $S$ and $T$. We prove the following connection between Boolean matrix product and the Hamming distance of row strings and column strings.

${(AB)}_{ij}=1$ if and only if there exists some $k\in [x]$ such that $A[i,k]=1=B[k,j]$. That means that both $A[i,k]$ and $B[k,j]$ were encoded by the character ${}_{}{}^{\prime }1_{}^{\prime }$, and $\mathrm{𝖧𝖣}(A[i,k],B[k,j])=0$. This implies that for $A_i$ and $B_j$ there is a match in at least one index, and therefore .

For the other direction, if , then for some $k\in [x]$ there is a match in $A_i[k]=B_j[k]$. Since ${}_{}{}^{\prime }a_{}^{\prime }$ does not occur in $B_j$ and ${}_{}{}^{\prime }b_{}^{\prime }$ does not occur in $A_i$, it must be that $A_i[k]=1=B_j[k]$. Therefore, $A[i,k]=B[k,j]=1$ and thus ${(AB)}_{ij}=1$. $\mathrm{⊲}$

To prove the hardness for binary alphabet one can find a binary encoding $E:\{1,a,b\}\to {\{0,1\}}^3$ for each symbol in $\{1,a,b\}$ that preserves the mismatches: for each $c\ne d\in \{1,a,b\}$ it holds that $\mathrm{𝖧𝖣}(E(c),E(d))=2$. Then, the reduction construction is modified to check if the distance between $A_i$ and $B_j$ is strictly less than $2x$. An example for such encoding is ${}_{}{}^{\prime }011_{}^{\prime }{,}^{\prime }{101}^{\prime }{,}^{\prime }{110}^{\prime }$.

Due to Claim 13 and the discussion above, the algorithm would query the data structure for each entry of $AB$ if and fill in the matrix $AB$ accordingly.

The correctness comes directly from Claim 13. Thus, using the oracle $𝒬$, one can compute the Boolean matrix product $AB$ in $O(p(n,m)+\frac{nm}{x^2}q(n,m))$ time.

Recall that $p(n,m)\cdot q(n,m)=O({(nm)}^{1-\epsilon })$ and $q(n,m)=\frac{x}{{(nm)}^{\epsilon /2}}$. Thus, we get that

Moreover,

Thus, the time for computing the product $AB$ using the oracle $𝒬$ is $O({(\frac{nm}{x})}^{1-\epsilon /2})$, which contradicts Conjecture 11 that suggests that no algorithm can compute $AB$ in $O({(\frac{nm}{x})}^{1-{\epsilon }^{\prime }})$ time. $◀$

As a preprocessing, the data structure only builds the $\mathrm{𝖫𝖢𝖯}$ data structure of Lemma 5 on $S\cdot T$ which takes $O(n+m)$ time. On a query $\mathrm{𝖧𝖣}(S[i..i+\mathrm{\ell }),T[j..j+\mathrm{\ell }))$, the algorithm queries the $\mathrm{𝖫𝖢𝖯}$ data structure to find the first mismatch between $S[i..n]$ and $T[j..m]$. If the mismatch is after $S[i+\mathrm{\ell })$ and $T[j+\mathrm{\ell })$, the algorithm reports that the Hamming distance is $0$. Otherwise, the algorithm found the first mismatch $t\le \mathrm{\ell }$ such that $S[i+t]\ne T[j+t]$. The algorithm computes recursively $\mathrm{𝖧𝖣}(S[i+t+1..i+\mathrm{\ell }),T[j+t+1..j+\mathrm{\ell }))$ and returns the reported result with the addition of $1$ (for the mismatch $S[i+t]\ne T[j+t]$). Finally, if the depth of the recursion becomes more than $k$, the algorithm reports that there are more than $k$ mismatches, meaning $\mathrm{𝖧𝖣}(S[i..i+\mathrm{\ell }-1],T[j..j+\mathrm{\ell }-1])>k$ and halts. Since every level of the recursion performs a single $\mathrm{𝖫𝖢𝖯}$ query, the running time of the algorithm is $O(1)$ per level of the recursion, which is $O(k)$ in total. We remark that the actual implementation of the query algorithm can be done iteratively, rather than recursively, to optimize space usage and time overhead. $◀$

If one is interested in a $k$-bounded Hamming distance oracle with $o(k)$ query time, one can simply use the data structure of Theorem 7, obtaining a similar preprocessing-query time tradeoff. One can observe that the lower bound of Theorem 12 holds for $k$-bounded Hamming oracles in the regime in which the query time is $o(k)$ (i.e., the queries used in the lower bound construction are between pairs of substrings with Hamming distance at most between them). Therefore, in the regime in which the query time is $o(k)$ and the alphabet is constant, the trade-off of Theorem 7 cannot be beaten by a combinatorial algorithm, even for a $k$-bounded oracle.

For every $r\in [1..p]$, let $I_r=(r+a\mid a\in [0..n-r]\wedge amodp\in B)$ (in increasing order) and let $J_r=(r+a\mid a\in [0..m-r]\wedge amodp\in B)$ (in increasing order). Let $S_r={⨀}_{i\in I_r}S[i]$ and $T_r={⨀}_{i\in J_r}T[i]$. Notice that for every $i,\mathrm{\ell }$ there exist $r,i^{\prime }$, and $i^{\prime \prime }$ such that $S_{i,\mathrm{\ell }}=S_r[i^{\prime }..i^{\prime \prime }]$. Specifically, this equality holds for $r\in [1..p]$ such that $rmodp=imodp$, $i^{\prime }$ is the rank of the successor of $i$ in $I_r$ and $i^{\prime \prime }$ is the rank of the predecessor of $i+\mathrm{\ell }-1$ in $I_r$. Similarly, for every $j,\mathrm{\ell }$ there exist $r^{\prime },j^{\prime }$, and $j^{\prime \prime }$ such that $T_{j,\mathrm{\ell }}=T_{r^{\prime }}[j^{\prime }..j^{\prime \prime }]$. Specifically, this equality holds for $r^{\prime }\in [1..p]$ such that $r^{\prime }modp=jmodp$, $j^{\prime }$ is the rank of the successor of $j$ in $J_{r^{\prime }}$ and $j^{\prime \prime }$ is the rank of the predecessor of $j+\mathrm{\ell }-1$ in $J_{r^{\prime }}$.

As a preprocessing step, the algorithm constructs for every $r\in [1..p]$ the sequences $I_r$ and $J_r$, and constructs predecessor/successor data structures for $I_r$ and for $J_r$. The algorithm also constructs strings $S_r$ and $T_r$, and constructs an $\mathrm{𝖫𝖢𝖯}$ data structure over $\widehat{S}={⨀}_{r\in [1..p]}{S}_r\cdot T_r$. Notice that for every $r\in [1..p]$, it holds that $|S_r|\in O(n\cdot |B|/p)$ and $|T_r|\in O(m\cdot |B|/p)$. Therefore, $|\widehat{S}|\in O((n+m)|B|)$. The construction time of all above data structures is therefore $\tilde{O}((n+m)|B|)$.

When a query $i,j,\mathrm{\ell }$ is given, the algorithm finds $r,i^{\prime }$ and $i^{\prime \prime }$ such that $S_r[i^{\prime }..i^{\prime \prime }]=S_{i,\mathrm{\ell }}$ and $r^{\prime },j^{\prime }$ and $j^{\prime \prime }$ such that $T_{r^{\prime }}[j^{\prime }..j^{\prime \prime }]=T_{j,\mathrm{\ell }}$ (where finding $i^{\prime },i^{\prime \prime },j^{\prime }$ and $j^{\prime \prime }$ is done using predecessor and successor queries on $I_r$ and $J_{r^{\prime }}$). Since the positions of $S_r$ and of $T_{r^{\prime }}$ within $\widehat{S}$ are known, the indices $i^{\prime },i^{\prime \prime },j^{\prime },j^{\prime \prime }$ can be easily shifted to the corresponding occurrences of $S_{i,\mathrm{\ell }}$ and of $T_{j,\mathrm{\ell }}$ in $\widehat{S}$. As we have found a representation of $S_{i,\mathrm{\ell }}$ and of $T_{j,\mathrm{\ell }}$ as substrings of $\widehat{S}$, we can use the $\mathrm{𝖫𝖢𝖯}$ data structure of $\widehat{S}$ to check if $S_{i,\mathrm{\ell }}=T_{j,\mathrm{\ell }}$ in constant time. The time complexity of the query is dominated by the invocation of the predecessor/successor data structures to find $i^{\prime },i^{\prime \prime },j^{\prime }$, and $j^{\prime \prime }$. The running time is therefore $\tilde{O}(1)$. $◀$

We now discuss how to use Lemmas 17 and 18, to preprocess $S$, $T$, $\epsilon$ and $k$ and support the following query: Given $i,j,\mathrm{\ell }$ return an $(\epsilon ,k)$-estimate of $\mathrm{𝖧𝖣}(S[i..i+\mathrm{\ell }),T[j..j+\mathrm{\ell }))$. Let $\widehat{p}={\epsilon }^{-1}sk\log (n+m)$, the algorithm picks a random prime $p\in [\widehat{p}\mathrm{..2}\widehat{p})$. For $L=\mathrm{\Theta }({\epsilon }^{-2}\log s)$, the data structure generates $L$ independent samples $B^{(1)},B^{(2)},\mathrm{\dots }{B}^{(L)}$ with sampling rate $\beta =\frac{1}{2k}$ from $[p]$. The algorithm then applies Lemma 18 on $S$, $T$, $p$ and $B^{(t)}$ for every $t\in [L]$. The preprocessing takes $\tilde{O}({\epsilon }^{-3}(n+m))$ expected time (since $𝔼(|B^{(t)}|)=p\cdot \beta \in O({\epsilon }^{-1}s\log (n+m))$ and $L\in \tilde{O}({\epsilon }^{-2})$). At query time, the algorithm uses the preprocessing of Lemma 18 to check if $X^{(t)}=Y^{(t)}$ for every $t\in [L]$ and compute $c$ and $\tilde{d}$ accordingly as in Line 7 of Line 7. It is immediate from Lemma 17 that the output is indeed an $(\epsilon ,k)$-estimate of $\mathrm{𝖧𝖣}(S[i..i+\mathrm{\ell }),T[j..j+\mathrm{\ell }))$ with probability $1-O(1/s)$. The running time of the query is $\tilde{O}(L)=\tilde{O}({\epsilon }^{-2})$. Choosing $s$ to be a large enough constant implies a small constant error probability. In order to achieve $(\epsilon ,k)$-estimate of $\mathrm{𝖧𝖣}(S[i..i+\mathrm{\ell }),T[j..j+\mathrm{\ell }))$ with high probability, it suffices to construct $O(c\log n)$ instances of the above data structure and return the median of the answers while processing a query.

To obtain Theorem 4, we construct the above data structure for every value of $k$ which is a power of $2$ and is at most $\min \{n,m\}$. While processing a query, the algorithm obtains an $(\epsilon ,k)$-estimate for each $k$. Let ${\tilde{d}}_k$ be the estimate computed for $k$. If one of these estimates satisfies ${\tilde{d}}_k\in [(1-\epsilon )k\mathrm{..2}(1+\epsilon )k]$, the algorithm reports ${\tilde{d}}_k$ as the approximation of $d:=\mathrm{𝖧𝖣}(S[i..i+\mathrm{\ell }),T[j..j+\mathrm{\ell }))$. Since with high probability every ${\tilde{d}}_k$ is an $(\epsilon ,k)$-estimate, the reported value is indeed $(1-\epsilon )d\le \tilde{d}\le (1+\epsilon )d$. Moreover, for the (correct) value of $k$ such that $d\in [k\mathrm{..2}k]$, with high probability ${\tilde{d}}_k\in [(1-\epsilon )k\mathrm{..2}(1+\epsilon )k]$. Thus, the algorithm is correct with high probability. The construction takes⁵⁵5We note that using a slightly more complicated construction, following Chan et al. [4], one can speedup the construction time to be $\tilde{O}({\epsilon }^{-2.5}(n+m))$. However, we preferred to put a simpler version here for the reader’s ease. $\tilde{O}({\epsilon }^{-3}(n+m))$ time and the query time is $\tilde{O}({\epsilon }^{-2})$.