$O(1)$-Round MPC Algorithms for Multi-Dimensional Grid Graph Connectivity, Euclidean MST and DBSCAN

Consider an implicit $(d,c)$-grid graph $G=(V,ℰ)$; let $[x_{\min }^{(i)},x_{\max }^{(i)}]$ be the value range of $V$ on the $i$-th dimension (for $i\in \{1,2,\mathrm{\dots },d\}$), where $x_{\min }^{(i)}$ and $x_{\max }^{(i)}$ are the smallest and largest coordinate values of the points in $V$ on dimension $i$, respectively. The minimum bounding space of $G$ is defined as $\text{mbr}(V)=[x_{\min }^{(1)},x_{\max }^{(1)}]\times [x_{\min }^{(2)},x_{\max }^{(2)}]\times \mathrm{\cdots }\times [x_{\min }^{(d)},x_{\max }^{(d)}]$. Moreover, we denote the projection of $\text{mbr}(V)$ on the $i$-th dimension by $\text{mbr}(V)[i]=[x_{\min }^{(i)},x_{\max }^{(i)}]$.

Consider the minimum bounding space $\text{mbr}(V)$; a $c$-divider on the $i$-th dimension at coordinate $x$, denoted by $\pi (i,x)$, is an axis-parallel rectangular range whose projection on dimension $i$ is $[x,x+c-1]$ and the projection on dimension $j\ne i$ is $\text{mbr}(V)[j]$. With a $c$-divider $\pi (i,x)$, the vertex set $V$ is partitioned into three parts: (i) the left part $V_{\text{left}}=\{u\in V\mid u[i]\le x-1\}$, (ii) the right part $V_{\text{right}}=\{u\in V\mid u[i]\ge x+c\}$, and (iii) the boundary part $S_{\pi }=V\cap \pi (i,x)$, where $u[i]$ is the $i^{\text{th}}$ coordinate of a vertex $u$.

We say that $\pi (i,x)$ separates $G$ into two sub-graphs induced by the left and right part, i.e., $V_{\text{left}}$ and $V_{\text{right}}$, respectively. And all the vertices in $S_{\pi }$ are called separator vertices. Observe that for any $u\in V_{\text{left}}$ and any $v\in V_{\text{right}}$, $|u[i]-v[i]|\ge c+1$ implying $\parallel u,v{\parallel }_{\mathrm{\infty }}\ge c+1$. As a result, there must not exist any edge between such $u$ and $v$. With such notation, we show the following Binary Partition Lemma.

We prove this lemma with a constructive algorithm. Given the vertex set, $V$, our algorithm first finds two integers, $y_j$ and $z_j$, for each dimension $j\in [1,d]$. Specifically, $y_j$ is the largest integer that the number of the vertices in $V$ located to the “left” of $y_j$ is at most $\frac{|V|}{2(1+d)}$, while $z_j$ is the smallest integer that the number of the vertices in $V$ located to the “right” of $z_j$ is at most $\frac{|V|}{2(1+d)}$. Formally, and $z_j=\min \{x\in \mathbb{N}:|\{v\in V\mid v[j]>x\}|\le \frac{|V|}{2(1+d)}\}$, where $v[j]$ is the coordinate of $v$ on dimension $j$.

Consider the hyper-box in ${\mathbb{N}}^d$, whose projection on each dimension is $[y_j,z_j]$ for $j\in [1,d]$. By the definition of $y_j$ and $z_j$, this box contains in total at least $|V|(1-\frac{2d}{2(d+1)})=\frac{|V|}{d+1}$ vertices in $V$. Since the coordinates of the points are all integers, the volume of the box must be at least $\frac{|V|}{d+1}$. That is, ${\prod }_{j=1}^d(z_j-y_j+1)\ge \frac{|V|}{d+1}$. Thus, there must exist some dimension $i$ such that $z_i-y_i+1\ge {(\frac{|V|}{1+d})}^{\frac{1}{d}}$. Next we fix this dimension, $i$. Let $S_{\pi (i,x)}$ be the set of all vertices in $V$ falling in a $c$-divider $\pi (i,x)$. Within dimension $i$, each vertex in $V$ can be contained in at most $c$ consecutive $c$-dividers. As a result, we have ${\sum }_{x^{\prime }\in [y_i,z_i-c]}|S_{\pi (i,x^{\prime })}|\le c|V|$. Since there are $z_i-c-y_i+1$ terms in the summation, there exists an integer $x\in [y_i,z_i-c]$ with

where the second inequality comes from the bound on $z_i-y_i+1$ and the third inequality is due to $c\le s^{\frac{1}{d^3}}\le \frac{1}{2}\cdot {(\frac{|V|}{(1+d)})}^{\frac{1}{d}}$ as $|V|>s$. Then such $\pi (i,x)$ is a desired $c$-divider.

Next, we bound the size of $V_{\text{left}}$ with respect to $\pi (i,x)$: bounding $|V_{\text{right}}|$ is analogous. Since $x\ge y_i$, there are only two possible relations between $x$ and $y_i$:

• $\mathrm{■}$

  If $x>y_i$, according to the definition of $y_i$, the number of vertices in $V$ to the left of $\pi$ is at least $|V|(\frac{1}{2d+2})\ge \frac{|V|}{4d+4}$.

• $\mathrm{■}$

  If $x=y_i$, the number of vertices in $V$ to the left of $\pi$ is at least $\frac{|V|}{2d+2}-|S_{\pi (i,x)}|\ge |V|\left(\frac{1}{2d+2}-\frac{2c{(d+1)}^{\frac{1}{d}}}{{|V|}^{\frac{1}{d}}}\right)\ge \frac{|V|}{4d+4}$.

Either way, $|V_{\text{left}}|\ge \frac{|V|}{4(d+1)}$ holds; Lemma 7 thus follows. $◀$

Given an implicit $(d,c)$-grid graph $G=(V,ℰ)$ with $1\le c\le s^{\frac{1}{d^3}}$ and $|V|>s$, initialize $S\leftarrow \mathrm{\varnothing }$ and perform the following steps:

• $\mathrm{■}$

  apply Lemma 7 on $G$ to obtain $\{S_{\pi },\{V_{\text{left}},V_{\text{right}}\}\}$;

• $\mathrm{■}$

  $S\leftarrow S\cup S_{\pi }$;

• $\mathrm{■}$

  if $|V_{\text{left}}|>s$, recursively apply Lemma 7 on $G_{\text{left}}=(V_{\text{left}},ℰ)$;

• $\mathrm{■}$

  if $|V_{\text{right}}|>s$, recursively apply Lemma 7 on $G_{\text{right}}=(V_{\text{right}},ℰ)$;

A construction algorithm proves existence, hence:

While our Pseudo $s$-Separator (PsSep) looks similar to the notation of the Orthogonal Vertex Separator (OVSep) proposed by Gan and Tao [22], we emphasize that some crucial differences between them are worth noticing. First, the OVSep was originally proposed for solving problems on $(d,1)$-grid graphs (in the External Memory model). Our PsSep supports implicit $(d,c)$-grid graphs for parameter $c$ up to a non-constant $s^{\frac{1}{d^3}}$ in the MPC model. This extension, discussed in Section 3, plays a significant role in our $O(1)$-round algorithm for computing Approximate EMST’s. Second and most importantly, it is still unclear how (and appears difficult) to compute the OVSep in $O(1)$ MPC rounds. In contrast, our PsSep is proposed to overcome this technical challenge and can be computed in $O(1)$ MPC rounds. However, as discussed in the next sub-section, because of the application of $\epsilon$-approximation in the construction algorithm of PsSep, the separator size at each recursion level no longer geometrically decreases and therefore, leading to a logarithmic blow-up in the overall separator size in PsSep. Despite of this size blow-up, by setting the parameters carefully, we show that our PsSep can still fit in the local memory of one machine, and thus, it is still good enough for the purpose of computing CC’s on implicit $(d,c)$-grid graphs and solving the Approximate EMST and Approximate DBSCAN problems in $O(1)$ rounds in the MPC model.

Recall that Theorem 15 shows that a pseudo $s$-separator $S$ of $G$ can be computed in $O(1)$ rounds with high probability. This algorithm works for all constant $\alpha \in (0,1)$. However, as we shall see shortly, both our CC and MSF algorithms require the pseudo $s$-separator, $S$, to fit in the local memory $O(s)$ in a single machine. As a result, they require $|S|\le s$. From the proofs of Lemma 10 and Lemma 13, we know that $|S|\le \frac{4c|V|}{s^{1/d}}\log s$. Recalling that $s={|V|}^{\alpha }$, our algorithm works when $\alpha \ge \frac{d+1}{d+2}$ for $d\ge 3$. Combining the case of $d=2$, a feasible range of $\alpha$ becomes $(\max \{\frac{d+1}{d+2},\frac{4}{5}\},1)$.

Consider a pseudo $s$-separator $S$ of $G$; let $G_i=(V_i,ℰ)$ be the induced sub-graphs of $G$ by $S$, where $i\in [1,h]$. By Definition 6, we have $h=O(\frac{|V|}{s})$ and $|V_i|\in O(s)$. For each $G_i$, denote the projection of $\text{mbr}(V_i)$ on dimension $j$ by $[x_i^{(j)},y_i^{(j)}]$, for $i\in [1,h]$ and $j\in [1,d]$. Consider the hyper-box $H_i$ whose projection on each dimension $j$ is $[x_i^{(j)}-c,y_i^{(j)}+c]$ for $i\in [1,h]$ and $j\in [1,d]$; we say that $H_i$ is the extended region of $G_i$. Moreover, we define the extended graph of $G_i$, denoted by $G_i^{+}=(V_i^{+},ℰ)$, as the induced graph by the vertices in $V_i^{+}=V_i\cup S_i$, where $S_i=S\cap H_i$ is the set of separator vertices falling in the extended region of $G_i$. Figure 1 shows an example of $G_i$ and $G_i^{+}$. Clearly, by choosing a constant $\alpha \in (\max \{\frac{d+1}{d+2},\frac{4}{5}\},1)$, we know that $|S|\in O(s)$ and hence, $|V_i^{+}|\in O(s)$. Therefore, $G_i^{+}$ fits in the local memory in one machine. Moreover, without loss of generality, we assume that $G_i^{+}$ is stored completely in a machine $M_i$.

By incorporating the techniques of the existing External Memory CC and MSF algorithms for grid graphs [22], where the detailed MPC implementations of them are respectively shown in Algorithm 2 and Algorithm 3 in Appendix A, we have the following theorem:

Let $P$ be a set of $n$ points in $d$-dimensional Euclidean space ${ℝ}^d$, where the dimensionality $d\ge 2$ is a constant. For any two points $u,v\in P$, the Euclidean distance between $u$ and $v$ is denoted by $\text{dist}(u,v)$. There are two parameters: (i) a radius $\epsilon \ge 0$ and (ii) core point threshold $\mathrm{𝑚𝑖𝑛𝑃𝑡𝑠}\ge 1$ which is a constant integer. For a point $v\in P$, define $B(v,\epsilon )$ as the ball center at $v$ with radius $\epsilon$. If $B(v,\epsilon )$ covers at least $\mathrm{𝑚𝑖𝑛𝑃𝑡𝑠}$ points in $P$, then $v$ is a core point. Otherwise, $v$ is a non-core point.

Consider an implicit core graph $G=(P_{\text{core}},ℰ)$, where $P_{\text{core}}$ is the set of all the core points in $P$, and there exists an edge between two core points $u$ and $v$ if $\text{dist}(u,v)\le \epsilon$. Each connected component $C$ of $G$ is defined as a primitive cluster. For a primitive cluster $C$, let $C^{\prime }$ be the set of all the non-core points $p\in P$ such that $\text{dist}(p,C)={\min }_{u\in C}\text{dist}(p,u)\le \epsilon$. The union of $C\cup C^{\prime }$ is defined as DBSCAN cluster.

Given a set of points $P$, a radius $\epsilon \ge 0$ and a core threshold $\mathrm{𝑚𝑖𝑛𝑃𝑡𝑠}\ge 1$, the goal of the DBSCAN problem is to compute all the DBSCAN clusters.

Given an extra approximation parameter, $\rho \ge 0$, the only difference is in the definition of the primitive clusters. Specifically, consider a conceptual $\rho$-approximate core graph $G_{\rho }=(P_{\text{core}},{ℰ}_{\rho })$, where the edge formation rule ${ℰ}_{\rho }$ works as follows. For any two core points $u,v\in P_{\text{core}}$: if $\text{dist}(u,v)\le \epsilon$, ${ℰ}_{\rho }(u,v)$ must return that $(u,v)$ is in $G_{\rho }$; if $\text{dist}(u,v)>(1+\rho )\epsilon$, ${ℰ}_{\rho }(u,v)$ must return that $(u,v)$ does not exist in $G_{\rho }$; otherwise, what ${ℰ}_{\rho }(u,v)$ returns does not matter.

Due to the does-not-matter case, $G_{\rho }$ is not unique. Consider a graph $G_{\rho }$; each connected component $C$ of $G_{\rho }$ is defined as a primitive cluster with respect to $G_{\rho }$. And an $\rho$-approximate DBSCAN cluster is obtained by including non-core points to a primitive cluster $C$ in the same way as in the exact version. The goal of the $\rho$-approximate DBSCAN problem is to compute the $\rho$-approximate DBSCAN clusters with respect to an arbitrary $G_{\rho }$.