String Problems in the Congested Clique Model

The first algorithm is for the string sorting problem [7, 25, 8]. This is a special case of the large objects sorting problem, where the order defined on the objects is the lexicographical order. We introduce an $O(1)$ rounds algorithm for this specific order, even if there are strings of length $\omega (n)$.

The second algorithm we present is an $O(1)$ rounds algorithm for pattern matching, which uses the string sorting algorithm. In the pattern matching problem the input is two strings, a pattern $P$ and a text $T$, and the goal is to find all the occurrences of $P$ in $T$. Algorithms for this problem were designed since the 1970’s [22, 29, 27, 40, 9]. In the very related model of Massively Parallel Computing (MPC) (see discussion below), Hajiaghayi et al. [21] introduce a pattern matching algorithm that is based on FFT convolutions. Their algorithm can be adjusted to an $O(1)$ rounds algorithm in the Congested Clique model. However, our algorithm has the advantage of using only combinatorial operations.

The last algorithm we present is an algorithm that constructs the suffix array [33, 37] ($\mathrm{𝖲𝖠}$) of a given string, together with the corresponding longest common prefix ($\mathrm{𝖫𝖢𝖯}$) array [28, 33]. The suffix array of a string $S$, denoted by ${\mathrm{𝖲𝖠}}_S$, is a sorted array of all of the suffixes of $S$. The ${\mathrm{𝖫𝖢𝖯}}_S$ array stores for every two lexicographic successive suffixes the length of their longest common prefix. It was proved [33, 28] that the combination of ${\mathrm{𝖲𝖠}}_S$ with ${\mathrm{𝖫𝖢𝖯}}_S$ is a powerful tool, that can simulate a bottom-up suffix tree traversal and is useful for solving problems like finding the longest common substring of two strings. Our algorithm takes $O(\log \log n)$ rounds.

Most of the problems considered so far in the Congested Clique model are graph problems. For such problems where the input is a graph, it is very natural to consider partitioning of the input among $n$ nodes. Each node in the network receives all the information on the neighborhood of one vertex of the input graph. However, when the input is a set of objects or strings, like in our problems, it is less clear how the input is spread among the $n$ nodes of the Congested Clique network. We tried to minimize our assumption on the input to get as general algorithms as possible. Inspired by the standard RAM model, we assume that the input of any problem can be considered as a long array that contains the input (just like the internal memory of the computer). In the Congested Clique model with $n$ nodes, we assume that the same input is now distributed among the local memories of the nodes (see Figure 1 for the case where the input objects are strings). So, to get as an input a sequence of objects with a total size of $O(n^2)$ words, we consider their representation in a long array, one after the other, and then partition this array into $n$ pieces, each of length $O(n)$. The assumption that the input of every node is of length $O(n)$, is consistent with previous problems considered in the Congested Clique model [3, 31]. A useful assumption we assume for the sake of simplicity is that when the size of every object is bounded by $O(n)$ words, any object is stored only in one node. This assumption can be guaranteed within an overhead of $O(1)$ rounds.

The Massively Parallel Computing (MPC) model [5, 2] is a very popular model that is useful for the analyzing of the more practical model of MapReduce [15], from a theoretical point of view. In this model, a problem with input of size $O(N)$ words, is solved by $M$ machines, each with memory of size $S$ words such that $M\cdot S=\mathrm{\Theta }(N)$. The MPC model is synchronous, and in every round each machine sends and receives information, such that the data received by each machine fits its memory size. We point out that, as described by Behnezhad et al. [6, Theorem 3.1], every Congested Clique algorithm with $\mathrm{\Theta }(n^2)$ size input, that uses $O(n)$ space in every node, can be simulated in the MPC model, with $N=n^2$ and $S=\mathrm{\Theta }(M)=\mathrm{\Theta }(\sqrt{N})$. Moreover, it is straightforward that every MPC algorithm that works with $S=\mathrm{\Theta }(M)$ in $r$ rounds, can be simulated in an MPC instance with $S=\omega (M)$ (but still $M\cdot S=\mathrm{\Theta }(N)$) in $r$ rounds since every machine can simulate several machines of the original algorithm. As a result, most of the algorithms we introduce in the Congested Clique model implies also algorithms with the same round complexity in the MPC model for $S=\mathrm{\Omega }(M)$. The only exception is the sorting algorithm for the case of $\epsilon =0$, which uses $\omega (n)$ memory in each machine (see Appendix B). We note that the regime of $S=\mathrm{\Omega }(M)$ is the most common regime for algorithms in the MPC model, see for example [21, 18, 34].

A string $S=S[1]S[2]\mathrm{\dots }S[n]$ over an alphabet $\mathrm{\Sigma }$ is a sequence of characters from $\mathrm{\Sigma }$. In this paper we assume $|\mathrm{\Sigma }|=[1..\mathrm{𝗉𝗈𝗅𝗒}(n)]$ and therefore each character takes $O(\log n)$ bits. The length of $S$ is denoted by $|S|=n$. For the string $S[i..j]=S[i]S[i+1]\mathrm{\dots }S[j]$ is called a substring of $S$. if $i=1$ then $S[i..j]$ is called a prefix of $S$ and if $j=n$ then $S[i..j]$ is a suffix of $S$ and is also denoted as $S[i..]$. The following lemma from [11] is useful for our pattern matching algorithm in Section 4.

Here is the definition of the longest common prefix of two strings. It is useful for the definition of the lexicographical order and also for the LCP array.

We provide here the formal definition of lexicographic order between strings.

In the Congested Clique model, a routing problem involves delivering messages from a set of source nodes to a set of destination nodes, where each node may need to send and receive multiple messages. A well-known result by Lenzen [31] shows that if each node is the source and destination of at most $O(n)$ messages, then all messages can be delivered in $O(1)$ rounds. The following lemma is useful for routing in the Congested Clique model.

The idea behind the renaming technique is that to compare two long strings, one can partition the strings into blocks of the same length, and then compare pairs of blocks in corresponding positions in the two strings. The lexicographic order of the two original strings is determined by the lexicographic order of the first pair of blocks that are not the same. Such a comparison can be done by replacing each block with the block’s rank among all blocks, transforming the original strings into new, shorter strings.

As a first step, the algorithm splits each string into blocks of length $\lceil n^{1/3}\rceil$ characters¹¹1For the sake of simplicity, we assume from now on that $n^{1/3}$ is an integer and simply write $n^{1/3}$ instead of $\lceil n^{1/3}\rceil$. as follows. A string $S$ of length $|S|=\mathrm{\ell }$ is partitioned into $\lceil \frac{\mathrm{\ell }}{n^{1/3}}\rceil$ blocks, each of length $n^{1/3}$ characters except for the last block which is of length $\mathrm{\ell }\mathrm{mod}{n}^{1/3}$ characters (unless $\mathrm{\ell }$ is a multiple of $n^{1/3}$, in which case the length of the last block is also $n^{1/3}$ characters).

In the case that every string is stored in one node, such a partitioning can be done locally. In the more general case, each node $v$ broadcasts the number of strings starting in $v$ and the number of characters $v$ stores from $v$’s last string. This broadcast is done in $O(1)$ rounds by Lenzen’s routing scheme and using this information each node $v$ computes the partitioning positions of the strings stored in $v$. Finally, a block that is spread among two (or more) nodes is transferred to be stored only in the node where the block begins. This transfer of block parts is executed in $O(1)$ rounds since each node is the source and destination of at most $n^{1/3}$ characters.

The next step of the algorithm is to sort all the blocks, using the algorithm of Theorem 4. The result of the sorting is the rank of every block. In particular, if the same block appears more than once, all the block’s occurrences will have the same rank, and for every two different blocks, the order of their rank will match their lexicographic order. Thus, the algorithm will define new strings by replacing each block with its rank in the sorting. As a result, every string of length $\mathrm{\ell }$ will be reduced to length $\lceil \frac{\mathrm{\ell }}{n^{1/3}}\rceil$. Notice that the alphabet of the new strings is the set of ranks, which is a subset of $[1..n^2]$, and therefore each new character uses $O(\log n)$ bits.

In the following lemma we prove that the new strings preserve the lexicographic order of the original strings.

We first prove that $A⪯B\Rightarrow A^{\prime }⪯B^{\prime }$. Recall that by Definition 8 there are two options for $A⪯B$ to be hold:

1. 1.

   If and

2. 2.

   $A$ is a prefix of $B$, i.e. $|A|\le |B|$ and $A=B[1..|A|]$.

For any $j$ let $A_j$ and $B_j$ be the $j$th blocks of $A$ and $B$, respectively.

For the first case, let $\alpha =\lceil \frac{\mathrm{\ell }+1}{n^{1/3}}\rceil$. Notice that $A[\mathrm{\ell }+1]$ and $B[\mathrm{\ell }+1]$ are contained in $A_{\alpha }$ and $B_{\alpha }$, respectively. Thus, for all we have $A_j=B_j$ and for $j=\alpha$ we have $A_{\alpha }\ne B_{\alpha }$. Moreover, by definition $A_{\alpha }⪯B_{\alpha }$. Hence, $A^{\prime }[1..\alpha -1]=B^{\prime }[1..\alpha -1]$ and which means that $A^{\prime }⪯B^{\prime }$.

For the second case, where $A$ is a prefix of $B$ there are three subcases: (1) If $A=B$ then all the blocks in $A$ will get exactly the same ranks as the corresponding blocks in $B$ and therefore $A^{\prime }=B^{\prime }$. (2) Otherwise, . (2a) If $|A|$ is a multiple of $n^{1/3}$ then all the blocks of $A$ are exactly the same as the corresponding blocks of $B$, but $B$ has at least one additional block. Therefore, $A^{\prime }$ is a prefix of $B^{\prime }$ and $A^{\prime }⪯B^{\prime }$. (2b) If $|A|$ is not a multiple of $n^{1/3}$ then the last block of $A$ is shorter than the corresponding block of $B$. Let $\alpha =\lceil \frac{|A|}{n^{1/3}}\rceil$ be the index of the last block of $A$, in particular the block $A_{\alpha }$ is a prefix of the block $B_{\alpha }$, and therefore by definition the rank of $A_{\alpha }$ is smaller than the rank of $B_{\alpha }$. Thus, we have that $A^{\prime }[1..\alpha -1]=B^{\prime }[1..\alpha -1]$ and which means that $A^{\prime }⪯B^{\prime }$.

By very similar arguments, one can prove that $B\prec A\Rightarrow B^{\prime }\prec A^{\prime }$. Thus, the claim $A^{\prime }⪯B^{\prime }\Rightarrow A⪯B$ follows. $◀$

We are now ready to prove Theorem 1 (see also Algorithm 1).

The algorithm repeats the renaming process $7$ times. Since the original longest string is of length $O(n^2)$, after seven iterations, we get that the length of every string is $\lceil O(\frac{n^2}{{(n^{1/3})}^7})\rceil =1$. Thus, at this time, each string is one block of length $1=O(n^{1/3})$ characters. In particular, each string is stored in one node. The algorithm uses one more time the algorithm of Theorem 4 (one could also use the sorting algorithm of [31, Corollary 4.6]) to solve the problem. Notice that during the execution of the renaming process, each block is moved completely to the first node that holds characters from this block. In particular, at the final sorting, each string contains one block, that starts at the original node where the complete string starts. Therefore, the ranks found by the sorting will be stored in the required nodes. $◀$

For every index $i$ the object represents the suffix $S[i..]$ is composed of two parts. The first part is $S_i$ - which is the substring of $S$ of length $t$ starting at position $i$. The second part is the ranks (due to the lexicographic order) of all the suffixes at position in $D{C}_t(S)\cap [i..i+t-1]$ among all suffixes of $D{C}_t(S)$, using ${\mathrm{𝖲𝖠}}_{S^{\prime }}^{-1}$. This information is stored as an array $A_i$ of length $t$ as follows. For every $j\in [0..t-1]$ if $i+j\in D{C}_t(S)$ we set $A_i[j]={\mathrm{𝖲𝖠}}_{S^{\prime }}^{-1}[f(i+j)]$, which is the rank of position $i+j$ (as computed by the recursive call) and $A_i[j]=-1$ otherwise. The first part is used to determine the order of two suffixes which their $\mathrm{𝖫𝖢𝖯}$ is at most $t$ and the second part is used to determine the order of two suffixes which their $\mathrm{𝖫𝖢𝖯}$ is larger than $t$.

The comparison of the objects represent positions $a$ and $b$, is done as follows. The algorithm first compares $S_a$ and $S_b$. If $S_a\ne S_b$ then the order of $S[a..]$ and $S[b..]$ is determined by the order of $S_a$ and $S_b$. Otherwise, $S_a=S_b$ and the algorithm uses the second part of the objects. By Lemma 17 there exists some $k\in [0..t-1]$ such that $a+k$ and $b+k$ are both in $D{C}_t(S)$. In particular $A_a[k]$ and $A_b[k]$ both hold actual ranks of suffixes of $S^{\prime }$ (and not $-1$s). The algorithm uses $A_a[k]$ and $A_b[k]$ to determine the order of $S[a..]$ and $S[b..]$. By the following lemma the order of $A_a[x]$ and $A_b[x]$ is exactly the same order of the corresponding suffixes starting at positions $a$ and $b$.

Let $\mathrm{\ell }=\mathrm{𝖫𝖢𝖯}(S[a..],S[b..])$. By definition, $S[a..a+\mathrm{\ell }-1]=S[b..b+\mathrm{\ell }-1]$ and . Notice that $\mathrm{\ell }\ge t$. Thus, for every $0\le k\le t\le \mathrm{\ell }$ we have $S[a+k..a+k+(\mathrm{\ell }-k-1)]=S[b+k..b+k+(\mathrm{\ell }-k-1)]$ and . Therefore, $S[a+k..]\prec S[b+k..]$. For $k\in [0..t-1]$ such that $A_a[k]\ne -1$ and $A_b[k]\ne -1$, it must be the case that $a+k,b+k\in D{C}_t(S)$. Thus, by Claim 18 we have $S^{\prime }[f(a+k)..]\prec S^{\prime }[f(b+k)..]$ and therefore .

By Lemma 17 there exists some $k\in [0..t-1]$ such that $a+k$ and $b+k$ are both in $D{C}_t(S)$. For this value of $k$ it is guaranteed that $A_a[k]\ne -1$ and $A_b[k]\ne -1$. $◀$

For every index $i\in [1..|S|]$ the algorithm creates an object of size $O(t)$ words of space. Thus, the total size of all the objects is $O(t|S|)\subseteq O(n^{\epsilon }\cdot n^{2-\epsilon })=O(n^2)$. Moreover, by definition $t\le n^{1/3}$. Therefore the algorithm sorts all the objects in $O(1)$ rounds using the algorithm of Theorem 4. By Lemma 19 the result of the object sorting algorithm is a sorting of all the suffixes of $S$.

Recall that for $|S|=O(n^{2-\epsilon })$ we defined $t=\min \{n^{\epsilon },n^{1/3}\}$ and that the length of $S^{\prime }$ is $|S^{\prime }|=|D{C}_t(S)|=O(|S|/\sqrt{t})$. Let $c$ be a constant such that $|S^{\prime }|\le c|S|/\sqrt{t}$ (for any $n>n_0$ for some $n_0$). Denote $S_k$, $S_k^{\prime }$, ${\epsilon }_k$ and $t_k$ as the values of $S$, $S^{\prime }$, $\epsilon$ and $t$ in the $k$th level of the recursion, respectively. Our goal is to gurantee an exponantial growth in the value of $\epsilon$ from level to level. For the first level, in order to have a growth, we have $|S_1^{\prime }|\le \frac{c|S_1|}{\sqrt{t_1}}=\frac{c|S_1|}{n^{0.5{\epsilon }_1}}=\frac{c}{n^{0.1{\epsilon }_1}}\frac{|S_1|}{n^{0.4{\epsilon }_1}}=\frac{c}{n^{0.1{\epsilon }_1}}O(n^{2-1.4{\epsilon }_1}).$ We are setting ${\epsilon }_1=10\log c/\log n$ and so $|S_1^{\prime }|\le O(n^{2-1.4{\epsilon }_1})$. Then, as long as we define ${\epsilon }_{i+1}=1.4{\epsilon }_i$ and we get with similar analysis $|S_i^{\prime }|\le O(n^{2-1.4{\epsilon }_i})$. By a straightforward induction we get $|S_i^{\prime }|\le O(n^{2-{1.4}^i{\epsilon }_1})$. From the time that ${\epsilon }_i\ge 1/3$ (i.e. $|S_i|=O(n^{5/3})$) we have $t_{i+1}=n^{1/3}$. Thus, $|S_{i+1}^{\prime }|=O(|S_i|/\sqrt{t})=O(|S_i^{\prime }|/n^{1/6})=O(n^{3/2})$ and in four rounds we get $S_{i+4}^{\prime }=O(n)$. At this time the algorithm solves the problem in $O(1)$ rounds in one node. Therefore the algorithm performs $O(\log \log n)+4=O(\log \log n)$ levels of recursion. Each level of recursion takes $O(1)$ rounds, and therefore the total running time of the algorithm is $O(\log \log n)$.