Parallel and Efficient Hierarchical k-Median Clustering
Authors: Vincent Cohen-Addad
Silvio Lattanzi
Ashkan Norouzi-Fard
Christian Sohler
Ola Svensson
Venue: NeurIPS 2021 Poster (2021)
Keywords: Clustering
k-Median
Hierarchical

Abstract: As a fundamental unsupervised learning task, hierarchical clustering has been extensively studied in the past decade. In particular, standard metric formulations as hierarchical $k$-center, $k$-means,  and $k$-median received a lot of attention and the problems have been studied extensively in different models of computation. Despite all this interest, not many efficient parallel algorithms are known for these problems. In this paper we introduce a new parallel algorithm for the Euclidean hierarchical $k$-median problem that, when using machines with memory $s$ (for $s\in \Omega(\log^2 (n+\Delta+d))$), outputs a hierarchical clustering such that for every fixed value of $k$ the cost of the solution is at most an $O(\min\{d, \log n\} \log \Delta)$ factor larger in expectation than that of an optimal solution. Furthermore, we also get that for all $k$ simultanuously the cost of the solution is at most an $O(\min\{d, \log n\} \log \Delta \log (\Delta d n))$ factor bigger that the corresponding optimal solution.  The algorithm requires in $O\left(\log_{s} (nd\log(n+\Delta))\right)$ rounds. Here $d$ is the dimension of the data set and $\Delta$ is  the ratio between the maximum and minimum distance of two points in the input dataset. To the best of our knowledge, this is the first \emph{parallel} algorithm  for the hierarchical $k$-median problem with theoretical guarantees. We further complement our theoretical results with an empirical study of our algorithm that shows its effectiveness in practice.

Parallel and Efficient Hierarchical k-Median Clustering
Vincent Cohen-Addad"
Silvio Lattanzi'
Google Research cohenaddaad@google. com
Google Research
silviol@google. com
Ashkan Norouzi-Fard
Christian Sohler+ University of Cologne csohler@uni toounni-ooennnn de
Ola Svensson" EPFL ola. alaassveesssn@eell.cco
Google Research achkammorouzzigooggle.. com
Abstract
As fundamental unsupervised learning task, hierarchical clustering has been extensively studied in the past decade. In particular, standard metric formulations as hierarchical k-center, k-means, and k-median received a lot of attention and the problems have been studied extensively in different models of computation. Despite all this interest, not many efficient parallel algorithms are known for these problems. In this paper introduce hierarchical m-median problem that, when using machines with memory s (for 8 E S2llog (n A + d))). outputs a hierarchical clustering such that for every fixed value of k the cost of the solution is at most ((min(d, log n. log A) factor larger in expectation than that of an optimal solution. Furthermore, we also get that in for all & simultanuously the cost of the solution is most expected O (minn(d d,, log n2} log log( Adn) factor bigger that the corresponding optimal solution. The algorithm requires in O (log, (ndlog(n dimension of the data set and A is the ratio between the maximum and minimum distance of two points in the input dataset. To the best of our knowledge, this is the first parallel algorithm for the hierarchical k-median problem with theoretical guarantees. We further complement our theoretical results with empirical study of our algorithm that shows its effectiveness in practice.
parallel algorithm for the Euclidean
A))) rounds. Here is the
Introduction
Clustering is central tool in any large scale machine learning library. The goal of clustering is to group objects into subsets so that similar objects are the same groups while dissimilar objects are in different groups. There are many different definitions of clustering depending on the description of the objects, the similarity measure between objects, as well as the application. While it is impossible to find the perfect formulation for clustering problem ([29), see also [13), the metric version of the problem has received a lot of attention over the last decades and a central topic in unsupervised learning research.
Here we focus on one fundamental metric clustering problem: the hierarchical Euclidean k-median problem. In this formulation, the input objects are described by vectors and the distance (dissimilarity) between objects measured by their Euclidean distance. More formally, given a S Rd the objective of the hierarchical k-median problem in its classic formulation 33
is to return an ordering
"Equal contribution
Work was partially done while author visiting researcher Google Research, Switzerland.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

cI....,,cr Cr. of points and set of n nested partitions PI.....P, Pn of P (i.e., for any 1 S S n. the (i-11 1)-patittion is obtained by merging two clusters in the i-partition) such that the following objective is minimized: the maximum over all S & S n of the ratio of Σi= Epec, lpp - cilla to the optimum unconstrained k-median cost, where Ck = {ci...., Ct) is the set of centers and Ps (C,,... -......,cc. a k-partition. In this paper, we will provide a slightly different guarantee: instead of minimizing the maximum ratio, we show that for every fixed k this ratio is O ( (d, log n log A) in expectation. Our results extend a slightly weaker bound that holds simultanuously for all k. We also remark that the above problem formulation implies a similar bound for the variant of the problem where we do not require an ordering of the centers but instead choose the optimal center for each cluster of the partition.
Hierarchical clustering, thanks to its ability in explaining the nested structures in real world data, has been extensively studied in the computer science literature (27 26 22 43 9 14
41 44 The main focus of previous work has been sequential solutions for the problem and they are difficult to apply on large data sets. For this reason, several papers recently proposed scalable hierarchical
clustering algorithms [27 26 22 43 5 39 34]. Nevertheless most prior work has focused only on scaling the single-linkage algorithm (in fact, efficient MapReduce and Spark algorithms are known for this problem 27 26 46 for which no objective function clearly specified.
Another closely related area of research focuses on the k-median and k-means "flat" clustering problems in the distributed setting where several important results are known B3 6 The main idea behind these algorithms is to compute in a distributed way some form of small summary
[8
B5]
I TO 23)
of the data (such as coresets). However, all algorithms based this framework use at least + n' memory per machine (often significantly more) to solve the problem in O rounds. Unfortunately, this is too much in our setting where we want solve the problem also for l ((x) (in fact to solve the hierarchical clustering problem we need to compute a solution even for k = n 1). To overcome this problem, in a recent related work [31] Lattanzi al. provide a parallel algorithm for the hicrarchical Euclidean k-median problem by dividing the data in two clusters iteratively. Unfortunately, this approach does not provide any theoretical guarantees for the problem (in the experimental section we actually show that it may return low quality solutions) and its round complexity is Ologn).
Our Results. In this work we design the first distributed algorithm for the hierarchical Euclidean k-median problem with provable guarantees. In particular, our algorithm returns an approximate solution to the problem using memory E M(log" + n + d)), O (nog log(n + A))) parallel rounds, and O(nd/s s) machines, where À is the ratio between the maximum and minimum distance of two points. Note that this implies that our algorithm runs in a constant number of rounds if E ne for any constant 8 > Interestingly, our algorithm is easily implementable in standard parallel frameworks such as MapReduce [16]. Hadoop [5], Spark [77 and Dryad [25 etc. and we analyze it in the standard Massive Parallel Computation (a. k. a. MPC) model [28 21 7 Furthermore, we complement our theoretical analysis with an experimental study in distributed setting where we show that our algorithm is significantly faster than parallel hierarchical [T and flat solutions 10 18
for the k-median problem.
Properties, extensions and limitations. Work efficiency. An interesting aspect of our algorithm is that the total running time of our algorithm across all machines is almost linear. In particular, the total running time of our algorithm is O(nd) so it has almost optimal work efficiency To the best of our knowledge, our algorithm is also the first approximation algorithm having almost linear running time for the nigh-dimensional Euclidean k-median problem (at the expense of having an expected Ominn(d, log k} log A) A) factor)
Round Lower Bound. We note here that Theorem 4 in g can be easily extended the Fuclidean k-median problem and so to the hierarchical Fuclidean k-median problem. Thus, no distributed
'In this section, for the sake of simplicity, we use Ô notation to hide both log n and log A factors. The exact term are provided in the following sections.
*We remark that for general metric spaces there is a lower bound of Q((kk) total work to achieve a constant approximation guarantee for our problem [37]. Furthermore, we note that finding a constant fonttont-factor approximation algorithm for the Euclidean k <-median problem in almost linear time would imply an asymptotically better approximation algorithm for the closest pair problem which is long standing open problem in algorithm design. For low-dimensional Fuclidean space, near-linear time algorithms are known [1] 3D)
'The exact same construction and proof work also for the Euclidean k-median problem.
2

---

algorithm with memory can output any approximate solution in less than log, n rounds. So our memory-round complexity trade-off is asymptotically optimal.
Simplicity and Efficiency. Our algorithm is extremely simple to implement. In fact, our results show that it is possible to approximate the hierarchical Euclidean k-median problem just by using sorting algorithm and few aggregation operations. For the same reason, our algorithm is also very parallelizable and efficient.
Practicality, Besides our theoretical guarantees our algorithm is also very efficient in practice. We run distributed experiments and we show that the algorithm is more accurate and efficient than previous parallel algorithms. Furthermore, for lt 10 our algorithm already outperforms the classic distributed algorithms for flat k-mediar
[3] [0 [8] by factor of 3. For larger k the gap becomes
even larger (for example for k = 1000 our algorithm is an order of magnitude faster 7
The large k setting. In recent paper [ the authors showed for the first time that it is possible to compute an approximate solution for the Euclidean k-means problem using parallel memory significantly smaller than k. In particular they provide a bi-criteria algorithm that approximates the solution of the k-means problem within a factor O(log n log log n)) using O( log & log n) centers, memory-per-mane per-machimeee is also possible for the k-median problem. Furthermore our algorithm returns a solution that is not bi-criteria solving an open question in [8].
S2(d log n²), and Olog, n.) parallel rounds. Our algorithm proves that this
Limitations. Our result has two main limitations. First, it relies on the existence of a good tree embedding that can be computed in few MPC rounds. As we show in this paper, it is indeed possible to compute a tree embedding of a d-dimensional Euclidean point set with expected distortion Od A) in a constant number of rounds. While there exists sequential O(log n) -istorrioo tree embedding construction of point sets of size n of arbitrary metric spaces (20). it remains an interesting open problem as to how this could be implemented in constant number of rounds. Second, the expected approximation factor of our algorithm O(min dd, log n log A) and the expectation is for every fixed k. Nevertheless, in our experimental analysis, show that in practice the quality of our solution is comparable to state-of th- algorithms while being much faster.
For additional related work we refer the reader to the full version.
2 Preliminaries
For two points p. we use |p - g|l to denote their Euclidean distance. For a point p and set C' C Rd we define DIST(P, C) min [p cil, i.e., the distance from p to its closest point in C. For two partitions P1,P2 we say that P1 is nested in P2 if P2 can be obtained from P1 by merging two or more parts of PI. Given a point set P C Rd. a set of centers C' {cI,.... }. and partition P of P into k parts (PI...., pk]. its k-median cost is COST(P, C,P) E EpEr, DIST c,). The points in C' are called the cluster centers. We let OPT(P, P. k) = minogrs, minp,p p = C,, denote the cost of an optimal k-median solution.
In this paper, we focus on slight variation of the classic Hierarchical Euclidean k-median problem which for given point set P C R2 asks to find an (ordered) sequence of centers C' = (ci..... C. together with a collection of nested partitions the entire space and contains i parts. We say that an algorithm for the Hicrarchical Euclidean k-median problem has an approximation guarantee of if, for every k 1,...,n, n. the out- put C, IT defines an a-approximate solution for k-median. That is, for every h: E (1,2..... COST(P, (cI....,c&] Pk)) I a OPT(P,A) Similarly, if the algorithm is randomized then we say that it has an approximation guarantee of if the guarantee holds in expectation over the random hierarchical clustering C, II output by the algorithm: for every E (1,2,...,, E[COST(P, tct...., J. S a OP.(P.)).
{PI..... Pa } of P. such that P. partition
"Note that flat clustering is sub-prohlem of hierarchical Fuclidean k-median problem, in fact our algorithm solve the problem for all at the same time
Note that the large & has many practical applications in spam and abuse 38 42
depl-duplicate detec-
tion [24]. compression or reconciliation tasks [40]
We note here that our results naturally extend to the Prefix Euclidean m-median problem 36 where clusters
not required to be nested.
3

---

For simplicity of presentation, here we assume that P S fo.....A................. and then we explain how to remove this assumption in our theoretical analysis in Appendix. The k-median problem can also be formulated for discrete metric spaces M = (P, DIST where P is finite set of points and DIST M a metric. For a subset _ P of the points, we also D (p. C)= = min.ec DIST M (p. c) be the distance from the point to its closest point in C. The objective of the metric k-median problem is then to find a subset C C P of size & such that C (P, C) = > DIST (p, C)) is minimized. The hierarchical k-median problem is analogously defined.
A (discrete) metric space (P, DISTT) is called a tree metric, if there exists a positively weighted tree T' = (P, E, w) such that for all pairs P.q p.q E P we have that DISTT q) equals the shortest path distance between and in T", We will be mostly interested in tree metrics that are defined by restricted hierarchically well separated trees. |
Definition 2.1 A restricted E-hierarchically well separated tree (RHST) is a positively weighted rootdd tree such that all the leafs are the same level, all edges at the same level have the same weight, and the length of the edges decreases by a factor of l on every root to leaf path.
Throughout the paper, we consider RHSTs with E = 2, i.e., 2-RHSTs. We therefore simplify notation and sometimes write RHST for 2-RHST. In the next section, we describe how to embed our point set P in Euclidean space into the leaf of RHST. Formally, a metric embedding between two metric spaces (P, DIST). DIST') is an injective mapping f P + P'. To simplify notation and to be consistent with this definition (and the definition of metric) we consider instances that contain no two points within distance 0. However, all our arguments and algorithms generalize to instances that may have several identical points.
that considered de-facto the standard theoretical model for large-scale parallel computing. Computation in MPC proceeds in synchronous parallel rounds over multiple machines. Each machine has memory s. At the beginning of computation, data is partitioned across the machines. During each round, machines process data locally. At the end of round, machines exchange messages with a restriction that each machine is allowed to send messages and also receive messages of total size The efficiency of algorithm in this model is measured by the number of rounds it takes for the algorithm to terminate and by the size of the memory of every machine. In this paper focus the most challenging and practical regime of small memory. In particular, we only assume to have E 2(log" (n + A + d)).
MPC model. We design algorithms for the MPC model 288 21
3 A Work Efficient Sequential Algorithm
In this section we introduce work efficient sequential algorithm and then in the next section, we show how to parallelize it in the MPC model. From a high level perspective our algorithm is based on embedding the input point set into the leaf of RHST and then solving the problem optimally for the embedded points. In order to obtain the embedding, we choose (standard) random quad-tree embedding of the input points into a hicrarchically well separated tree. We then show that a simple the induced tree metric. Unfortunately, naive
greedy algorithm solves the problem optimally implementation of our greedy algorithm would result in large parallel and sequential rumning time. So we modify our greedy algorithm and we show that it can be implemented using only few aggregation operations combined with sorting.
3.1 Quadtree Embedding into a 2-RHST
The first step of our algorithm is to embed the points in a restricted 2-hierarchically separated tree. Interestingly, we observe that using standard embedding techniques is possible embed all the points in the datasets in 2-RHST by incurring only small distortion. Furthermore, in this construction every point can compute its own position in the embedding independently just by knowing its own coordinated and a random shift r that is applied to all the points.
Given that the construction of the embedding is standard defer it to the full version. Now we present formally the main property of the embedding that will be useful for our algorithm. Before
"Our definition is slightly more restricted than the standard notion of f- H-HST (see. for example, (4). because we require that all edges at the same level have the same cost (rather than all descendants of node) and that the cost decreases by the same factor.

---

stating the property we need to introduce some additional notation. For two points p. 9 in the RHST T. we use DIST q) to denote their (shortest-paad -aatt distance. Similarly we let DIST (p. C) min DIST c). We now define COSTr C) == Σper DISTr(p, C*) to be the cost of a set of centers C' with respect to the tree metric. We use OPT (PTx(P,k) == milloge+,)C CO C) to denote the cost of optimal solution with respect to a given RHST T. Recall that OPT(P, k) denotes the cost of an optimal solution with respect to the original Euclidean distances. Now we are ready to state the main result of this section whose proof is presented in the full version.
Theorem 3.1 Let P S fo.....
A......JJ A]d be a point set. There exists procedure that constructs 2- 2-RHST tree T time OOdd log A) such that for the its optimum solution CT. using lo centers, we have [[ + = (dd I log A) OPT(P, (P, k). Furthermore all the input points are mapped COST(P,Ct
to leaves of the RHST. In addition, we have that E[max;
OrT(P.k) = O(d - log A log(dnA)).
3.2 Optimal Algorithms for k-Median on 2-RHST
In this subsection, we design two optimal sequential algorithms for hierarchical k-median on 2-RHST metric. This combined with our 2-RHST embedding will give us an efficient approximation algorithm. We first show that simple greedy algorithm (see Algorithm 1) finds the optimum solution. The greedy algorithm chooses, at each step, the point that leads to the largest decrease in the cost. Then we modify the algorithm to be more amenable to parallel implementation and to run in almost linear time.
3.2.1 A Greedy Algorithm for 2-RHST
We start by providing the pseudo-code for our algorithm in Algorithm I and state the main property of our greedy algorithm (whose proof is deferred to the full version )
Theorem 3.2 For any set of points P C {O,..... A and distance function DISTI defined by 2-RHST T, Algorithm returns an optimum solution for the hierarchical k-median problem.
Proof First observe that by the cluster assignment in line (8) the returned partitions (Pi...., Pn] are nested. It remains to show that for every k. the partition Pş with centers C1y...,Gr C% is optimal. The proof is by induction on the height of the tree T' For the base case, when T is height O, the statement clear: In that case the instance consists of single point so COSTT(P,S) = if + Ø.
Algorithm 1 GREEDY alg. for hier. k-median on 2-RHST
Input:
Set of points P, cost function COST. de- fined
by a 2-RHST
1: Set S. < 0
2: Set Po < (P)
3: Label all internal nodes of the RHST as unla- belled
For the inductive step we make two fundamental observations. First, we observe that in a 2-RHST
4: for 1 to n do
metric the cost of a solution can be decomposed as a sum of the cost of individual subtrees. Sec- ond, we also show that the cost of each subtree roughly independent of the choice made by the algorithm in other subtrees. So combining these two facts, with the fact that greedy is op- timal for all the subtrees of we can conclude our inductive arguments,
5: Let G; = argminges COSTr(P,rUS;_)
6: Label the highest unlabelled ancestor of c; with
7:
S is obtained by adding & to S
8:
Define P. as the clustering obtained by as- signing all points to the cluster centered at their closest labelled ancestor.
9: end for
Output: return C1, CI...., Cn, Pı.... Pn
3.2.2 Quasi Linear Time Algorithm
In this subsection we show how to change the previously presented algorithm (Algorithm I to obtain an almost linear-time algorithm that can easily parallelized. The algorithm will output a list of centers and an implicit description of list of nested partitions. The list of centers as well as the partitions will be identical to that of the previous algorithm. Hence, we will focus on the optimality of the centers wrt. the hierarchical k-median problem.
5

---

As a first step we modify Algorithm I to reduce its sequential dependencies. The downside of Algorithm Tis that the selection to open the i-th point depends on the previously chosen points, i... Si-1. The main idea is to remove this dependency and to make the decision dependent on other parameters that can be efficiently precomputed. Before describing our result we introduce some additional notation. We say that a node in the (2-RHST) tree is at level i if the subtree rooted at this node is of height i. We remark that with this convention a Ieaf is at level O and the root is at the maximum level h. Let S be a set of centers and x be a point in P \ S. We refer to the ancestor of a at level i by (z( and, with some abuse of notation, we denote with p(()) the number of points in the subtree of (1) for 0 S i S h. We also write A,(x) S P for the set of points in the subtree of node (z)).. Finally, we let {(r) E {1..... h} be the highest level E for which S n Ac()) = 0. For clarity,
when it is clear from the context, we drop the and use a,, As. Pt,
Our first key observation is that the distance of a point x to its nearest center only depends on f. This is true because i) the distance of to the point y E S 0 A4+1 is exactly twice the distance of x to ag+t, which is 2 > 2' 2(2 - 1) 2 2. ii) The distance to any other point w E S is at least 26+2 2 since their common ancestor is least at level l ++ 1. Therefore,
Observation 3.3 The distance DIST( 5) of a point x to its nearest center in S only depends on ((x). More precisely, DISTT( S) 20(2)+1 - 2.
In addition, we observe that the benefit of opening x (denoted by BENF(x)) only depends on the number of nodes in close subtrees, p...... Pr- In fact opening x only affects the cost of the points in Ag. This is true because any point w that is in A N is at least as close to x as to any other point in Ae+1 and not in Ae. Now, consider point y in A, for < iis < l. The cost of y after opening is 2 2. and before opening x its cost was 2 2. Furthermore, we can precisely compute the number of points in A, and not in A, it equals p. P:-1- So we get:
Lemma 3,4 The benefit of opening point x only depends on p1(x). ........................ PE(e)) (z) and is BENF(Z) E (x) Pp:-(())) (2*(r)+1 - where for simplicity we assume p-1(x) O.
These simple observations significantly reduces the dependency of computing the benefit of opening a point x from the set of centers S, which is the main step of) Algorithm 1] In fact, the BENF(x) value does not depend for all é before opening the centers and use only those values to make our selection of the centers.
the full structure of S but only {(x). Theretore,
compute (ENF(x)
We denote this by BENF( f), i.e., BENF(#, f) = (P)))( pi)) (2(+1 - 21+1), for all points x and 0 < sé h.
Now, to select the centers we can design an alternative algorithm based only on the BENF(æ, E) values. In fact we can sort all the BENF E) in an ordered list L and go over them from the highest value to the lowest. We show that it is sufficient to prune the list L by removing a pair (z,, E) in the following two cases:
There is another point with larger benefit in Ae. In this case we need to update our sorted list by removing (z. E) from the ordering L. In general to deal with this case for each subtree rooted level é for all possible é we preserve only one pair (x, E) with highest benefit.
- For point xr collect all pairs (1r E) that remained after the previous pruning step. Identify the pair with the maximum value of and prune all other collected pairs.
After these two steps, the ordering L can be used to obtain our final solution for Hierarchical k-median (resp. k-median) by returning the centers in the same order as in L (resp. the top k centers of L). The pseudo-code is presented in Algorithm 2]
Importantly, we show that the output sequence of centers and the implicitly defined partitions of Algorithm 2 are the same the output of Algorithm This is intuitively true because the pruning rules identify at which level r is a good candidate for the greedy algorithm and then we sort the x based on their score at that level. Note that in this algorithm we only output the partition implicitly because outputting them explicitly will take 2(n²) time. The full proof of this argument is presented in the full version.
Theorem 3.5 Algorithm 2 finds an optimum solution for the hierarchical k-median problem RHSTs in time O(n log" (A + n)).

---

4 Euclidean k-Median in the MPC Model
In this section we present main results in the MPC model. The algorithm that we use is the same [Algorithm 2| but we implement each step in the MPC model. Our algorithm is based on basic operations: summation, computing the maximum and sorting a list of elements. All these operations can be done efficiently in the MPC model using [21]. We provide the details on the implementation of our algorithm along with its theoretical performance guarantees.
Algorithm 2 Quasi-linear alg. for hier. k-median on RHST
Input:
Set of points P. cost function COSTT de- fined by a 2-RHST T
1: Va E P,O 0 < E S h, compute BENF(2, 6)
2: for 0 E h do
3: for subtree T" S T rooted at level do
4: Let x T" be the point maximizing BENF(I, for Me T' do
Theorem 4.1 There is distributed algorithm
that uses memory 8 E (odlogg + log (A n)) and compules solution for the hierarchical Euclidean k-median problem such that for ev- ery fixed k the k-clustering of the hierarchy has an expected approximation factor of Odd log A). Furthermore, the expected maximum approxima- tion factor (over all k)) is (d A log( (dnn). The algorithm uses O (log, (n log A)) parallel rounds and O(n s) machines in the MPC model. Furthermore the total rumning time of the algorithm across all the machine is (Od log( A + n))).
5:
6:
C(a.,) + C(a.)) U {v} If # x delete BENF(Y, E)
7:
8: end for
9: end for
end for
11: For every x keep only the pair (r, e) with
maximum and its cluster C(a.))-
12: Sort all pairs (x, E) according
BENF(", E)
and let (c,, E.) be the pair in position i.
Implicitly define the i-th partition P;
(Pi....,P) .... as follows: P, = C(c,,t)) A
Proof. Our distributed algorithm consists of parallel implementation of Algorrthm 2 that we run on the embedding described in |Section 3.1
ش for 1 S. Output: Return the ordering of the points Ci....: On as centers and the clusters Clas8)
This gives us an expected approximation factor of Old log A). because from Theorem 3.5 we
Vi to implicitly define the partitions.
know that Algorithm 2) solves the problem op- timally on 2-RHST and from Theorem 3.1 we
know that we loose a factor Od A) in expectation in our embedding step.
The details for the distributed implementation of this algorithm in the MPC model is as follows. In the implementation we need to be able to compute the embedding, compute pe(x) for all points x, compute BENF, discard the useless BENF pairs and sort the values. First, note that can compute the embedding in parallel for each of the points because the embedding only depends on their coordinates and uniform random shift. Then to compute (a( and BENF for all nodes we just need to be able to compute weighted sums efficiently. This can be done using memory s E 2dd A log + n)) in Olog, (n log A)) MPC rounds with O(In log A)/s) machine and total running time of O(nd log A) using the algorithm in [21]. Then we need to sort the computed BENF values which can be done similar to be previous step using (21) with the same bounds as before. To apply the filter we just need to be able to find the maximum in list of values and we can again do this using memory E R(log" (A + n)) in Olog,, (n log A)) MPC rounds using the algorithm in (21) Note that after computing the maximum we can also construct the sets C(z.e) by outputting as C(a.t) all nodes sharing the same ancestor of x at level f, and this can be done in O(1) rounds as well. Finally we can also do sorting with the same bound using the same techniques with total running time of O(n log n).
We remark that we can speed up the algorithm for datasets of large dimension, by reducing the dimension from d to Ollog n) by losing a small constant factor in the approximation ratio [5] and achieve the following result, the details are presented in the full version. We also remark that the guarantee on the expected maximum approximation ratio (over all k) from Theorem 3.1 to this theorem and the following corollary.
carries over
Corollary 4.2 There is distributed algorithm that uses memory 8 E (logg( + n d)) and computes solution for the hierarchical Euclidean k-median problem such that
7

---

-10F
(a) KDD Cup
-10"
(b) SONG
-107
(c) US Census
1.5
GOOURAGGO BB LLLM
Solution Cost
1.5
Solution Cost
Solution Cost
05
0.5
0.5
10
100
1000
10
100
1000
1:
10
100
1000
Figure 1: In this plot, compare our algorithm (QURAL.G)) and L.L.M. The results are presented in for KDD Cup (a), SONG (b), US Census (c). All the numbers reported for 5 runs (average value and variance).
10"
(a) KDD Cup
-10*
(b) SONG
-107
(a) US Census
2.5
JEOURALGO
KM++
Solution Cost
2
BEL
Solation Cost
Solution Cost
1.5
In
CSZ
1.5
PLSH
EIN
0.5
1:
102
10
104
8 =
10
10a
104
10
102
10
Figure 2: In this plot, compare algorithm (OURALGO), k-median++ seeding (KM++ Seed), BEL, PI.SH, and EIM. The results are presented in for KDD Cup (a), SONG (b), Us Census (c). All the numbers reported for runs (average value variance).
(8)
(h)
(6)
300
QURALGO
40
Relative mimning
KM++ Sead
Relative romning
Relative rumsing
100
200
BEL
20
0
0.2
0.4
0.6
0.8
0
0.2
0.1
0.5
0.5
0.2
0.1
0.6
0.8
-10
-10
Figure 3: Figure (a). (c) compares the running time for our algorithm (OURALGO). k-mediant+ seeding (KM++ Seed), BEL, PLSH, and CSZ on HIGGS and US Census datasets, respectively. In (b) focus algorithm and k-median++ seeding HIGGS dataset further highlight their differences.
for every fixed k the k-clustering of the hierarchy has an expected approximation factor of O(min (d, log n) log A log(ndd))- The algorithu uses O (log, log(n + A))) parallel rounds and O(nd log(n + s) machines in the MPC model. Furthermore the total running time of the algorithm across all the machine is O(nd(log(n A))). Finally the algorithm returns solution also for the prefix k-median clustering and the hierarchical k-median clustering problems.
Empirical Evaluation
In this section we empirically evaluate our algorithm with both hierarchical and aon-hierarchica algorithms. We report the expected value and the variance over 5 runs for all the randomized algorithms. We evaluate the algorithms on the following data sets from UCI Machine Learning
Repository [7] KDD Cup ka. Intrusion, SONG, n = 515, 345; d 90).US Census Data (1990) (n 2, 458, 285; d 29),and HIGGS (n 11, 000. 000; d = 28).
31, 0299 d = 35), YearPredictionMSDD (a.k.a
8

---

5.1 Distributed Hierarchical Algorithms
We compare algorithm with LLLM [3] an algorithm for hi- erarchical k-median problem in dis- tributed setting. In Fig. 1 we com- pare the quality of the produced solu- tion. We observe that the algorithms are comparable and our algorithm out performs LLLM by 2 3% on av- erage. The running time of the the LLLM algorithm divided by the run- ning time of our algorithm is presented in (Tall Our algorithm significantly faster (up to factor 10 26 depending on the dataset) and the difference increases with number of the machines used.
Dataset
m=1x
10x
100x
KDD Cup
9.58
13.5
26.9
SONG
2.32
5.26
19.3
US Census
1.72
3.10
6.71
Table I: Distributed hierarchical algorithms running time comparison for various number of machines. The running time of the LLLM baseline divided by the running time of our algorithm with the same amount of machine used.
5.2 Distributed Algorithms
Our algorithm can be also used for the noon-hierarchical) k-median problem. In order assess its quality, we compare it with sequential and distributed algorithms for the hierahiearrc k- k-median problem. i) We compare the quality of the computed set of centers and the sequential running time with both sequential and distributed algorithms for the k-median problem, ii) we compare the running time with distributed algorithms in a distributed setting, iii) we run our algorithm on massive datasets of with tens of billions of nodes and report the speedup gained by using more machines. Notice that the baselines do not scale to this size of data, therefore we cannot compare the performance.
Baselines. We compare our algorithm (without dimensionality reduction) with well-known se- quential algorithm: k-median++ seeding; and four distributed algorithms: PLSH (8), EIM (I9), BEL (2). CSZ [TO] Description of these algorithms and the details of the setting used for running the algorithms are provided in the full version.
Quality and Sequential Running Time Comparison. Our algorithm 40, 41, 300 times faster than k-median+++ BEL, and PLSH, respectively for census dataset for k = 10, 000. Also it is figure 3 we compare the running time of these four algorithms for different A (recall that compute the solution for all k are similar for other datasets and are presented the full version. Let us focus on the quality of the solution. The results consumption of the PLSH, CSZ, and EIM we were not able to run it in some cases. The results suggest that algorithm provides comparable results.
significantly faster than CSZ 10
the same time). The plots
presented in Fig. 2) Note that due to the slow running time and memory
Distributed Running Time Comparison. Now we focus on the running time of OURALGO, BEL, EIM, and CSZ algorithms in distributed setting for HIGGS dataset. We compare the running time of the baselines with our algorithm with the same amount of machine used for k=10 to 10, 000. We present the running time of the baselines divided by the running time of our algorithm. The results are presented in the full version. Our algorithm is significantly faster than all baselines. For small values of k. e.g:
10, we are faster by a factor 3.2 60.2, 50 182, and 65 1380 compared to BEL, EIM, and CSZ, respectively. Moreover, for k = 1, 000 we are 12.08 - 71.2, 2082 3091, 46 941 times faster compared to BEL. EIM, and CSZ, respectively. Also for 10, 000 we are 41.17 126 and 171 708 times faster than BEL and CSZ, respectively.
Scalability on Large Datasets. To provide an empirical scalability analysis of our algorithms over large datasets, expanded the HIGGS dataset to experiment datasets of size almost 100 millions, billion, and 10 billions. More details can be found in the full version of the paper.
The missing values are due to the slow running time of CSZ., EIM is slower that rest of the algorithms and its running time is presented in the Appendix.

---

Conclusions
We present the first distributed approximation algorithm for Euclidean Hierarchical k-Median problem in the MPC model. Interestingly our algorithm even works in the setting where each machine has very limited memory interesting to obtain similar results for other clustering problems and to improve the approximation factor of our algorithm. We believe that the core ideas used in this work can extend to the general k-clustering problem (e.g., k-means and higher powers). To be more precise, if we are given a RHST that increases the distances by most factor of (n)), then we believe that our approach construct g(n) approximate solution, for any function g. The difficulty here is to construct such RHST.
O(log (A + n + d)) and it is work efficient. In the future, it would be
Acknowledgments and Disclosure of Funding
This research was partially supported by the Swiss National Science Foundation projects 200021- 1 14655 "Randomness in Problem Instances and Randomized Algorithms".
10

---

References
[1] Bahman Bahmani, Benjamin Moseley, Andrea Vattani, Ravi Kumar, and Sergei Vassilvitskii. Scalable k-means++. Proc. VLDB Endow., 5(7):622-633, 2012.
[2] Maria-Florina Balcan, Steven Ehrlich, and Yingyu Liang. Distributed k-means and k-median clustering on general communication topologies. In Christopher C. Burges, Léon Bottou, Zoubin Ghahramani, and Kilian Q. Weinberger, editors, Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, pages 1995-2003, 2013.
[3] Maria-Florina F Balcan, Steven Ehrlich, and Yingyu Liang. Distributed k- k-means and k-median clustering on general topologies. In Advances in Neural Information Processing Systems, pages 1995 2003, 2013.
[4] Yair Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS), pages 184 193, 1996.
[5] M. Bateni, S. Behnezhad, M. Derakhshan, M. Hajiaghayi, S. Lattanzi, and V. Mirrokni. On distributed hierarchical clustering. In NIPS 2017, 2017.
[6] MohammadHossein Bateni, Aditya Bhaskara, Silvio Lattanzi, and Vahab Mirrokni. Distributed balanced clustering via mapping coresets. In Advances in Neural Information Processing Systems, pages 2591-2599 2014.
[7] Paul Beame, Paraschos Koutris, and Dan Suciu. Communication steps for parallel query processing. In Proceedings of the 32nd ACM SIGMOD-SIGACTSSICAA symposium on Principles of database systems, pages 273-284. ACM, 2013.
[8] Aditya Bhaskara and Maheshakya Wijewardena. Distributed clustering via Ish based data partitioning. In International Conference on Machine Learning, pages 570-579, 2018.
[9] Moses Charikar and Vaggos Chatziafratis. Approximate hierarchical clustering via sparsest cut and spreading metrics. Proceedings of the Swenty-Eightt Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, Jamuary 16-19, pages 841-854, 2017.
[10] Jiecao Chen, Erfan Sadeqi Azer, and Qin Zhang, A practical algorithm for distributed clustering and outlier detection. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018
2018, 3-8 December 2018, Montréal, Canada, pages
[11] Vincent Cohen-Addad A fast approximation scheme for low- wow-dimensionll k-manns In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM- SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 430 SIAM, 2018.
[12] Vincent Cohen-Addad, Andreas Emil Feldmann, and David Saulpic. Near-linear time approxi- mations schemes for clustering in doubling metrics. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 540-559. IEEE Computer Society, 2019.
[13] Vincent Cohen-Addad, Varun Kanade, and Frederik Mallmann- Dallmann--Tennn. Clustering redemption- beyond the impossibility of kleinberg's axioms. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 2018
11

---

[14] Sanjoy Dasgupta. A cost function for similarity- based hierarchical clustering. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing. STOC 2016. Cambridge, MA, USA, June 18-21, 2016, pages 1 118-127, 2016.
[15] Sanjoy Dasgupta and Anupam Gupta. An elementary proof of theorem of johnson and lindenstrauss. Random Struct. Algorithmss, 22(1):60-655 2003.
[16] Jeffrey Dean and Sanjay Ghemawat. Mapreduce: simplified data processing on large clusters. Communications of the ACM, (11)110771133, 2008.
[17] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017.
[18) Alina Ene, Sungjin Im, and Benjamin Moseley. Fast clustering using mapreduce. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 681 681-689, 2011.
[19] Alina Ene, Sungjin Im, and Benjamin Moseley. Fast clustering using mapreduce. Chid Apté, Joydeep Ghosh, and Padhraic Smyth, editors, Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, CA, USA, August 21-24, 2011, pages 681-689. ACM, 2011.
[20] Jittat Fakcharocnphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. Journal of Computer and System Sciences, 69(3):485-499 2004.
[21] Michael T Goodrich, Nodari Sitchinava, and Qin Zhang. Sorting, searching, and simulation in the mapreduce framework. In International Symposium Algorithms and Computation, pages 374-383. Springer, 2011.
[22] C.C. Gower and J. Ross. Parallel algorithms for hierarchical clustering. Parallel Computing, 21(8):1313- - 1325, 1995.
[23] Sudipto Guha, Yi Li, and Qin Zhang. Distributed partial clustering. ACM Transactions on Parallel Computing, 1:3:11:1-11:22 2019.
[24] Oktie Hassanzadeh, Fei Chiang, Renée J. Miller, and Hyun Chul Lee. Framework for evaluating clustering algorithms in duplicate detection. PVLDB 2(1):1282-129, 2009.
(25) Michael Isard, Mihai Budiu, Yuan Yu, Andrew Birrell, and Dennis Fetterly. Dryad: distributed data-parallel programs from sequential building blocks. In ACM SIGOPS operating systems review, volume 41, pages 59-72. ACM, 2007.
[26] Chen Jin, Zhengzhang Chen, William Hendrix, Ankit Agrawal, and Alok N. Choudhary. Incremental, distributed single-linkage hierarchical clustering algorithu using mapreduce. In Proceedings of the Symposium on High Performance Computing, HPC 2015, part of the 2015 Spring Simulation Multiconference, SpringSim '15, Alexandria, VA, USA, April 12-15, 2015, pages 83 92, 2015.
[27] Chen Jin, Ruoqian Liu, Zhengzhang Chen, William Hendrix, Ankit Agrawal, and Alok N. Choudhary. A scalable hierarchical clustering algorithm using spark. In First IEEE International Conference on Big Data Computing Service and Applications. BigDataService 2015, Redwood City, CA, USA. March 30 April 2, 2015, pages 418 426, 2015.
[28] Howard Karloff, Siddharth Suri, and Sergei Vassilvitskii. model of computation for mapre- duce. In Proceedings of the twenty-firsl annual ACM-SIAM symposium on Discrete Algorithms, pages 938-948. SIAM, 2010.
[29] Jon M Kleinberg. An impossibility theorem for clustering. In Advances in neural information processing systems, pages 463-470, 2003.
[30] Stavros G Kolliopoulos and Satish Rao. A nearly linear-time approximation scheme for the euclidean k-median problem. In European Symposium on Algorithms, pages 378-389, Springer, 1999.
12

---

[31] Silvio Lattanzi. Thomas Lavastida, Kefu Lu, and Benjamin Moseley. A framework for paral- lelizing hierarchical clustering methods. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 73-89. Springer, 2019.
[32] Silvio Lattanzi, Thomas Lavastida, Kefu Lu, and Benjamin Moseley. A framework for paral- lelizing hierarchical clustering methods. In Ulf Brefeld, Élisa Fromont, Andreas Hotho, Amo J. Knobbe, Marloes H. Maathuis, and Céline Robardet, editors, Machine Learning and Knowledge Discovery in Databases European Conference, ECMI PKDD 2019, Würzburg, Germany, September 16-20, 2019, Proceedings, Part I, volume 11906 of Lecture Notes in Computer Science, pages 73-89. Springer, 2019.
[33] Guolong Lin, Chandrashekhar Nagarajan, Rajmohan Rajaraman, and David Williamson. general approach for incremental approximation and hierarchical clustering. SIAM Journal on Computing, (9(3):363333666 2010.
[34] Q. Mao, W. Zheng, L. Wang, Cai, V. Mai, and Y. Sun. Parallel hierarchical clustering in linearithmic time for large-scale sequence analysis. In 2015 IEEE International Conference on Data Mining, pages 310-319, Nov 2015.
[35] Alessio Mazzetto, Andrea Pietracaprina. and Geppino Pucci. Accurate mapreduce algorithms for k-median and k-means in general metric spaces. In 30th International Symposium on Algorithms and Computation, ISAAC 2019, December 8-11, 2019, Shanghai University of Finance and Economics, Shanghai, China, pages 34:1-34:16, 2019.
[36] Ramgopal Mettu and C. Greg Plaxton. The online median problem. SIAM Comput., 32(3):816 832, 2003.
[37] Ramgopal R. Mettu and C. Greg Plaxton. Optimal time bounds for approximate clustering. Machine Learning, 56(1-3):35-60, 2004.
[38] Feng Qian, Abhinav Pathak, Yu Charlie Hu, Zhuoqing Morley Mao, and Yinglian Xie. A case for unsupervised-lcaure weaerdd---aannnbaeaeeee spam filtering. In Proceedings of the ACM SIGMETRICS international conference Measurement and modeling of computer systems, pages 367-368, 2010.
[39] Sanguthevar Rajasekaran. Efficient parallel hierarchical clustering algorithms. IEEE Trans. Parallel Distrib. Syst., (6(6))497-500) June 2005.
[40] M. Ali Rostami, Alieh Saeedi, Eric Peukert, and Erhard Rahm. Interactive visualization of large similarity graphs and entity resolution clusters. In Proceedings of the 21th International Conference on Extending Database Technology, EDBT 2018, Vienna, Austria, March 26-29, 2018., pages 690-693, 2018
[41] Aurko Roy and Sebastian Pokutta. Hierarchical clustering via spreading metrics. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 2316-2324, 2016.
[42] Mina Sheikhalishahi, Andrea Saracino, Mohamed Mejri, Nadia Tawbi, and Fabio Martinelli. Fast and effective clustering of spam emails based on structural similarity. In International Symposium on Foundations and Practice of Security, pages 195-211, Springer, 2015.
[43] Spark. https://spark.apg http:/paa....aacc...rg////////// htw.:///l/mmiiiiilseernnnanmmaaa 2014.
[44] Joshua Wang and Benjamin Moseley. Approximation bounds for hierarchical clustering: Average-linkage, bisecting k-means, and local search. In NIPS, 2017.
[45] Tom White. Hadoop: The definitive guide. O'Reilly Media, Inc.". 2012.
[46] Grigory Yaroslavtsev and Adithya Vadapalli. Massively parallel algorithms and hardness for single-linkage clustering under lp distances. In Proceedings of the 35th International Conference on Machine Learning, ICML. 2018, Stockholmsmässson Stockholm, Sweden, July 10-15, 2018, pages 5596-5605, 2018.
[47] Matei Zaharia, Mosharaf Chowdhury, Michael Franklin, Scott Shenker, and Ion Stoica. Spark: Cluster computing with working sets. HotCloud, 10(10-10):95, 2010.
13


Reviews:
[{"review_id": "wx2ldQDyQv7", "reviewer": "Reviewer_2DG5", "summary": "The authors of this paper consider the Hierarchical k-median clustering problem in the Euclidean setting, and they give approximation algorithms with provable guarantees for it in the Massive Parallel Computation (MPC) model. Specifically, they given the first results with bounded approximation ratios for the problem in the MPC model.\n\nAlthough I'm somewhat familiar with hierarchical clustering, this is the first time I came across the MPC model. However, it looks like a very reasonable setting for parallel computation. According to it, each machine has memory $s$. Then we proceed with a number of rounds, in which each machine processes data locally, and at the end of the round the machines can exchange messages of size at most $s$. Obviously, efficiency in this setting is measured with respect to how large $s$ should be and how many rounds the algorithm might take. The authors study an interesting and realistic I would say regime, where the memory available to each machine is relatively small.   \n\nThe authors solve their problem in two steps. First they provide a sequential algorithm. The latter begins by embedding the metric space in a a restricted 2-hierarchically separated tree (2-RHST). Then the authors show how you can find an optimal solution for an 2-RHST instance, and hence in the sequential step they end up only paying the distortion of the embedding in the approximation ratio. Finally, for the second step of their framework they show how their sequential algorithm can be readily parallelized in MPC model. \n\nFinally, experiments are presented, which clearly demonstrate that the given algorithm is much faster than many possible baselines (both parallel and sequential heuristics). In addition, in terms of the objective function value, it is shown that the output of the algorithm is actually quite comparable to even sequential approaches like k-median++. Another experimental advantage of the proposed algorithms, seems to be its simplicity that leads to it being easily implemented.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "CONFIDENCE - ORIGINALITY:\n\nAlthough I'm familiar with metric clustering, I have to admit that I do not have much experience in hierarchical clustering. In addition, I'm completely unfamiliar with the literature on parallel algorithms. That being said, I do not believe I can adequately judge the originality and the significance of this work. Nonetheless, it feels like providing the first parallel algorithms for hierarchical k-median is a solid contribution and that's why I believe that this paper should appear in NeurIPS. \n\nCLARITY:\n\nFor the most part the paper is nicely written and clear. I would have preferred a more detailed discussion on related work on sequential hierarchical k-median. Specifically, an expansion of the paragraph in lines 41-47.\n\nQUESTION/SUGGESTION TO AUTHORS:\n\nMy point here relates to my previous comment regarding discussing related work more. Can you elaborate more on the properties of the LLLM algorithm you use as a baseline in Section 5.1? This seems like the most comparable competitor and it feels like you should have explained it in more detail. For example, is it a heuristic (I suppose it is)? What runtime guarantees it has?\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours reading the paper + 1 hour thinking about the review + 1 hour writing the review"}, "extra_text": {}}, {"review_id": "uGJApZOXD0H", "reviewer": "Reviewer_kqYe", "summary": "This paper proposes a parallel algorithm for hierarchical k-means in the MPC model. The algorithm makes use of a randomized tree embeddings of a dataset. The authors prove the approximation ratio for their algorithm (for every value of k) as well as the space and round complexity. In experiments on 4 datasets, the proposed algorithm achieves either competitive/superior performance to a handful of baselines (in terms of clustering cost), and is demonstrated to be scalable and efficient.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "*Originality*: \nThis work builds on existing research in parallel/distributed clustering. The proposed algorithm is novel, but is built from well-known components: RHST embedding techniques and achieving certain operations in the MPC model.  The key novelty in the algorithm lies in the observations that many of the required computations only require knowledge of the RHST, and can therefore be performed in parallel. The proof techniques are relatively straightforward, but the observations which lead to the parallelization are interesting.\n\n*Quality*: \nWhile there are a lot of details skipped in the proofs, the algorithm and arguments made in this paper seem correct to me. While reading, I had a question about fundamentals (appears in the clarity paragraph), but I have assumed this is my own misunderstanding rather than a flaw. \n\nThe experiments are sufficient but could be improved. The proposed algorithm is compared to a handful of baselines in terms of cost and speed. The datasets chosen are reasonable, but better datasets could be used. In particular, none of the datasets have particularly high dimension and only 2 have more than 1M points. Since the theoretical results depend on \\delta, it would be informative to compute/report \\delta for each of the datasets.   \n\nIn the experiments, is the time for computing the RHST included in the timing? Please be clear about this; it is an important detail.\n\n*Clarity*: \nThis paper was a pleasure to read. It is very clear: the writing/grammar is easy to digest, the flow of ideas is sensible, the authors provide examples and high-level descriptions of their algorithms to make their theoretical arguments easy to follow. I especially like the progression from sequential to parallel to MPC, which I thought made the algorithms easily understandable.\n\nOne thing that was slightly difficult was keeping track of all the tree notation in 3.2.2.  Perhaps a visual aid could help. \n\nIn Section 4: loose → lose\n\nAlgorithm 2: after line 10, we have for every subtree, a single point x that maximizes benefit. Then, in line 11, it seems like we filter these points so that each point can only be associated with a single subtree (the highest one where it maximizes benefit). But doesn’t this mean that if a point maximizes benefit for more than 1 subtree, then after filtering, there will be some subtrees with no associated point/center? Please clarify. In writing my review I assume this is my own misunderstanding and not a flaw in the algorithm.\n\nIn your proposed algorithm, is the RHST computed in a distributed fashion or prior to the MPC setting?\n\n*Significance*: \nEmpirically, the proposed algorithm has potential to be adopted in practice. The empirical results demonstrate that the algorithm achieves either superior or competitive performance with a number of baselines (and has relatively small variance). Moreover, it is scalable and efficient, which are both very important given the increasing size of datasets and computing infrastructure. \n\nAlgorithmically, this work is also significant. While the idea of embedding a dataset in an RHST is not new, the parallelization of the clustering algorithm after this transformation seems novel. As the authors mention in their conclusion, it may be possible to apply similar techniques to develop additional parallel clustering algorithms for different cost functions--which would be useful.\n\nWhile many of the proofs are skipped, I do not think that any significantly new proof techniques were developed in this work.\n\nEDIT AFTER AUTHOR RESPONSE: thank you for the informative response, especially the pointers to the appendix and the clarifications about not explicitly computing the RHST and the experiments/datasets/baselines. Also, thank you for fixing the typos in the algorithm.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As mentioned in the introduction, one limitation is the proposed algorithm relies on a high-quality and efficiently computable tree embedding of a dataset.  Also, as mentioned, their theoretical results only hold in expectation, but this is understandable given their randomized embedding. Also, their bounds are a function of the largest and smallest distance between any two points in the dataset.\n\nDue to space constraints much of the proofs are significantly shortened or completely skipped. It would have been nice to include more of these proofs for a better understanding (for example, for Theorem 3.2).\n", "review_text": "", "extra_scores": {"ethical_concerns": "I do not see any ethical issues with this work.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "JaIDOyJg0I", "reviewer": "Reviewer_c7EP", "summary": "This manuscript studied introduce a new parallel algorithm for the Euclidean hierarchical k-median problem that claimed to be the first parallel algorithm for the hierarchical k-median problem with theoretical guarantees. However, I slightly recommend for acceptance despite the imperative importance of targeted problem.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n\n1. Clearly written and well-organized manuscript, lucid background and problem statement.\n2. The motivation is creative, presenting the first distributed approximation algorithm for Euclidean Hierarchical k-Median problem in the MPC model, when k-median received a lot of attention and the problems have been studied extensively.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Cons:\n\n1.\tThe proposed model strongly relies on the existence of a good tree embedding, which weaken the applications of the model and uncertain results of specific tasks.\n2.\tThere's no theoretical guarantee that for all k, the cost of the solution is at most a factor bigger that the corresponding optimal solution. \n3.\tIt seems not to be the first distributed approximation algorithm for Euclidean Hierarchical k-Median problem in the MPC model. In my research, it is possible to compute an approximate solution for the Euclidean k-means problem using parallel memory.\n4.\tThere's no theoretical explanation to speed up the algorithm for datasets of large dimension, by reducing the dimension from d by losing a small constant factor in the approximation ratio.\n5.\tThe experiment needs to be further improved and strengthened. All data sets used do not reflect the diversity of data, and obviously cannot reflect all adaptation scenarios in the real world. At the same time, the advantages of the experimental results on some data sets are not prominent.\n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "two"}, "extra_text": {}}, {"review_id": "HrJ8JqnYWv", "reviewer": "Reviewer_KiLL", "summary": "This paper studies the hierarchical k-medians clustering problem and develops a new parallel algorithm. The algorithm is based on building a tree embedding of the dataset parallelly first and then the partitions of the dataset are computing using this tree. A rigorous theoretical analysis is provided for the communication complexity, memory, and the approximation guarantees of the algorithm for the k-medians problem for all k. The provided experiments complement the theoretical results.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Originality\n\nAlthough tree embedding-based methods are popularly used in distributed algorithms, this paper develops the first theoretical guarantees for the parallel hierarchical k-medians clustering problem using tree-based partitions. I believe a substantial amount of original work is needed in the analysis and developing correct tools to build the algorithm. \n\n# Quality\n\nThe writing and the presentation of the paper are good in general.  Motivations are discussed adequately and this result is placed well among the other related work. Detailed experiments provide a good understanding of how the algorithm works and its performance.\n\n# Clarity\n\nThe clarity of the paper for the most part is good. However, I have some clarifying questions.\n- In the abstract, the authors claim that \"for all k simultaneously the cost of the solution is at most $O(min (d, log n) \\log \\Delta \\log (\\Delta dn))$ factor bigger than the corresponding optimal solution\", however, if I have not mistaken, the provided theorem(theorem 4.1) only gives a result for every fixed k in expectation. Is the general result true with high probability? Can the authors clarify more on this?\n\n# Significance\n\nI believe the result presented in this paper carries a high level of significance given that it provides the first theoretical guarantees for parallel hierarchical k-medians and the approximation guarantees for the objective are not too far from the standard k-median++(which is a serial algorithm) guarantees. This algorithm also avoids the memory restrictions per node (here, only a small amount of memory is required) which was considered a key bottleneck in prior coreset based distributed algorithms for k-medians(needs to store at least k points per machine). In addition, the algorithm also matches the known round lower-bounds.\n\nOverall, I believe this paper adds very nice contributions.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Some potential limitations are discussed.\nThis paper focuses solely on the k-medians problem. Why this algorithm is specific to the k-medians objective and what is stopping one from using a similar technique for other k-clustering problems can be an important discussion to have.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "2-YUWcxeiAb", "reviewer": "Reviewer_zNbV", "summary": "The paper proposes algorithms for hierarchical k-median clustering. Besides my concern with its technical quality, I had a hard time following some of the statements/proofs in the paper.\n", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I am not too familiar with the recent advances of hierarchical clustering. I feel the authors should include some general introduction on how tree embedding is used here: What would be the main motivation for using the quad tree embedding technique needed here?  The paper mentions that the embedding from P will only incur a small distortion. Then what would be the benefit of using such embedding technique? How is it different from directly using Euclidean space metric? Is it because the assumption that the dataset P are sitting on integer grid {0, ..., \\Delta}^d? If so, what's the motivation behind this assumption?\n\nFor Theorem 3.2, the proof sketch argues that the cost can be decomposed as the cost of subtrees. I don't see how this is true for the k-median cost: for example, after finding the optimal (or near-optimal) solution for k=1; when k=2, shouldn't algorithm consider to move the first center as well? Can the authors provide more details on how the greedy algorithm work here?\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper does have a section discussing limitations: that is relies on a good tree embedding that can be computed fast.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "4hrs"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors present an algorithm for the distributed hierarchical k-median problem that requires only logarithmic memory on the machines, logarithmic rounds of communication, and has an O(d*log(n)) approximation factor for each k simultaneously. The approach taken combines tree embeddings with a careful parallelization of the clustering operations. The algorithm is of practical interest to the community, and the approach may lead to further innovation and efficient approaches to other clustering problems.
Decision: Accept (Poster)