ICCG 2022, Sharif UT, February 24, 2022

Geometric Spanner in MPC Model
Mohammad Ali Abam∗

Mohammad Reza Bahrami†

Abstract
The importance of processing large-scale data is growing rapidly in contemporary computation. In order todesign and analyze practical distributed algorithms, recently, the MPC model has been introduced as a theoretical framework. In this paper, we present the geometric spanner construction in the Massively Parallel
Computing (MPC) model. Constructing θ-graph using
the given ϵ, we modified distributed range tree to findthe nearest point to the apex of a θ-cone efficiently andeform a (1 + ϵ)-spanner in O(1) rounds and O(S)time,where S is the memory size of a single machine.
1

Introduction

We consider the problem of finding a geometric spanner
for a set of points in Rd in the MPC model. In thissection we talk about both the spanner and MPC modeland also we motivate our work. Then the sketch of theproof is presented.
1.1

Spanners

Given an edge-weighted graph G = (V, E), the tspanner of G is a weighted graph S = (V, E ′ ) whereE ′ ⊆ E and for every two vertices u and v, dS (u, v) ≤t · dG (u, v), where dS (u, v) indicates the shortest pathdistance between u and v in graph S. That is, the spanner of graph G, is a graph which preserve the distancesby a t multiplicative factor. For a fixed graph G, thesmallest t, which preserve spanner property is called dilation or stretch factor.
Among general graphs, we are focused on Euclidean
geometric graphs, which are complete graphs with a Euclidean metric edge weight function. Hence, a geometricspanner is a complete Euclidean graph, in which for any
two points we have the weight of edge (u, v) ≤ |uv|,
where |uv| indicates the Euclidean distance between
points u and v.
Also, we can view a spanner as compression for themain graph. Assuredly, the fewest edges it has, the morecompressed it is considered. However, we look forward∗ Department of Computer Science, Sharif University of Tech-

nology, Tehran, Iran abam@sharif.edu† Department of Computer Science, Sharif University of Technology, Tehran, Iran mrbahrami@ce.sharif.edu‡ Department of Computer Science, University of Maryland,College Park, MD, US peymanj@cs.umd.edu

Peyman Jabbarzade Ganje‡

to keeping the dilation as low as possible. Assuming
Erdös girth conjecture, there is a tight bound for generalgraphs that there is a (2k−1)−spanner with O(n1+1/k )edges [19].
The extensiveness of spanners’ applications like approximating shortest path queries, routing distributedand parallel algorithms, designing work efficient PRAM
algorithms [13], and etc. make researchers come up withmany ideas and variants to build them efficiently.
1.2

MPC Model and Geometric Problems

The importance of processing large scale data-set is becoming more crucial every day. Over past years we have
faced exponential growth in the speed of generating new
data. Recently, many tools have been developed to process these data practically, among them Map-Reduce
model [10], Hadoop [21], Spark [22] and Dryad [16]. Dueto the diversity of tools and methods, some general theoretical models were built to conceptualise current andforthcoming tools. One of the most realistic and practical abstract models is Massively Parallel Computing or
MPC for short, which was introduced by Karloff et. al[17], as a computation model for Map-Reduce.
In this model [7], [14], [17], it is assumed that there
are M machines, each of which has a memory of size
S known as local memory and the given input size is
N which distributed arbitrarily. Usually, we assume
the memory size is polynomially smaller than the ine α ) where 0 < α < 1. As theput size, i.e. S = O(Nwhole data must fit into machines, we consider M ≥ N
S.
Also, it is common to add polylog factor to the number
e N ) = O(N/S poly(log N )).
of machines, i.e. M = O(S
Also, despite K-machine model [18], there is no point toepoint connection between machines, so there is a O(S)communication limit for each machine.
However, while we consider graph problems, given agraph G = (V, E) the total memory N is consideredas the number of graph edges E which can be O(n2 )where n = |V |. But we are interested in settings where
local memory is small. Thus, there are three studied
regimes in the MPC model for graph problems; Strongsuperlinear where S ≥ n1+c for a constant c > 0, neare
linear where S = O(n),and strongly sublinear whereS = nγ for a constant γ < 1.
In geometric problems, especially in geometricgraphs, as the weight function is defined implicitly without keeping all edge weights on memory, we only con-

5th Iranian Conference on Computational Geometry

sider in the later regime. Henceforth, from now on wee 1−γ ) machines whereconsider n points and M = O(ne γ ) local memory for a coneach of them has S = O(nstant γ < 1.
1.3

Prior Works

There is an extensive line of research on spanners andalso geometric spanners, especially after Chew [9] introduced them in 1986 but term spanner coined by Pelegand Ullman [20]. In addition to some surveys [11], [15],there is a book completely about geometric spanner [19].
Although there is a classic greedy algorithm for computing geometric spanner [4], there are many works to
reduce the running time while preserving useful properties like minimizing maximum degree or not using too
many more edges. E.g. using θ-graph [5] a geometricspanner can be built in O(n log nd−1 ) time with O(n)edges.
Assuming a large data set, there are some works
on streaming mode like [6], which construct a spanning tree in a single path with O(min(m, kn1+1/k ))edges. Also there is a recent work for general graphby Ghaffari et.al [8], constructs a O(k 1+o(1) )-spannerin O(log log n) rounds in strongly sublinear regime with
O(n1+1/k ·log k) many edges. Also Ghodsi et al. provide
a constant round algorithm in MapReduce framework
to build the geometric spanner in L1 metric in R2 usingO(n/ϵ2 ) edges [3].
In recent years, also, there is a growing line of research to solve the geometric problems in the distributedmodel; such as triangulation algorithms in 2D and 3D[23], or finding the nearest neighbor in K-Machine mode
[12].
1.4

Overview of Method

Our algorithm works as follows, for each cone σ we build
a distributed data structure (Next Tree) to obtain thenearest point inside the cone. Inside each cone, it takes
O(d) rounds to find the point which is the nearest one
with respect to its projection on the representative edge.
This is constant if we naturally assume d is constant. To
obtain constant round complexity for all points, we must
re-distribute sub-trees stored on each machine among
searching round, while we look for the nearest point
image on the representative edge. This leads to an algorithm with constant rounds of computation and O(S)time.
2Preliminaries

θ-graph We use an approach based on θ-graph [1] tobuild our spanner. Given constant ϵ, we choose θ suchthat cos 2θ − sin 2θ ≥ 1/(1 + ϵ). On the other hand,a θ-cone is the intersection of d half-spaces such thatthe angle of any two rays emanating at the cone’s apex
and being inside the cone is at most θ. Hence we define
the canonical cone set C, as a collection of O(1/θd−1 )interior disjoint θ-cones, where share apex at the origin.
For a p ∈ Rd , translating each σ ∈ C to the point p,
constructs our θ-graph. Choosing one of the edges ofeach σ ∈ C as representative edge (ℓθ ) the following
lemma from [1] can be stated:
Lemma 1 Let C be a collection of θ-cones, wherecos 2θ − sin 2θ ≥ 1/(1 + ϵ). Choosing ℓσ as representative edge for each θ-cone σ and connecting each point
p to q ∈ σ(p) that its projection on ℓσ minimize theEuclidean distant to p lead us to a (1 + ϵ)-spanner.
Distributed Range Tree A d-dimensional range
tree is a data structure that can answer orthogonal
range queries in O(logd−1 n) time. If d = 1, the range
tree is a balanced binary search tree. For d > 1, therange tree consists of a primary structure in which every node has a range tree on d − 1 dimension for the
point below that node.
Agarwal et al. in [2] show that it is possible to builda range tree in the MPC model efficiently. As the range
tree should be stored in a distributed fashion, a primary
top tree is built which contains O(s1/5 ) top nodes of
the range tree. Hence for each node, the top of the secondary structure build locally and recursively. The procedure continues by using leaves of the primary structure and build the tree recursively. We will use thisstructure and the result of the following theorem from
[2]:
Theorem 2 Given a set P ⊂ Rn , a range tree on P canbe built with size O(n logd−1 n) in constant rounds andO(s logd s) time which can answer orthogonal queries inO(1) rounds and O(logd−1 n) time in MPC model.
3

Next TreeFirst, we consider the definition of Next Tree. The Next
Tree is an augmented distributed range tree that helps
to find the nearest point in a cone to the apex of thequery cone. To build this we amend the range tree [2].
As we discussed earlier, we need a range tree to findthe subset of points inside the query cone σ. Also, weneed to find the nearest point q ∈ σ(p) to connect it to
p in terms of q’s projection to one of σ(p) representative edges or even any arbitrary line at that half-space.
Consider a line in one of the mentioned half-spaces asℓσ , We assume that qσ′ the projection of q on ℓσ is stored
within q.
To build the Next Tree, we add one dimension to eachpoint which contains its rank on ℓσ . This rank can becomputed easily with a constant round of computation[14]. Afterward, a (d + 1)-dimension distributed range
tree is built open this augmented point set Pσ , just like

ICCG 2022, Sharif UT, February 24, 2022

the one appeared in [2]. We only alter the query procedure to find the lowest rank point in the canonicalsubset. This leads us to the following lemma:
Lemma 3 For a point set P ⊂ Rd , Next Tree can bebuilt in O(d) rounds, in O(s logd+1 n) time with sizeO(n logd n).
A query to Next tree is an orthogonal cone σ(p). The
desired response is a point q where qσ′ , the projection ofq on ℓσ , is the next projected point on ℓσ and q ∈ σ(p).
Lemma 4 In d-dimension Next Tree, the next query
can be answered in O(1) rounds and O(logd+1 n) time.
Proof. Without loss of generality consider a orthogonalcone σ(p) = (x1 , . . . , xd ) which is open to (+∞, +∞).
Just like distributed range tree for each query, we mustgo through the data structure. For each xi , where i ≤ d,our search in Next Tree is a path with at most O(log n)points. Just like lemma 3, we must repeat it for each dlevel. However, at the d+1 level, we take a O(log n) pathjust to find the minimum ranked point as the (d + 1)thcoordinate of q is rank of qσ , which takes O(1) roundand O(logd+1 n) time for a single point.
□
4

Spanner Construction

Briefly, the procedure of constructing the spanner is asfollows, as algorithm 1 specify, for each canonical cone
σ, we transform points and build a Next Tree. Then wefind the nearest point to each cone’s apex and connect
them.
Algorithm 1 Distributed algorithm to build a (1 +ϵ) − spanner using θ-graph
Require: Point set P , ϵ, n nodes distributed arbitrary
1: Compute θ based on ϵ and canonical θ - cones C
2: for all σ in C do
3:transform and order points(σ, ℓσ )4:
Tσ = build next tree(σ)
5:find nearest(P , Tσ )6: end for
Recall that for each 1 ≤ i ≤ n, σ(pi ) is translated of
the same canonical cone σ ∈ C. Henceforth, we need toproject all points into ℓσ and also transform all points toform all σ(pi ) orthogonal. After that, we must computethe rank of each projected point on ℓσ which can bedone in a constant rounds for all points [14]. Hence thefollowing proposition is inferred:
Proposition 5 In algorithm 1, the procedure transform and order points project the points onto ℓσ anderank them in O(1) rounds and O(S)time.

Now we must show how find nearest works in parallel for all points. If we want to find the nearest point
one by one it takes O(n) rounds to build the spanner
which is unacceptable in our model.
By lemma 4, it is clear that query one point in the
Next Tree requires O(1) rounds of computation. However, we design an algorithm to find the next point, theadjacent vertex in the desired spanner, for all points inconstant rounds. To this end, we must be able to initiate the search procedure locally for all machines. Hence,each machine needs to have the top sub-tree or the master node which contains the top O(S 1/5 ) nodes [2]. Thiscan be done on logS 1/5 n = O(1) rounds of computation
using the broadcast tree [14]. Afterward, in each machine Mi , s points have been searched and in the next
step their search procedure must continue among set
Mi = {M1 , . . . , Ms }. As a result, we can imagine somecases in which a machine is overwhelmed by Ω(S) nodes
to resume its search procedure. To resolve this problem,at the end of the first searching round, each machine
sends the number of applicant nodes to their destination machine say Mi . As each machine sends a number
to Mi , if the sum of these numbers exceeds S, Mi shouldmake a copy of its self and inform nodes about the newdestinations. Mi choose these machines randomly. Also
it sends the number of required machines, so using thebroadcast tree, we can handle the distribution. The following lemma shows us that this procedure (algorithm2) can be done on constant rounds of computation.
Lemma 6 Targeted sub-trees to resume the query procedure to find neighbour of the point subject to a cone σ
can be redistributed to be able to host all requests at around, with O(1) rounds of computation and O(S) time.
Proof. Notice that, the total number of points is n andalso a machine requires another helping machine for every O(S) applicant point. As S ≥ s = n/M , where s isthe number of points hosted by each machine, the total number of sub-trees to redistribute is less than M .
This is also an upper bound for redistributing a fixed
sub-tree. Again using the broadcast tree to distributethe sub-trees. A machine with exceeded query requests
should choose uniformly at random max (S, r/S) machines, where r is the number of arriving requests. Using the broadcast tree this will end up in the constantround. However, if a machine receives more nodes thanits memory size, it should drop extra sub-trees. So, we
consider Xi the number of guest sub-trees requested tojoin Mi . As E[Xi ] = 1 we can use chernoff bound:P r[Xi ≥ log n] ≤ exp(

1
− log2 n)≤ 2
3n

Using union bound, the probability of no machine re-5th Iranian Conference on Computational Geometry

ceive more than O(log n) nodes is:
P r[X1 ∪ · · · ∪ XM ] ≤

M
X
1
1

n2

=

[2]

P. K. Agarwal, K. Fox, K. Munagala, and A. Nath,“Parallel algorithms for constructing range andnearest-neighbor searching data structures,” inProceedings of the 35th ACM SIGMOD-SIGACTSIGAI Symposium on Principles of Database Systems, ser. PODS ’16, San Francisco, California, USA: Association for Computing Machinery,
2016, pp. 429–440.

[3]

S. Aghamolaei, F. Baharifard, and M. Ghodsi,“Geometric spanners in the MapReduce model,”in Lecture Notes in Computer Science, Springer
International Publishing, 2018, pp. 675–687.

[4]

I. Althöfer, G. Das, D. Dobkin, D. Joseph, and J.
Soares, “On sparse spanners of weighted graphs,”
Discrete Comput. Geom., vol. 9, no. 1, pp. 81–100,
Dec. 1993.

[5]

S. Arya, D. M. Mount, and M. Smid, “Dynamic
algorithms for geometric spanners of small diameter: Randomized solutions,” Computational Geometry, vol. 13, no. 2, pp. 91–107, 1999.

[6]

S. Baswana, “Streaming algorithm for graphspanners—single pass and constant processing
time per edge,” Information Processing Letters,
vol. 106, no. 3, pp. 110–114, 2008.

[7]

P. Beame, P. Koutris, and D. Suciu, “Communication steps for parallel query processing,” inProceedings of the 32nd ACM SIGMOD-SIGACTSIGAI Symposium on Principles of Database Systems, ser. PODS ’13, New York, New York,
USA: Association for Computing Machinery,
2013, pp. 273–284.

[8]

A. S. Biswas, M. Dory, M. Ghaffari, S. Mitrović,and Y. Nazari, “Massively parallel algorithms for
distance approximation and spanners,” in Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures, ser. SPAA
’21, Virtual Event, USA: Association for Computing Machinery, 2021, pp. 118–128.

[9]

L. Chew, Paul, “There are planar graphs almost
as good as the complete graph,” Journal of Computer and System Sciences, vol. 39, no. 2, pp. 205–
219, 1989.

[10]

J. Dean and S. Ghemawat, “Mapreduce: Simplified data processing on large clusters,” Commun.
ACM, vol. 51, no. 1, pp. 107–113, Jan. 2008.

[11]

D. Eppstein, “Chapter 9-spanning trees and spanners,” Handbook of Computational Geometry,pp. 425–461,

M
1
≤
2
n
n

So, with high probability, no machine receives moree δ ), thethan log n nodes. Using the fact that S = O(nlemma concludes.
□
Algorithm 2 find nearest(P, Tσ )Require: Point set P and its projection on ℓσ within,
Pre-computed and stored Tσ , Constant k =logS 1/5 n = O(1)1: Distribute the master node to all machines and set
as current searching node Mi on each machine
2: for k times do
3:
Perform the search on Mi locally and find theMi machine set to resume the search
4:
Inform Mi members about the coming requests
5:
Redistribute the machine Mi if necessary
6: end for
Using proposition 5 and lemma 3, we conclude thatthe first two lines of the for loop in Algorithm 2 requireseO(1) rounds and O(S)time. Moreover, by lemmas 4
and 6 the find nearest procedure requires O(1) rounds
and O(S) time. Assuming d and ϵ are constants leads
to the following theorem:
Theorem 7 In the MPC model, a geometric (1 + ϵ)spanner can be built using O(1) rounds of computationeand O(S)time.
5Concluding Remarks

We considered constructing a geometric spanner in the
MPC model. Benefiting from θ-graph, we designed analgorithm to build this spanner in constant rounds ofcomputation. However, we can consider the same problem to find a spanner with a smaller final degree. Also,
we can consider the problem in dynamic or kinetic models if we consider the possibility of temporal changes inour point, with less work.
References[1]

M. A. Abam and M. de Berg, “Kinetic spanners in Rd ,” in Proceedings of the Twenty-Fifth
Annual Symposium on Computational Geometry,ser. SCG ’09, Aarhus, Denmark: Association for
Computing Machinery, 2009, pp. 43–50.

ICCG 2022, Sharif UT, February 24, 2022

[12]

R. Fathi, A. R. Molla, and G. Pandurangan, “Efficient distributed algorithms for the k-nearest
neighbors problem,” in Proceedings of the 32nd
ACM Symposium on Parallelism in Algorithms
and Architectures, ser. SPAA ’20, Virtual Event,
USA: Association for Computing Machinery,
2020, pp. 527–529.

[13]

S. Friedrichs and C. Lenzen, “Parallel metric treeembedding based on an algebraic view on moorebellman-ford,” J. ACM, vol. 65, no. 6, Nov. 2018.

[14]

M. T. Goodrich, N. Sitchinava, and Q. Zhang,“Sorting, searching, and simulation in the mapreduce framework,” in Proceedings of the 22ndInternational Conference on Algorithms andComputation, ser. ISAAC’11, Yokohama, Japan:
Springer-Verlag, 2011, pp. 374–383.

[15]

J. Gudmundsson and C. Knauer, “Dilation anddetours in geometric networks,” Handbook of Approximation Algorithms and Metaheuristics Chapman & Hall/CRC Computer & Information Science Series, 2007.

[16]

M. Isard, M. Budiu, Y. Yu, A. Birrell, and D. Fetterly, “Dryad: Distributed data-parallel programsfrom sequential building blocks,” SIGOPS Oper.
Syst. Rev., vol. 41, no. 3, pp. 59–72, Mar. 2007.

[17]

H. Karloff, S. Suri, and S. Vassilvitskii, “A modelof computation for mapreduce,” in Proceedings of
the Twenty-First Annual ACM-SIAM Symposium
on Discrete Algorithms, ser. SODA ’10, Austin,
Texas: Society for Industrial and Applied Mathematics, 2010, pp. 938–948.

[18]

H. Klauck, D. Nanongkai, G. Pandurangan, and
P. Robinson, “Distributed computation of largescale graph problems,” in Proceedings of theTwenty-Sixth Annual ACM-SIAM Symposium on
Discrete Algorithms, ser. SODA ’15, San Diego,
California: Society for Industrial and Applied
Mathematics, 2015, pp. 391–410.

[19]

G. Narasimhan and M. Smid, Geometric Spanner Networks. USA: Cambridge University Press,
2007.

[20]

D. Peleg and J. D. Ullman, “An optimal synchronizer for the hypercube,” in Proceedings of thesixth annual ACM Symposium on Principles of
distributed computing, 1987, pp. 77–85.

[21]

T. White, Hadoop: The definitive guide. ” O’Reilly
Media, Inc.”, 2012.

[22]

M. Zaharia, M. Chowdhury, M. J. Franklin, S.
Shenker, and I. Stoica, “Spark: Cluster computing with working sets,” in Proceedings ofthe 2nd USENIX Conference on Hot Topics inCloud Computing, ser. HotCloud’10, Boston, MA:
USENIX Association, 2010, p. 10.

[23]

H. Zhou, H. Wu, S. Xia, M. Jin, and N. Ding,“A distributed triangulation algorithm for wireless sensor networks on 2d and 3d surface,” in 2011
Proceedings IEEE INFOCOM, 2011, pp. 1053–
1061.