Clustering using Approximate Nearest Neighbour Oracles
Authors: Enayat Ullah
Harry Lang
Raman Arora
Vladimir Braverman
Venue: Accepted by TMLR ()

Abstract: We study the problem of clustering data points in a streaming setting when one has access to the geometry of the space only via approximate nearest neighbour (ANN) oracles. In this setting, we present algorithms for streaming $O(1)$-approximate $k$-median clustering and its (streaming) coreset construction. In certain domains of interest, such as spaces with constant expansion, our algorithms improve upon the best-known runtime of both these problems.  Furthermore, our results extend to cost functions satisfying the approximate triangle inequality, which subsumes $k$-means clustering and $M$-estimators. Finally, we run experiments on Census1990 dataset wherein the results empirically support our theory.

Published in Transactions on Machine Learning Research (03/2023)
Clustering using Approximate Nearest Neighbour Oracles
Enayat Ullah
enayat edu
Department of Computer Science Johns Hopkins University
Harry Lang
hlang08@gmail..cm com
Unaffftiated
Raman Arora
aroraOcs.jher edu
Department of Computer Science Johns Hopkins University
Vladimir Braverman
vb21 @rice. edu
Department of Computer Science
Rice University
Reviewed on OpenReview: https: // // openeevee.. net/ net/ forum? id- TaRXy03CxX
Abstract
We study the problem of clustering data points a streaming setting when one has access to the geometry of the space only via approximate nearest neighbour (ANN) oracles. In this setting, we present algorithms for streaming a1)-aappre k-median clustering and its (streaming) coreset construction. In certain domains of interest, such as spaces with constant expansion, algorithms improve upon the best-known runtime of both these problems. Furthermore, our results exlend to cost functions satisfying the approximate triangle inequality, which subsumes k-means clustering and M-estimators. Finally, we run experiments on Census dataset wherein the results empirically support our thcory.
1 Introduction
In recent years, the streaming model of computation has become very popular for analyzing large datasets. In this model, the objective to compute some statistic or function of the dataset (eg: frequent items, norms, etc.), with access to data points sequentially. Moreover, only one or a few passes through the stream are allowed and the algorithm is permitted to use memory, sub-linear in the number of data points. A general technique is to compute and store succinct reprosentation, typically called sketch, of the points seen till given point in the stream and to update it efficiently upon seeing new point. A key challenge is to ensure that the size of the sketch is sub-linear in the number of data points. For more details, we refer the reader to Muthukrishnan et al. (2005); Babcock et al. (2002) for comprehensive surveys.
In this work, we are concerned with the problem of clustering over data steams using only approsimale mearest neighbour (ANN) search. Clustcring is a ubiquitous unsupervised data processing and exploratory technique wherein the high-level goal is to accumulate similar points together. Clustering and ANN search are two classical geometric problems which have been extensively studied and it is folklore that these two bear connections. We investigate this connection with the following questions: "Can we devise clustering algorithms with provable guarantees with access to the geometry of the space via only ANN queries"? Secondly, "are there (interesting) sellings wherein this yields an overall improved runlime compared to prior work
To this end, we present algorithms for k-median clustering which work with blackbox ANN oracle accesses. A related problem that of building coresets, which are small but representative sub-sample of the dataset such that it approximates the cost of every solution (see Section for formal definition). In this work,

---

Published in Transactions on Machine Learning Research (03/2023)
are concerned with building coresets with respect to the k-median clustering cost. For both these problems, our algorithms are simple and provably correct adaptations of known algorithms: Braverman et al. (2011) for streaming k-median clustering, and both Chen (2009) and Braverman et al. (2016) for its corcsct constructions, to the ANN oracle setting - we will call these Algorithm 1, Algorithm 2 and Algorithm 3 respectively. We furthermore instantiate these with specific ANN constructions, which aided by fast ANN search, give improvements in overall runtime. In practice, is observed that many point sets in high-dimensional ambient space usually have an intrinsic low-expansion structure. Motivated by this, there has been series of results studying ANN search in small expansion spaces (to be formalized later), for example (Beygelzimer& et al., 2006; Krauthgamer and Lee, 2004). We show that in these constant expansion spaces we get a striet improvement in terms of rumning time, of k-median clustering and its coreset construction. Specifically, with n points and k larget clusters, the runtime improves from O (nk log n) to O (n log(k (k log(n/)))) for both problems without affecting the space complexity. Moreover, in domains other than constant expansion spaces, popular methods like Locally Sensitive Hashing (LSH) (Indyk et al., 1997), when used as ANN oracles, can trade-off faster runtime for worse space complexity, in clustering.
We summarize our main contributions as follows.
We present algorithms for streaming k-median clustering and its coreset construction using only blackbox ANN oracle accesses.
2. Equipped with sub-linear time ANN search, this speeds up the overall runtime of streaming k- median clustering and its coreset construction. In particular, in spaces with constant expansion constant, the runtime improves from O(nk log(n)) to On log(k log(n/k)) without sacrificing the space complexity.
3. A minor and unrelated result is that we improve the space complexity of streaming k-median clus- lering algorithm of Braverman al. (2011) from O(k log(n)) to O(k log(n/k)) (with and without using ANN). We note that this improvement only manifests in certain restrictive regimes.
4. Our results extend to distance functions satisfying approximate triangle inequality, such as those used in k-means clustering, M-estimators etc.
1.1 Prior Work
The problems of k-median and k-means clustering have been widely studied. The rich history consists of algorithms with provable guarantees as well as heuristics which work well in practice. One popular such heuristic for k-means clustering, based on local search, is Lloyd's heuristic (Lloyd, 1982), which alternatively updates the cluster assignments and the cluster centers. However, it is easy to come up with arbitrarily bad examples for it. The first polynomial time algorithm which gives a constant approximation was given by Charikar et al. (1999), which was then improved by a line of work (Charikar and Guha, 2005; Jain and Vazirani, 2001; Arya et al., 2004). The first result for k-median clustering in the streaming setting was given by Guha et al. (2000) which achieves 0(2)/1) approximation using O(n") space. Meyerson (2001) introduced the related problem of Online Facility Location (OFL) which paved way for a stream of works on k-median clustering using OFL. In particular, Charikar et al. (1999) gave an algorithm that produces a (1) approximate solution using O(k n) space, subsequently improved to Okloog)) n) by Braverman et al. (2011). Another popular technique for the clustering problem is to construct. e-coresets of the dataset with respoct to the clustering cost. Herein, the idca is to extract a weighted set from the original set such that the cost of any k-median clustering on this set is close to that on the original set. The first coreset construction was given by Har-Peled and Mazumdar (2004) for k-median and k-means clustering which uses O(kcdd ((kk-1lo22de n) space. Subsequent works by Frahling and Sohler (2005); Chen (2009); Feldman and Langberg (2011); Braverman et al. (2016) improved upon the guarantees and also showed how to adapt the construction to the streaming setting.
We note that there are indood previous works which explore this connection between clustering and ANN search, however most of these are houristics which use ANN as an implementation detail (Deng and Zhao, 2017; Franti al., 2006). The most related to ours is that of Shindler et al. (2011), which as ours, builds
2

---

Published in Transactions on Machine Learning Research (03/2023)
upon the work of Braverman et al. (2011) for streaming k-median clustering. Their work addresses its application to real data sets, and one of the tricks they employ is ANN search, which they remark enjoys theoretical guarantees as well. However, they are primarily limited to only one such ANN method - random projections, which they use in their implementation. Morcover, they only give bounds in expectation, their runtime has an undesirable dependence on optimal cost, and suffer from a large unspecified constant in their approximation guarantec. On the other hand, our methods work with blackbox ANN oracles and we give high probability bounds with precise constants.
1.2 Overview of results
In this section, we state our results and discuss the key insights. The reader is encouraged to refer to section 2 to see exact definitions of the technical terms used. Our results are presented in a general setup wherein one has access to the geometry of the set via blackbox ANN oracles. Our theorems are therefore stated in terms of the update, query and space complexities of the ANN oracle/data structure, which are functions of its size (i.e. number of data points). We first state the theorem for streaming k-median clustering.
Theorem 1 (k-median clustering). Given an ANN oraele with q(-) query time, u(-) update time and s-)) space complezity, [O(1), ((1)),((1)-b))))) (11))
approzimate k-medion clustering solution can be computed on a stream of n points with probability at least 1 1/poly(n) while using s(k log(n/k)) space and with Ou(( log(n/k)) + q( log(n/k))) worst-case update time.
Even though the above theorem is stated for finding a bicriterion solution, we will, in section 3, show how to efficiently convert it into an (11)apprrxximate solution. In terms of runtime, our algorithms makes enaclly n calls to the ANN oracle for n points. We remark that this is optimal in terms of oracle complexity in our setting i.c when we have access to the goometry via ANN oracles. It easy to see as a single bad point can arbitrarily change the optimal clustering, and therefore we need to query at every point. Another (minor) implication of this theorem is separate (unrelated to ANN) result: we improve the space complexity for k-median clustering of Braverman et al. (2011) from Ol log(n)) to O(k (ollog()/k)) even without ANN oracles. A final remark is about computational complexity of k-median clustering. For n points and k clusters, the classic lower bound on runtime of any O(1) )approxiimeee randomized or deterministic algorithm is ((nk) (Guha et al., 2000; Mettu and Plaxton, 2004). However, this lower bound is established in a limited computational framework that counts the number of distance queries any algorithm necessarily needs to make. Our result indicates that it is quite pessimistic, as there are spaces that admit sub-linear time ANN scarch (like Euclidean spaces), which suffices for solving the problem of k-median clustering faster.
We now present our result on constructing e-coresets.
Theorem 2 (Coreset). Given an ANN oracle with q(-) query time, ul-) update time and s(-) space complexity, an 6-coreset for k-median can be compuled on a stream of n points with probability at least 1- 1/poly(( in Ou(( log(n))+ +q(k log(n))) worst-cas case update time and O(E log? + log(n))) space.
We adapt two coreset construction frameworks: Chen (2009) (Algorithm 2) and Braverman et al. (2016) (Algorithm 3), to the ANN setting. Equipped with fast ANN search, this similarly allows us to improve their runtimes. For the first, we adapt the ring construction of Chen (2009) to the ANN setting, and show that this approximation preserves the theoretical properties. For the second, we employ techniques from Braverman et al. (2016) which allows construction of coresets by importance sampling even when sampling probabilities can be overestimated. We essentially show how using ANN oracles can lead to controllable worsening of sampling probabilities, and still enable us to construct e-coresets. An important remark is that second framework uses the ((1) approximate k-median clustering algorithm of Braverman et al. (2011) as a crucial subroutine. Therefore our Algorithm 1 which adapts the k-median clustering algorithm of Braverman et al. (2011) to the ANN oracle setting is important to make the coreset construction Algorithm 3 wholly implementable using ANN oracles.
Applications. We discuss how specific ANN oracle instantiations manifest in overall runtime and space bounds Table gives the query complexity of varions ANN mothods, as well as space and time complexities when used for k-modian clustering and e-coresets. For coresct construction, for case of exposition, we only list. bounds obtained from adapting the algorithm of Braverman et al. (2016) (Algorithm 3), and omit Chen
3

---

Published in Transactions on Machine Learning Research (03/2023)
ANN method
Geometry of the set
q(m)- Query complexity
k-median clus- tering
e-coreset
Cover trees
Expansion
O 12 log m)
time
(n
((1log(k))
Constant r
space
O (og(kk))
O logg" (oggog())
Navigating Nets
Expansion
((1 log m
time
On k)
OOn k)
Constant t
space
Olggogn)/))
O k (eloo"(n) (n))
LSH
(R",4) ())
(2m
time
(ndvVk
O(nd K)
O + kd)
O 2 log n n(k" 3/2
+ kd))
space
LSII
llamming (30,1)% dd
time
(ndvk K)
O (T)
O + kd)
O(E *log n(k" 4/2
+ kd))
space
Data-
(RS,0) (2)
d(m'
time
O(ndk!/7)
OOdkk" "
depen-
-dent par-
space
O + kd)
O(e loo n(k 8/7
+ kd))
tition
Exhaustive
(X Any ((m)
time
Onk Ok (oggokk)))
O log()) - log log)(n))
Search
metric
space
space
Table 1: Runtime and space complexity using different ANN methods in various domains. The query complexity g(m) of ANN method is the time complexity compute ANN from candidates. For space partitioning methods (LSH and others), the query complexity is O (m=d),, where usually is poly(1/c), being the approximation factor of ANN. For example, in Euclidean space, we get e= 1/c2. For simplicity of presentation, we present the results with c=2, and give bounds in terms of and where = log(n//)) 1),k,, ke n.o...
(2009) 2). In the table, exhaustive search denotes the brute force nearest neighbour search method which serves as a baseline. Furthermore, we define the terms & and as k == k log(n/k), k= k log n, which are used in the table. We see that LSH based methods have faster runtimes but they have worse space complexity. On the other hand, in constant expansion spaces, cover trees and navigating nets give fast runtimes with the same space complexity, which establishes out claimed improvement in runtime.
2 Preliminaries and definitions
In this section, we formalize the problem and provide key definitions. Let (X' d) be a metric space, and let P C | n be the set of points observed in stream. Given integer E n), the desired number of clusters, the problem of k-median clustering asks for a set of points called cluster centers (or just centers) from X' such that the sum of distances of points in P to the nearest point in C is minimized; therefore it can be posed the following optimization problem.
min CC
min d(p,c) Σ
(k-median clustering)
eEC
PEP
For a fixed l and set of points P, let OPT(P,A) k) denote the cost incurred by the optimal selection of centers from P. related problem is Online Facility location (OFL), which is used in our algorithm.
Online Facility Location. Given a fixed facility cost f > O, the facility location problem relaxes the constraint of selecting exactly l centers to adding penalty cost. of per center to the total cost. Intuitively,
4

---

Published in Transactions on Machine Learning Research (03/2023)
the set of points P, called demands, are to be served via set of facilities such that the total cost of serving the demands via the nearest facility plus opening facilities is small. Service cost of point E P is the cost of serving this demand via the nearest facility, defined via its distance to the nearest facility. Therefore the total service cost is Σpep mingee d(p, c). Facility cost is the cost incurred in opening facilities; the total facility cost. = |c]f. Therefore, facility location problem can be formulated as min
C_x p min d(p, + [C] f.
min
eEC
The online variant of facility location, known as Online Facility Location (OFL) considers the problem of facility location in the streaming setting with the added constraint that once a point is assigned to particular facility, it cammot be changed in the future (even if we open a nearer facility). Moreover, once you designate a point as a facility, it remains a facility henceforth. Equivalently, the service and facility costs incurred while observing the stream are irrevocable.
o-metric Spaces and k-service clustering. The problem of k-service clustering generalizes the objective of k-median clustering to a-metric spaces, which are defined by relaxing the triangle inequality to what is called a-approximate triangle inequality (ATT): p(x, v) S o(p(z,, z) + p(z,8)) y)) V xr V, E X (see Appendix A for formal definitions). It can be posed as the following optimization problem.
min CC
min p(p, c) CEC
(k-service clustering)
PEP
We note that k-median and k-means clustering are special cases of the above (sce Appendix A). We now define some notions of approximations which are widely used for clustering problems.
Definition 1 (>-approximation). Let & N O. For the k-service clustering problem, X-approzimation is luple u) where C C X uu::. X + [0, oo] such that Σ min u(c)p(e,p) S XOPT(P,,)) & |C] = k. PErSEC
In the above, are tolerating a constant approximation to the optimal cost but returning set of exactly I centers. A bicriterion approximation, defined below, further also relaxes the constraint on the size of the set of centers from k to Okk).
Definition 2 ((A, biccittioonio approximation). Let & E N, 0 and < K < 1. A (A, -ibcriiertnio approzimation a tuple (C, u), C x & u X - [0, oo] such that EpEp mincec u(c)p(e,p) S XOPT(P, k) and CI S Kk
Coresets. We first give formal definition of an e-coreset, and then discuss some applications. A query space over X' is tuple (P, w. f, Q) where P C X, w P - [0, xo] is weight function, Q is the set of all possible queries, W the set of all possible weight functions, and f X' x W x Q oo].
Definition 3 (e-coreect). An c-coreset for the query space (P, f, Q) is a tuple (Z, u) where Z S X and u Z + [0, oo] are points and their corresponding weights respectively such that for every q E Q, we have (1-c) w. < f(Z, u) q) < (1+ w.
In the context of k-median clustering, a query is any set of k points i.e. any candidate solution of l centers. Informally, for given problem, coresets are small, succinct representations of the dataset such that the cost of any candidate solution on the coreset is close to that on the original set. Recently, coresets have been designed for various problems such as k-median clustering, M-estimation, Bayesian inference, in offline and streaming settings (Chen, 2009; Feldman and Langberg, 2011; Braverman et al., 2016; Huggins et al., 2016; Braverman et al., 2019). In this work, we are primarily concerned with the function being the k-median cost, but it can easily be extended to k-service cost. A useful property of coresets is that they are closed under operations like union and composition, formalized as Proposition 1 in Appendix A.
Approximate Nearest Neighbour Oracles. Approximate nearest neighbour search is a classical geo- metric problem concerning with the design of data structures and algorithms which support sub-linear time (in number of points) querics for ncarest neighbour scarch. We now define an approximate nearest neighbour oracle. more detailed discussion is provided in the appendix.
Definition 4 (Approximate Nearest Neighbour (c(8)-ANN) Oracle). For a given space X, a-ATI function P and set C C X, an algorithm A is c(N)-ANN Oracle if given query point x E X, it returns (y. p(x, v))
5

---

Published in Transactions on Machine Learning Research (03/2023)
where y C, such that with probability at least 1 1-6, 8, p(x, y) S c(6) mingee p(z, 2). The query, update and space complerity of ANN is denoted by 2(ICI), and s((C)) respectively.
Cover trees (Beygelzimer et al., 2006), Navigating Nets (Krauthgamer and Lee, 2004) and Locally Sensitive Hashing (LSH) (Indyk et al., 1997; Andoni et al., 2018) are some examples which can serve ANN oracle. A key quantity which these bounds depend on is expansion constant. Informally, the expansion constant of metric space is the largest factor by which the number of points in any ball increasos when we erpand a ball to be of twice the radius.
Definition 5 (Expansion constant T). (Beygelzimer et al., 2006) Let (S.p) be metric space. Fiz ony O, define Bp(p,r) r) = {x 2(p,z) S r) and (p,r)) = (p) ns. The Expansion Constant of set p) is defined as T, if T 2 2 the smallest number such that [B (r.
2r) = IB
for any r.
3 Streaming k-median Clustering
In this section, we discuss the algorithm for streaming k-median clustering (Algorithm 1) and skotch its analysis. We remind the reader that in the streaming model of computation, we observe data points one at a time, and the goal is to answer some pre-defined query on the whole stream. Our algorithm builds upon the algorithms of Charikar et al. (2003); Braverman et al. (2011) which uses OFL as subroutine. The algorithm in full is presented in Algorithm 1. The algorithm runs in phases, wherein each phase corresponds to a guess, say, L, of the lower bound to the optimal cost. OPT. After reading a new point, the algorithm computes its approximate nearest neighbour in the set of candidate facilities, and then either adds the point to the facility set or incurs a service cost line of Algorithm 1, where the notation if probobility(z) then y denotes the random event to take action y with probability I, by tossing a (Bernoull)) coin with bias If the guess is too low, either end up opening too many facilities or the service cost grows large. At this point, we trigger phase change where we increase our guess by a constant factor B, and do a soft reset. We empty the facility set and push its points to the start of the stream. If we keep incrementing the phase, at some point our guess to the lower bound exceeds the optimal cost OPT. We call this phase the critical phase. We show that upon setting the values of parameters appropriately, the algorithm processes the whole stream before the critical phase and returns constant approximate solution.
There are essentially three changes to the original algorithm of Braverman et al. (2011): line 7, line 13, and the value of the f. In line 7, we use ANN instead of exact nearest neighbour and in line 13 we change the condition from |C] > (7 - 1)k(1 + log(n)) to (7 - 1) + log(n/k)). These two changes independenily improve the runtime and space complexity of Braverman et al. (2011) respectively. The first improvement comes from faster runtime of ANN search compared to exact nearest neighbour computation, and the second comes from an improved analysis of Braverman et al. (2011).
Intermediate our analysis is the analysis of OFL with ANN oracles. As was shown in Meyerson (2001); Braverman et al. (2011) that the service cost and number of facilities is at most a constant times optimum (using distance oracles), we show that that same holds with ANN oracles. We formalize this in Theorem 3. Theorem (OFL.. Given an CNN)-ANN oracle with u(-) update, q(-) query and s(-) space complesity, OFL run on a stream of n points from an a-metric space with facility cost f T+logu/K where L S OPT incurs service cost al most (3c(5/An)a - (1 + log (t)) OPT and produces al most (1+66og(4/0))((//4n) a1) log (n/k)) facilities, with probability at least 1-8. The algorithm runs in O (n(g(klog(n//h) + log(n///o///ooooooooln/ kk))) time.
We now give the main theorem for Algorithm 1 with the proof in the appendix.
Theorem 4. Given a siream of n points P from an a-melric space (X, and a posilive integer k, Al- gorithm ezecuted with parameters set as B 202coFL + 2a and 7 max { (4o² .BKOFL + +1}, where COFL == (3c(6/An)a + - (1+ log (4))), kOFL == (1+ + 6log(4/0)c(//4)aa) returns a set C with aln |C|- = O (olo)()/)) such that COST(P,C) < 3-a (PT(P,k) with probability at least 1- - 5. The algorithm runs in time O (n(g(k log(n/k) + u(k log(n/k))) and uses space ((klog(n/k))
6

---

Published in Transactions on Machine Learning Research (03/2023)
Algorithm Streaming k-median clustering
1: Input: Integer & 2 1, stream P of points, a c(0)-approximate ANN Oracle
2: f- 1 w(p) < 1 for all points p
3: while solution not found do
4: C C COST
COST + f - [a/(k(1 + log(n/k)))
5:
while stream not ended do
6:
I + next point from the stream (v. v)) + ANN Oracle(2, C) if probability (min (min ( 1)) then Cu
7:
8:
9:
10:
else
11:
COST -- COST + w(x) p(a,y)
w(y) w(y) + w(x)
13:
if COST yL, or [C] (7 1)k(1 + log(n/k)) then
14:
Break and raise flag
15:
flag raised then Push facilities in C the start of stream
16:
17:
Li+1 + SLg, i t +
else Declare solution found
19:
Output: COST
Constant expansion spaces. An immediate corollary of the above result is obtained by using cover tree for fast ANN search in spaces of constant expansion, yielding faster runtime.
Corollary 1. Given a stream of n points P from an a-metric space () with constant expansion, and a positive önteger k, Algorithm 1 executed with cover tree data structure as the ANN oracle, and with parameters specified in Theorem returns set C with |C] = O (k (og(n/k)) such that COST(P,C) S 3-a OPT(PPK k) with probability al least - 8. The algoritlem runs in time O (n log (k log (n/k))) and uses space O log(n/k))
a3y
We remark that in the worst case, Algorithm 1 executes in O(log, OPT) phases. So the overall runtime has undesirable dependence OPT. Morcover, the size of the cluster set produced is Ö(k) and not exactly k. Below, we discuss how the algorithm can be provably tweaked to remove these discrepancies.
Extensions:
1. Improved runtime via routine from Lang (2017). To remove this dependence on OPT, Braver- man et al. (2011) proposed a pruning method, but it works only for average-case update time. Instead, we use the deterministic B(X, k) routine of Lang (2017), which not only gives worst case update time guarantee but also lakes advantage of the ANN setting. Given XX| = n points and a positive integer k. B(X, k) returns a weighted set of size [=**]] such that COST(X, Z) < 20PT(X, k). Incidentally, if the nearest neighbour graph of X is pre-computed, the runtime of B(X, k) is (n)) B(X,) is executed using c(5) ANN oracle, the Z returned satisfies COST(X, Z) S 2c())OPT(X, k) with probability at least 8 and runs in time After every phase change, take the union of the previous and new facilities K and call B(K, k) this set. Since in each phase, get O(klog(n/// is also O(k log(n/k)). In this way, bounds the number of phases by O(n/(k (k (ko))k/k)) Therefore, executing B(K, k) via ANN oracles, the total time is (n((((k (Ilog(n/k)) + ulk log(n/k)) (k)).
facilities, the number of facilities removed by B(K, k) ensured to read O(k (og(()/)))) new points at every phase, which
2. Extracting exactly i points. As pointed out before, Algorithm 1 produces O(k log(n/k)) clusters. To reduce it to exact k points, we can use any Random Access Machine (RAM) algorithm, for example Mettu and Plaxton (2004), on these set of points C. Let c, denote the constant approximation factor incurred by the RAM algorithm of Mettu and Plaxton (2004) which, on a set of points takes O(n?) time. The total runtime therefore increases by O(22 log(n/k)?), however in the regime when O(vn), we get the same overall runtime of (nngg(llog(n//1 + ulk (o)(n/k))). We state this below simple corollary.
7

---

Published in Transactions on Machine Learning Research (03/2023)
Corollary 2. Using Cr approzimate RAM algorithm after Algorithm 1 gives a set C of size k such that COST(P,C) < B-a (k (ol(nn/))) ) time and uses s(klog(nnk)) space.
adeec OPT(P,k) k) with probubility 2 1 11 The algorithm lakes ((((g(k log(n/k)++ul (og(///)
4 Building a Coreset
In this section, we show how two popular coreset construction algorithms, in particular, of Chen (2009) and Braverman et al. (2016), which have optimal runtime (using distance oracles), can be adapted to the ANN setting. Our results show that we still get improvements in the running time of these algorithms.
4.1 Coreset construction I (Algorithm 2)
Offline Coreset. We first discuss how the offline coreset construction algorithm of Chen (2009) can be adapted to the case when only ANN queries are allowed. The algorithm operates on a bicriterion solution obtained from some algorithm. We have already seen that Algorithm 1 gives us one such solution and using only ANN queries. Given 2 1, > 0, the goal is to construct a c-coreset of a set P n points. Let A 1={a,, a2, 3 be the (A, (ibeerrrtrnnrro solution which implies COST(A, P) S AOPT(P, k) and |A| S sk. The coreset construction adapted from Chen (2009) proceeds as follows.
1. Partitioning. The first step is to partition the space into rings. For every point p E P, find an ANN in the set A via an ANN-Oracle. This constructs partition of the space into m sets P1, P2, ... Pm,, where Pi is the set of points in P whose ANN returned in A is a; We now further partition each of these sets into concentric circles. To do this, we first define R := COST P)/Kn. Note that Rt S OPT k)/n, i.e. it is a lower bound on average cost. Let t = [log(ın)] the maximum number of concentric partitions we can have inside each P3. We use B(a, R) to denote a Euclidean ball of radius centred at a. We now define the rings Pej as,
Pia R) 28 29 21 j j= to
==0
Pg =
The main idea is that we can calculate the indices i and j approximately simply from the answer to the ANN query. In particular, if p and are the points and distance returned by ANN oracle respectively, then is the index of the point p in A, and j [log(A/R) - 17, and we get the ring construction.
2. Sampling. The second step is to sample points from these rings. Define 8 == s: [ (k log n + 4- For each partition P., if Pbll S 8, then we pick all its points and construct Sij- Otherwise, we draw 8 independent and identical samples from Ps to construct Siy. Furthermore, each of the points in Siz is assigned weight of [Psl//. We finally return S Sfj which we claim is a e-coreset of P, as stated in full in Theorem 5.
Theorem 5. The coreset construction of Chen (2009) run n points using c(ő) (NN oracle out- puts an e-coreset of size O log n) + log(1/5) log with probability 2 1-5. The space complerity is Okke 1) +logll log n + log(n/k))) and update time is Olg(k: (ogg/k))utt +u(logn))))))
Streaming Coreset. In recent years, merye and reduce has become a standard technique to convert offline coresets to the streaming setting. The idca is partition the stream into equal sized blocks, and then use an offline algorithm to construct coresets of these blocks. In our case, the modifed algorithm of (Chen, 2009) with ANN is used for the same. We then keep merging and reducing (in size) these coresets the stream progresses to get streaming coreset. The reader is encouraged to see Chen (2009) for details. The proof follows from the observation that coresets are closed under operations like set union and composition (see Proposition 1). We therefore obtain the following result.
Theorem 6. The coreset construction of Chen (2009) executed on a stream of n points using a c(6)- ANN oracle outputs an c-coreset with probability at least -8. The size of the coreset output O(ke 2 (I: log n)), total space complexity of the algorithm is O(ke 2kk n) log(n/k))) and the updote time of the algo- rithm is Oíg(k log n/k) + u(klog logn/k)).
8

---

Published in Transactions on Machine Learning Research (03/2023)
4.2 Coreset Construction II (Algorithm 3)
We now discuss how another streaming coreset construction technique Braverman et al. (2016) can also be adapted to work in the ANN setting. Given a candidate solution set C of k centers, for point p, the p(p.C) i. its distance to the nearest. center in C divided by sum sensitivity s(p) is defined 88, s(p) - E Emepp(ee)) P(g.))
of distances of all points to their nearest centers. At high-level, the framework presented in Braverman et al. (2016) works in two steps. In the first step, we compute a candidate solution and compute sensitivity of all the data points; in the second step, we sample with probabilities proportional to sensitivity. As in Braverman et al. (2016); we use the algorithm of Braverman et al. (2011) to compute the set C; however, in our setting, we use our adaptation with ANN oracles (Algorithm 1). The computational bottleneck is the step where we need to compute the sensitivities and we show how ANN oracles can accelerate it. We do not state the full algorithm due to space constraints and since it is essentially based on Algorithm 1. Line 8 of Algorithm 1 (page 11) in Braverman et al. (2016) involves computing the distance of the new point in the stream to the nearest point in the facility set. This step dominates in computation over all the other steps of the algorithm. We replace this by computing approximate nearest neighbour using an ANN oracle. This replaces the computational cost of O(CI) by ((CI) where C is the facility set. In the streaming setting, we have that the size of facility set C is Ol Olllog n). We now state the detailed statement for Theorem 7.
Theorem 7. Algorithm 1 of Braverman et al. (2016) ezecuted on a stream of n points using c(6)-ANN oracle (line 8) outputs e-coreset with probability at least 1 - 6. The size of the coreset is O log" n + s(k l)) and the update time of the algorithm is Ogg(k logn))))) n) + u(k log n)).
The key idea in the proof of Theorem 7, the details deferred to the appendix, is to show that the sensilivily computed using ANN orcale (denoted as s(p)) gets worsened only by a constant.
Lemma 1. Using ANN, the sensitivities are approzimated as s(p) S c())s(p) with probability 2 6
An important property established by Braverman et al. (2016) is that even if we overestimate sensitivity by a constant, sampling using this still gives us a e-coreset. Therefore, the correctness of our modified algorithm follows simply by invoking the above result. Plugging this in the result of Braverman et al. (2016) gives us that the size of the coreset is O(e -2k log" n s(k log n)) and the update time is (gg(klogn) + u(k n)).
5 Experiments
We run two experiments on USCensus1990 dataset (available at Frank and Asuncion (2010)) on 200,000 points in 68 dimensions. Tn the first. experiment (depicted in Figure Ia), we set the target number of clusters k = 1000 and evaluate the proposed method (Algorithm 1) with an ezact nearest neighbour search and three approximate NN search methods, namely cover trees", kd-trees and LSH We also compare against standard and highly-optimized implementations of three other clustering methods, Lloyd's, Gaussian mixture model and Elkan's, available in sklearn python library (Pedregosa et al., 2011). Figure 1a shows the average cost of clustering against time taken for these methods. We see that cover trees achiove the same cost as exact NN search, but takes much less time, even less than (highly optimized) sklearn methods, which produce lower cost clusters. On the other hand, ANN methods kd-tree and LSH do poorly on time taken and/or the cost of clustering. To investigate further, we evaluate how these methods fare for incrcasing values of k. In principle, ANN search methods are developed with the goal to give sublinear query time, once the data structure is built. In contrast, in our application, the data structure has to updated plentiful times, as the algorithm proceeds. Therefore, potentially the overhead of update time can overwhelm the benefits obtained from the sublinear query time. In Figure 1b, we observed that, as expected, the time for clustering with exact NN grows linearly with k, whereas the overall time taken by LSH grows super polynomially with k. On the other hand, the time for cover trees grows logartithmically with k as well as sklearn methods. However, the time for cover trees grow slower than sklearn methods and therefore is expected to perform even better in large(r) scale applications.
Source: http://gghhab.comm/mmmmm//////f 2 2Suurce: http:://wahkllleeooom///aaamalme
9

---

Published in Transactions on Machine Learning Research (03/2023)
Skiearri Lioycs
Sklearn
Skleam GMM
40000
Sklearn
Skleer Elkan
Sklearn
Exact NN
Exact NNI
Cover Trea ANN
12000
LSH1 ANN
Time (coes)
20000
8000
8000
20000
30000
40000
50000
50000
250
1000
1750
(a) Average cost clustering against clock time for 2 200000 points and & = 1000. We also try various values of hyper-parameter in the ANN constructions, like maximum depth in cover trees, marked in the same color, in the plot.
(b) Clock time against incrcasing valucs of target number of clusters k. We omit kd-trees here (but provide it in Figure in the appendix), as the time for kd-tress grows exponentially with k, thereby hiding the useful compar- isons otherwise.
6 Conclusion
We present algorithms for k-median clustering and coreset construction in the setting when only approximate nearest neighbour (ANN) search queries allowed. We show, using specific ANN instantiations, that this improves upon the total runtime of previous algorithms for these problems in certain domains such ones with constant expansion constant. We remark that our result can be extended to other clustering methods, for example k-means++. For the coreset construction part, we focus on algorithms of Chen (2009) and Braverman et al. (2016) since these have the optimal runtime, however as before, our results can extended to other frameworks like Feldman and Langborg (2011).
10

---

Published in Transactions on Machine Learning Research (03/2023)
References
Alexandr Andoni, Piotr Indyk, and Nya Razenshteyn. Approximate nearest neighbor search in high dimen- sions. arXic preprint orXiv:1806.09822 2018.
Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit. Local search heuristics for k-median and facility location problems. SIAM Journal compuling, 33(3): 544-562, 2004.
Brian Babcock, Shivnath Babu, Mayur Datar, Rajeev Motwani, and Jennifer Widom. Models and issues in data stream systems. In Proceedings of the twenty-first ACM SIGMOD- CIGMOD-SICACT-SICARR sympostum Principles of database systems, pages 1-16. ACM, 2002.
Jon Louis Bentley. Multidimensional binary search trees used for associative searching. Communicaatioss of the ACM, 18(9):509-517 -17, 1975.
Alina Beygekzimer Sham Kakade, and John Langford. Cover trees for nearest neighbor. In Proceedings of the 23rd international conference on Machine learning, pages 97 104. ACM, 2006.
Nitin Bhatia et al. Survey of nearest neighbor techniques. arXiv preprint or orx: 1007:000.0000 2010.
Vladimir Braverman, Adam Meyerson, Rafail Ostrovsky, Alan Roytman, Michael Shindler, and Brian Tagiku. Streaming k-means on well-clusterable data. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 26-40. Society for Industrial and Applied Mathematics, 2011.
Vladimir Braverman, Dan Feldman, and Harry Lang. New frameworks for offline and streaming coreset constructions. arXiv preprint Xr1: 008889, 2016.
Vladimir Braverman, Harry Lang, Enayat Ullah, and Samson Zhou. Improved algorithms for time decay streams. In Approzimation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM) 2019). Schloss Dagstuhh-eebiii-Zeetrnn fuer Informatik, 2019.
Moses Charikar and Sudipto Guha. Improved combinatorial algorithms for facility location problems. STAM Journal on Computing, 34(4):803 824, 2005.
Moses Charikar, Sudipto Guha, Éva Tardos, and David B Shmoys. A constant-factor approximation algo- rithm for the k-median problem. In Proceedings of the thirty-first annual ACM symposium on Theory of computing, pages 1-10. ACM, 1999.
Moses Charikar, Liadan O'Callaghan, and Rina Panigrahy. Better streaming algorithms for clustering prob- lems. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 30-39. ACM, 2003.
Ke Chen. On coresets for k-median and k-means clustering in metric and euclidean spaces and their appli- cations. STAM Journal on Computing, 39(3):923-94) 947, 2009.
Cheng-Hao Deng and Wan-Lei Zhao. Fast k-means based on knn graph. arXiv preprint arXin: 10:i:1005.000 705.01813, 2017.
Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. Tn Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 569 578, ACM, 2011.
Gereon Frahling and Christian Sohler. Corescts in dynamic geometric data streams. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 209-217. ACM, 2005.
Andrew Frank and Arthur Asuncion. Uci machine learning repository lhttp://archive. ics. uci. edu/ml]. irvine, ca: Universily of california. School of information and compuler science, 213:2 2, 2010.
Pasi Franti, Olli Virmajoki, and Ville Hautamaki. Fast agglomerative clustering using a k-nearest neighbor graph. IEFE transactions pattern analysis and machine intelligence, 28(11):1875-188 1881, 2006.
11

---

Published in Transactions on Machine Learning Research (03/2023)
Sudipto Guha, Nina Mishra, Rajeev Motwani, and Liadan O'Callaghan. Clustering data streams. In Foun- dations of computer science, 2000. proceedings. 41st annaul symposium on, pages 359-366. TEEE, 2000.
Sariel and Soham Mazumdar. On coresets for k-means and k-median clustering. In Proceedings of the thirty-sirth annual ACM symposium Theory of computing, pages 291-300. ACM, 2004.
Sariel Har-Peled, Piotr Indyk, and Rajeev Motwani. Approximate nearest neighbor: Towards removing the curse of dimensionality. Theory of computing, 8(1):321-33) 350, 2012.
Jonathan Huggins, Trevor Campbell, and Tamara. Broderick. Coresets for scalable bayesian logistic regres- sion. In Advances in Neural Information Processing Systems, pages 4080 4088, 2016.
Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: towards removing the curse of dimen- sionality. In Proceedings of the thirtieth annual ACM symposium Theory of computing, pages 604-613.
ACM, 1998.
Piotr Indyk, Rajeev Molwani, Prabhakar Raghavan, and Santosh Vempala. in multidimensional spaces. In Proceedings of the twenty-ninth onnual ACM sympostum on Theory of computing, pages 618 625, 1997.
hashing
Kamal Jain and Vijay V Vazirani. Approximation algorithms for metric facility location and k-median problems using the primal-dual scherna and lagrangian relaxation. Journal of the ACM (JACM), 48(2): 274 274-296, 2001.
Robert. Krauthgamer and James R Lee. Navigating nets: simple algorithms for proximily search. In Pro- ceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, pages 198-807. Society for Industrial and Applied Mathematics, 2004.
Harry Lang. Online facility location on semi-random streams. arXie preprint
2017.
Stuart Lloyd. Least squares quantization in pem. IEEE transactions on information theory, 28(2):129 137, 1982.
Ramgopal R Mettu and C Greg Plaxton. Optimal time bounds for approximate clustering, Machine Learning, 56(1-3):35 60, 2004.
Adam Meyerson. Online facility location. In Foundations of Computer Science, 2001. Proceedings. 4 42nd IEEE Symposium on, pages 426-431. IEEE, 2001.
Shanmugavelayutham Muthukrishnan et al. Data streams: Algorithms and applications. Foundations and Trends in Theoretical Computer Science, 1(2):117-236, 2005.
Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit-learn: Machine learning in python. Journal of machine learning research, 12(Oct):2825 2830, 2011.
Michael Shindler, Alex Wong, and Adam W Meyerson. Fast and accurate k-means for large datasets. Advances in neural information processing systems, pages 2375 2383, 2011.
12

---

Published in Transactions on Machine Learning Research (03/2023)
A Additional Preliminaries
We start with giving the definition of a semi-metric space called a-metric space which generalizes k-median clustering to k-service clustering. We first formally define a- A-Apoxxximate Triangle Inequality (a-ATI).
Definition 6 (a-Approximate Triangle Inequality (a-ATI)). A symmetric positive-defintte function X X X Rt satisfies a-ATI if V v, E X, p(a, 2) S a y) + p(y,2))
In the following claim, we show that p= d(- ) satisfies 2 ATTI, where d is a metric. Note that for 2, we get that d² used in k-means clustcring satisfies 2-ATI.
Claim 1. If (X, d) is metric space, then p= dp satisfies a-ATI, with a = 2
Proof. For any I, E, E X, we have,
p(x,2) = d dz, (x,2) 2) S (d(a,)) + +dyy, 2))
2" d(x, u) + dly, 2)
S 2" (d' (1, v) + d (y, 2)
= 20 2p(x)) + 2),
2
where the last incquality follows from Jensen's ' inequality.
We now define a-metric space.
Definition 7 (a-metric spaces). An a-metric space is tuplet (X, where X is set endowed with function p: X' x X + R+ which 4 z, V. E X' satisfies the following properties,
p(a, x)
p(z, y) = ply.2) σ)
3. p(x,1) v) S alp(z, 2) + p(z,v))
We now give an important property of coresets, called Merge and Reduce. Proposition 1. [Merge and Reduce] (Chen, 2009) Coresets satisfy the following two and properties
1. S 8 S2 are e-coresets of disjoint sets Pi 8 Pa respect., then S U.S. is a c-coreset of Pi U P2-
2. Tf S1 is c-coreset of S2 8 S2 is 8-coreset of Ss, then S₁ is ((1 c) 5) 1)-coresct of Sz.
A.1 Approximate Nearest Neighbor Oracles
The problem of nearest neighbour search is a classical geometric problem concerning with the design of data structures and algorithms which support queries for nearest neighbour search in various (metric) spaces. Nearest neighbour search has applications in diverse fields like data science, databases, computer vision etc (Bhatia et al., 2010). The typical motivation is to have query complexity better than an exhaustive search. Moreover, the problem is typically relaxed to return approcimate nearest neighbours, usually in the multiplicative sense. A major challenge to balance the tradeoff between (larger) space and (faster) query complexity.
We now review and discuss some results and techniques for approximate neighbour search in various domains. In terms of query complexity, with points in d dimensional space, we can characterize existing results into two mutually exclusive categories:
1. ANN in low dimensions (ANN-Id): poly(d) poly log(n)
2. ANN in high dimensions (ANN-hd): poly(d,n)
13

---

Published in Transactions on Machine Learning Research (03/2023)
where d is some notion of intrinsic dimensionality of the space, for example: expansion constant, doubling dimension etc. We remark that there might be algorithms which do not fall in the above stated categories but for the sake for brevity, we limit ourselves to only the above two. These examples serve to instantiate the framework and therefore a detailed discussion on them is unnecessary. The interested reader is encouraged to go through the referenced material.
ANN-Id. In low-dimension spaces, existing works on approximate nearest neighbour search typically use tree data structures to give algorithms with query times logarithmic in the number of points. Some examples which fall in this category are cover trees (Beygelzimer et al., 2006), navigating nets (Krauthgamer and Lee, 2004) etc. We restrict ourselves to only cover trees in this article. There are also hcuristics which work well in practice but their guarantees is the same as that of vanilla nearest neighbour search in the worst case. Some examples are k-d trees and ball trees (Bhatia et al., 2010; Bentley, 1975). To state the result of (Beygelzimer al., 2006), we first define expansion constant below.
Definition 8 (Expansion Constant т, (Beygelzimer et al., 2006)). The expansion constant of a set (S.p) is the smallest value of 2 such that [ (p. 2r) S T | (p. where (p, =
We now restate the result of Beygelzimer et al. (2006).
Thcorem 8 ([Beygelzimer et al., 2006)). Cover tree data structure is an (1 (1+ Cc--NN oracle which succeeds with probability 1. The query complexity is, g(n) = O (log A) + (1/6)0(1) u(n) = O (- log s(n) = O (n) where A is the aspect ratio of the set.
ANN-hd. We now discuss the other class of results which are designed with the consideration that the dimension is large. Our discussion is primarily drawn from survey by Andoni, Indyk and Razenshteyn (Andoni et al., 2018). In these methods, the approximate nearest neighbour search is generally reduced to its decision variant called approcimate near neighhour, defined below.
Definition 9 ((c, p, Approsisseee Near Neighbour). Given set of points P C X, build a data structure S such that given any query point q E X, such that P contains a point in Ba(g, p)) S returns a point from Ba(q, cp) with probability at least 1 1.
The reader is encouraged to look Har-Peled et al. (2012) to see the reduction of the approximate nearest neighbour problem to sequence of approximate near neighbour problems. We use (c, ANN oracle to refer to an oracle corresponding to the (c, p. A)-pproxieeate Near Neighbour problem. We now introduce Locally Sensilive Hashing, an idea central to the problem of approximate nearest neighbour search.
Locally Sensitive Hashing (LSH). Locally- hashing (Indyk and Motwani, 1998) is an instan- tiation of the technique of randomized space partitions. The idea is to come up with a distribution of hash maps such that a query point collides more with points nearby, but collides with only a few points which are far away. This formalized below.
Definition 10 (Locally-Sensitivv Hashing (Andoni et al., 2018)). For a metric space (X,d), scale p > 0, approzimation e > 1 and set P. Then a distribution H over maps h X + P is called (u, P1))) sensitive if the following holds for any 2.y E X
If d(z,,)) S μ then IP [h(x)) = h(v)] 2 P1
df v) > ey then P( h(v))] < p2
h
The distribution H. is called an LSH family and has quality v = v(H)) log(1/p1) log(1/p2)
We now restate theorem from Andoni et al. (2018) which formally describes how existence of an LSH family facilitates construction of ANN oracles.
Theorem (Andoni et al. (2018)). Suppose that a metric space (X, d) admits (n, cp, -2)-sssitttiee LSH family H with scale p. Moreover, suppose that the space required to store h(.)) is a and for a given x, E X, h(x) can be computed in time and d(z,y) be computed in O (T) time. Let e= e(H) log(1/p1) Then there
[og(1/ps)
exists and (c, 5) ANN Oracle with q(n) = 0
(n (og1////2 and space complexity = o
n n' +
no log1/p2"
P1
P1
14

---

Published in Transactions on Machine Learning Research (03/2023)
LSH is data-independent space partitioning approach. There are other approaches which constructs data structures based on partitions that depend on the dataset. These usually improve over the results obtained via LSH. Table 2, drawn from (Andoni et al., 2018), lists some results under various metrics and methods. The query and space complexity in each of these is O (n and O (n I + nd) respectively.
Metric
Type
Exponent
L/c
4
LSH
02 1/c o(1)
== 27 + ([)
Data-dependent hashing
2c-1 (1)
0 0 1/c²
l
LSH
0 -= 1/c² + o1)
0 0 - (11)
0 0= 26 (11
Data-dependent hashing
0 2
o(1)
Table 2: ANN search using LSH and data-dependent partitioning where is the constant in approximation
B Streaming k-median Clustering
We first give a thcorem for Online Facility Location (OFL) with approximate nearest neighbour oracles. The algorithm for k-service clustering (Algorithm 1) uses OFL a subroutine and therefore ils guarantees are crucially dependent on the guarantees of OFL. We restate the theorem.
Theorem 10. (Restatement of Theorem 3) Given an c(6)-ANN oracle with u(-) update, g(-) query and s(-) space complexity, OFL run on a stream of n points from an a-metric space with facility cost f = I+log where L S OPT gives an expected service cost of al most 3e (c 1)PPT and the eapected number of facililies produced is at most (3c(8)a + 1)k(1 + log (n/k)) conditioned
the randomness of the ANN oracle which succeeds with probability at least 1 - 8. Furthermore, with probability at least 1 8, the service cost is most (3c(6/4n)a + - (1 + log (1)) OPT and the number of facilities produced is at most (1 + (1 + (og(44/)c(0/4n)a)kkt log (n/k))) The algorithm runs in O (n(g(k (og(kk)))))))) ((kkoog(n/k)) time.
Proof. Let OPT K
min =
Evex
min p(z,y) be the optimal service cost and C be the set of facilities yeK
allocated by OPT. Let ct's denote the optimum k facilities, and Ct's denote the points allocated to of by OPT,
E [k). Let A = Euec; c() be the cost of region C₁ and at = A be its average cost. Let St be the
|Cp]
first ring around or which contains half the nearest points in C₁ Formally, S KIIK K,IK= CC,1/22
min Execy p(z, cf).
fI si might not be uniquely identifiable but for the sake of analysis, we only care about their existence. Let 1/= Enes: (T) be the cost of region S. For a point p, let P denote its optimal service cost and let Pp denote the service cost incurred by p by our algorithun. For region Z C Y. COST(2) denotes the service cost incurred by the points in region Z. Let COST denote the service cost incurred by our algorithm and C denote the set of facilities produced by our algorithm. Part and 2 of the theorem follows from Lemma 2 and 3 respectively.
The subsequent rings, S = f C. p(y. & p(x, of) V e s and | = 2
C.I We remark that
Lemma 2 (OFL | Bounds in Expectation). After observing n points in the stream, conditioned on the randomness of the ANN oracle, the expected service cost S (L+(((1))))PP and expected number of facilities < OPP where 8, is the failure probability of the ANN oracle.
Proof. We start with showing the bound on expected cost by analyzing two cases. We first look at the case wherein every region has facility. Consider region Se and let q be the facility opened in the region.
15

---

Published in Transactions on Machine Learning Research (03/2023)
For subsequent point p, in the worst case q is be the nearest facility and the service cost incurred is most c(51)p(p: 9) with probability at least 1 81- So we have Pp S c(1)aa (Pz + Pp) by a a-approximate
triangle inequality. By construction of P S o V z E sp+t. Summing over all the z in s we gel
A
Pg
Furthermore, summing over all the points p in S and doing union bound over the ANN
/ A s
)
oracle calls with failure probability ó1 for all points in Sy, we get COST(S!) c(5))a A/+
(( (Ar + + with probability at least 1-15 (6, Summing over j and doing a union bound over ANN oracle calls with failure probability ó, for all points C we get cost(C;) S 3c(8) )aA, with probability at least 1-107 Finally, summing over i's and doing a union bound over ANN oracle calls with failure probability 61 for all points in the stream, we get that ANN oracle succeeds with probability at least 1 - 51 for all points in the stream and the total (expected) cost after facilities opened in all the regions: cost S (c(6;))OPP) conditioned on the randomness of the ANN oracle.
The second case is when no region has a facility opened. For a region Sy the expected service cost incurred before a facility is opened S ʃ (See Fact 1, Lang (2017)). By Lemma 9, we have that for n points, and k facilitics, the total number of regions service cost before facilities opened is less than or equal to k (1 + log(n/k)) f.
less than or equal to &o (1 + log(n/k))). Hence the expected total
Combining the two cases above, expected total service cost - A(1 + log k )f + 3c(8))OOPT with probabil-
L
ity at least 1-n I
(1 + log(n/k)) and L S OPT, we get expected total service cost < (1+33(61))))0P))
We now look at the expected facility count. After k(1 + log facilities (one cach region); cach subscquent point p has probability of Pp to open new facility. Hence the expected number of facilities Exp Pp f
f
We already showed that E, Pp 3c(6)) Therefore, get E [number of facilities] < 3c(6))aOPT
0
f
We now present high probability versions the above bounds.
Lemma 3 (OFL. | High probability Bounds). After observing n points in the stream, with probabil- ity at least 1 - 5, COST (3c(5/4n) - (1 log (f)) OPT and the number of facilities is at most (1 6log(4/0)c(0/4n)jcl)) + log (n/k)).
Proof. We first look at the service cost. Let P(x, v] be the probability that given x regions which do not yet have a facility, the remaining service cost due to points in these regions arriving prior to the region having holds
facility is more than yf. Using induction, we show that P(z, y] S ====( The base case for y S - Now assume that it holds for xo and y yo If the first request in one of the facility-loss regions incurs a service cost of p 0, then
P [20 yol
p P
f PIzo-
[wo
1,
1
P
P(za you
P f
f
1-vo (=1)
- (vo (vo-P)( (o.r))
f 0
+ 1 -
f
n0 -vo
p
p f
Fe
+
1 -
117
117
ef
00 -v(((
16

---

Published in Transactions on Machine Learning Research (03/2023)
The last inequality follows because of + 1 9) elc-tyy
S 1 l < f. For the total mum-
ber of regions to be at most equal to &s 1 + log
(m)
and a failure probability of d2, we have (x) + +og (2 Hence cost is at most (/ f) S م (1+
k
ex c²-x(==)) = 82. Therefore, we get, = c-1 1: 1 + log
- kk 1 log (x)) log + ) - (OP + log
[1+1og log )=)) OPT with probability
at least - 82, when f k(1+lognn/8) We already proved a deterministic guarantee of at most 3c(8))oOPT with probability at least. - nói cost after all the regions have facilities. Combining it with the above bound via a union bound gives us that the total service cost is at most (3c(ā))a + - (1+ log ( )2) OPT with
probability at least 1 1- 1 62.
We now look at facility count. After 111 + logn) facilities (one in each region), each subsequent point p has probability of Pe to open a new facility. Hence the expected number of facilities = - Ep f
Pv Let A be the event that ANN oracle calls for all n points succeed with constant factor c(51). We know that this events occurs with probability at least 1 - 1 i.c. P[A] 2 1 nd1. Conditioned event A, we already showed in Lemma that EpPp S 3c(5))aOPT, Therefore μ S 3r(h JaOPT = Mu- Let the event B.- = {number of facilities 2 ())m) From Chernoff bound on Bernoulli trials, we have IP [B]]A]]= S exp 1aud ) S 8g. Solving for c, we get 2 (log(1/62) Therefore, conditioned on event A, the number Ma
of facilities S (Mu + (3log(1/62)mm) S pull log((1/)2) < (1 + 300((1/)))))(( (1+ log n2 OPT TT) L
L
when
with probability at least 1 82. Moreover, since P P[B.] 2 P[B.[A] P[A] Z
k 1 (1+10g " T.)
(1 - 16 - 82) 2 (noi + 62), therefore, combining the two cases, we have the number of facilities
n) OPT with probability at least 1 - (noj + 62). Setting 81 = 4 and 8 1 and using union bound over the above guarantees of cost and number of facilities finishes the proof.
I (1 +
(1+ log ) L
Theorem 11. (Restatement of Theorem 4) Given a set of n points P from an a-metric space (X) observed in a stream and positive integer k, Algorithm 1 executed with 3 20²coFL + 2a and 7 max (FI. BkoFL + +1}, where COPL == Bec(0/An)a+ - (1 + log (4)) KoFL := (1 + 6log(1/62)c(6io)) returns a set C with |C| = O (k log(n/k)) such that COST(P,C) S ag (PT(P,k) with probability at least 1 8. The algorithm runs in time O (n q(k log(n/k))) and takes space O (klog(n/k)))
R-a
Proof. From Theorem 3, we get that at every phase, OFL produces a bicriterion approximation to our problem with high probability. Note that COFL == (3c(5/4n) + ب (1 + log (+)) is the constant approximation factor of the service cost of OFL in the high probability bound. Similarly, KOFL = (1+ /3e(5/4n)a (oo(///))alloo(48)))) log(4/8)) such that OFT, opens at most koFLk (1 + logn) OPT facilities with high proba- bility.
We remind the reader that the algorithm proceeds in phases, wherein at each phase we guess lower bound to the optimal cost and start reading points from the stream. If the guess is too low, either end up opening too many facilities or the service cost grows large. At this point, we trigger a phase change and enter the next phase in the algorithm where we increase our guess to the lower bound by a constant factor of 3, and first read the already clustered points and then start reading the remaining ones. we keep incrementing the phase, at some point our guess to the lower bound exceeds the optimal cost. We call this phase the critical phose, formally defined as q = min (i: BL, > OPT). From Lemma 4, we have that with probability at least 1 - d, the am exits before or at the critical phase.
17

---

Published in Transactions on Machine Learning Research (03/2023)
For point X, let de denote its representative in phase Let j be the phase when æ first clustered. By a-ATI of we have,
b- , a' a c/)
plz,
Summing over all points a E X, with probability at least 8 of terminating before the critical phase, we have,
plcz b- c + +a- EE(x,
COST <
1=1
a'qla-i
I44
L <
a,57
OPT
where in the second equality we used the fact that the cost in phase i is upper bounded by L Note that our value of ensures < 3, so we can use the sum of an infinite geometric progression. In the third inequality, we used that L, = = the last inequality, we use L S OPT with probability at least since from Lemma we know that the algorithu terminates before or at the critical phase.
We show below that before the critical phase, the algorithm finishes and produces a bicreterion ap- proximate solution.
Lemma 4. With probability at least the success probability of online facility location, Algorithm terminates or before the critical phase.
(
a²
Proof. Let. X₁ be the stream in phase 1. We first show that cost of clustering X1 is S aOPT
L
Consider a point x E X. We remind the reader that of represents æ in phase Let be the phase which gets clustered the first time. Note that c' Vi <. Moreover, once gets clustered, gets represented by some point not necessarily er in all subsequent phases. Let ct, denote the optimal facility fro representation of x in phase i. We have that in phase 1, the optimal service cost of x is at most,
(,,1- , alplo, (, p(ct-1,2))
s cap(z,c))-))) 12) Σ
1- , d-itl)
1=2
- ((1
18

---

Published in Transactions on Machine Learning Research (03/2023)
where we used a-ATI of p to expand the cost incurred in phase I into the costs across previous phases. Let OPT, denote the optimal cost of clustering at phase i. Summing over all points x in the stream, we get
OPT, S
Σ Alc -.--1)
L-j p(c
S a Σ
L a La'
, (1)
+ +a
L-j
<OPT + Σ
+ +
1=2
< aPPT aay
Li
1=1
1-1
S aOPT + at
L
a² 3 - L
0PPT +
where the second and third incquality we used that the service cost in phase bounded by yh, and L fi.. Therefore, we see that we ensure that Li S OPT, we get constant approximate solution. Note that earlier defined, critical phase is the first phase which violates this. We now show that with high probability the algorithm terminates before at the critical phase. Let q be the critical phase, therefore Byg 2 OPT We have,
a²7
OPT, S aOPT +
Ing
3-a
aB + 3 -
a²²
Lig
By Theorem 3, we have that in phase 4 OFL guarantees a bicriterion approximate solution such that COST, I OPF,,PT, and the number facilities at most Bkori +1 (n/k)) OPT, We define == 2a 2orc + 2a,7 7 == max Co.L, + 1]. We therefore get
a²y
COST S COFL (a(2a" + 2a)) 2(202 + a))
Li
5y44
Moreover, the number of facilities is s BkoPL(1 + log (n/k)) OPT S (y- 1)k(1 + log(n/k)). Therefore, the algorithm doesn;t procoed to the next phase.
C Building a coreset
Theorem 12. (Reminder of Theorem 5) The coreset construction algorithm of Chen (2009) execuled on n points using c(5)-ANN oracle oulpuls a e-coresel with probability lenst 8. The size of the coreset output O (ke (kloggn + log(L/o) total space com- plerity (kk-=(kkoogm) + (og(1/5)log + s(k ((klog(n/k))) and the update time of the algorithm is O (g(klog + u(k logn/k)).
Proof. Lemma gives us the cost guarantoe. We now only need look at size and update times. The size of the coreset. is [S| ml.s O (2k log + log(1/5) (1))) logn). Note that if we use our algo-
19

---

Published in Transactions on Machine Learning Research (03/2023)
rithm to get the bicriterion solution, its size is O (k (log(n/))). Therefore the total space complexity is O (k n) + log(1 /6) logn + s(k log(n/k))) The update time also follows from the above.
Lemma 5. For all C Ç P such that |C| S k, with probability at least 1 - 6, we have
ICoST(C, COST(C, Se COST(C,))
Proof. For fixed C, from Lemma 6, with 5 2(2c(61)+1) and 82 > O, with probability at least -82, we gel,
[coST(C,P..) - COST(C,,
|s,l diam( $ 2(2c(61) 1)x
Moreover, from triangle inequality, have,
COST(C, P) COST(C,
COST(C, P..) - S.,,)
Σ
Pesl diam (P:s)
2(2c(61) + 1)K
For a point p E P.j.j 2 1, note that 2/ R S p(p. A) E c(6))((p, A) with probability at least 1 - 5,. Therefore, 2R < max(R, RR 2c(6)))(p, A)) _ R+ 1++2((1))ppp, A) for j 2 0. Taking a union bound over all points, we get that with probability at least nd1,
1 R Σ 137
Σ Σ (2c(6))p(p,.a) + R)
1. PEPS
Σ (2c(61))((, A) R)
PEP
(AST (A, P) + |
-20(T))OOST( A, P)+
S (2c(61) + (A, P)
S (2c(61) + 1)kOPT(P., k)
where the last inequality follows because R COST(A,P) OPT(P.k)
Moreover, diam(P.s) 2 2- We
AM
therefore get, with probability at least - noō, m. + 1)82,
ICOST(C, COsT(C,,
6
2(2c(61) + 1)xc $
2.(2c(61) + 1)xOPT(P,P) S cCOST(C, P)
Setting 81 = 8/8 and & n + 1), and noting that there can be n ways of selecting k points from P, we get that with probability at least 1 - 6, for all C' of size at most k;
|COST P) - CO,T(C, S) s cCOST(C,
Lemma 6. Let V be a a set of points from metric space (X, d) and let 8', > O. Let a set constructed by sampling s' = - log(2/8')1 points independently and identically from V, and each point is assigned weight VV. For fized set C X, the following holds with probability at least 8'
[COST(C, COST(C, U) V (VdiaV)(
20

---

Published in Transactions on Machine Learning Research (03/2023)
Proof in (Chen, 2009) which crucially uses Lemma 7 stated below.
Lemma 7. Let M 2 0 and n, be fixed constants and let h(-) be function defined set V such that M
SS h(v) 5 + M. Let be a set of z 28t log(2/6) samples drawn independently and identically from V. Let h(U) Euer h(u) and h(V) EvEv h(v). For > O, we then have,
MVVV [V
M(U) U
2 SA
Theorem 13. (Restatement of Theorem 6) Algorithm of Chen (2009) executed a stream of points using NNN) oracle (line 8) outpuls e-coreset with probability at least 1 - 8. The size of the coreset output is O (E log' n + s(k logn)) and the update time of the algorithm is O (q(k logn) + u(k l)g.)).
Proof. The proof is the same as that of merge and reduce in Chen (2009)
0
Theorem 14. (Restatement of Theorem 7) Algorithm 1 of Braverman et al. (2016) executed stream of n points using a c(6)-ANN oracle (line 8) outputs a e-coreset with probability at least 1 5. The size of the coresel. outpul is O Oc-22llog" n + s(k n)) and the update time of the algorithm is O (g(k n) + u(k n)).
Proof. We will show that using ANN oracle, the sensitivity of a point increases with at worse a constant factor.
Let p be the point observed in the stream and let s(p) denote its sensitivity computed using ANN oracle. We show in the following claim that this worsens the sensitivity by constant factor. In claim 8, show that s(p) z c(0) s(p) with probability 2-6.
We now carefully invoke the result of Braverman et al. (2016) that overestimating sensitivity by a constant factor still produces a e-coreset. In particular, we set probability failure of the oracle 8' as 8 = 6/2n and condition on the event that it succeeds for each point. This establishes that we get a e-coreset with probability least 8.
Since the ANN data structure takes s(k log m), the size of the coreset is O (c-2k log" s(k log where O (6 log² n) is the size coreset obtained by Braverman et al. (2016). The update time guarantee simply follows query and update time complexities of the ANN data structure.
Lemma The sensilivilies are upprocimated as 8(p) S c(6) s(p) with probubilily 2 1-
Proof. For point q, let a be its nearest neighbour C and let ā E be the point output by ANN oracle. Let C(q,C) denote the distance of g the point output by ANN oracle, ie. p(q.C) p(q. a). From the definition of ANN oracle, we have that p(g,a) a) S p(g,a) ā) S c()) a) with probability at least 1-8. 8. We use this to upper and lower bound the numerator and denominator of sensitivity follows.
plp,C) S <((0)
p(p,C)
8(p) = Eger C)..C) E
= c(8)s(p)
Eger p(g,C)
D Auxiliary results
Lemma 9. With n data points, k facilities, let e; denote the (optimal) facilities, C, the set of points assigned to facility e E [k]. Let S = fo E C, p(y,ca) I p(x, cx) & ply, v y E s and Vz E s Cal
and | Let the number of regions N { s v [M] A { Then,
(1 (1+log n) < N < & (1 log 11 (m))
21

---

Published in Transactions on Machine Learning Research (03/2023)
Proof. We proof by demonstrating when the two ends of the bound hold. The lower bound is attained if there is only 1 facility (or & facilities, but all the n points belong to only of them, and k k-1 has no points). The upper bound is attained when all the & facilities have equal number of points ie. n k.
E
Additional plots
60000
Skear Loydd
SK earn Elkan
Exact
Cover Tree ANN
40030
LSH ANN
Time
20000
200
400
600
800 1000
Figure The plot of time taken against target number of clusters with exact and three ANN methods (kd-tree included) and sklearn methods. As is apparent, the time taken for kd tree increases exponentially with where sklearn methods and cover tree grows sublinearly.
22


Reviews:
[{"review_id": "CnIDXnDR9s", "reviewer": "Reviewer_3X13", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths \n1. K-means and K-median clustering are fundamental and the setting considered here is interesting.\n2. The work provide a systematic study on the setting, and new algorithms with theoretical guarantees are provided.\n3. Non-trivial theoretical improvements are obtained for special cases. And the space complexity is also slightly improved.\n4. Preliminary experimental results are provided to support the theoretical findings.\n\nWeaknesses:\n1. The experimental studies are somewhat week.\n2. Most technical ingredients in the new algorithms follow ideas from previous literature, and I think the overall technical contribution is not significant.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considers streaming K-means and K-median clustering and focuses on the setting where the geometry can only be accessed via nearest neighbour oracles. O(1)-approximate algorithms are provided with time complexity depending on the efficiency of the underlying ANN oracle. For special cases when ANN is cheap, e.g., constant expansion space, the running time of the proposed algorithm is better than prior work. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. The experimental studies are somewhat week. Maybe more datasets should be used, and expansion constant should be empirically estimated.\n2. I think the space complexity of the algorithms are in terms of d-dimensional points. The author should be more explicit on the space complexity.\n3. I suggest the authors put existing bounds on streaming clustering in Table 1 as well, so that the reader can quickly compare the results from this submission to previous ones.\n4. Since the new algorithm gets improved results only for special cases, I suggest the authors add discussions on how often such special cases happen in real applications.", "broader_impact_concerns": "There is no concern on the ethical implications of the work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "AjSodTqaFA", "reviewer": "Reviewer_gXjA", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nS1. Clustering data points in a streaming setting is an important problem. \n\nS2. They provide theoretical analyses for the proposed algorithms, and the improvement regarding the runtime and space is convincing.\n\nS3. They conduct some experiments to validate the the runtime improvement of the proposed streaming k-median clustering method compared with previous algorithms. \n\nWeaknesses:\n\nW1. The authors claim that \"their results are presented in a general setup wherein one has access to the geometry of the set via blackbox ANN oracles.\" Nonetheless, I am not very sure whether this setting is general or not. It will be more convincing if the authors can provide some actual applications for demonstration. \n\nW2. They claim their results can be extended to other clustering methods (e.g., k-means) and M-estimators, but I fail to find more discussions in the later sections. Can they justify their claim with more discussion (and more experiments)?\n\nW3. I suppose the $k$-median clustering is a special case of $k$-service clustering with $\\alpha=1$ but not $\\alpha=2$, as the $k$-median clustering is with respect to 1-norm with $p=1$.\n\nW4. Definitions 1-4 could be improved by specifying the range of input parameters. \nFor example, for Definitions 1-3, it would be clearer to add $\\lambda > 1$, $\\kappa > 1$, and $0 < \\epsilon < 1$. \nMoreover, $z$ is not defined in Definition 1; I suppose it is a typo and should be replaced by $c$. \nIn Definition 3, $Z \\subseteq X$ should be $Z \\subseteq \\mathcal{X}$.\nIn Definition 4, $x \\in \\mathcal{C}$ should be $x \\in \\mathcal{X}$.\n\nW5. I appreciate they conduct the experiments for validation, but I still have several concerns as follows:\n\n(1) Using a single dataset (with low intrinsic dimensions) for performance validation might be incomplete and contain some bias. Can the authors consider at least one more datasets for a further demonstration?\n\n(2) They only validate Algorithm 1. Can they conduct more experiments to validate the improvement of Algorithms 2 and 3 for the coreset construction?\n\n(3) The analysis of the experimental results for the highly optimized clustering methods is missing. In Figure 1(b), why does the curve of Sklearn Elkan decrease from k=750 to k=1000?\n\nW6. The presentation can be further improved. Some typos are found as below:\n\n(1) \"... An important remark is that second framework using the $O(1)$ ...\" ==> \"... An important remark is that the second framework uses the $O(1)$ ...\" (In the paragraph after Theorem 2)\n\n(2) \"... in constant expansions paces...\" ==> \"... in constant expansions spaces...\" (In the **Applications** paragraph of Section 1)\n\n(3) $\\rho(x, y) \\leq \\alpha(\\rho(x_z), \\rho(z, y))$ ==> $\\rho(x, y) \\leq \\alpha(\\rho(x, z), \\rho(z, y))$ (In the **$\\alpha$-metric Spaces and $k$-service clustering** paragraph of Section 2).\n\n(4) \"we observe data points one at at time...\" ==> \"we observe data points one at a time...\" (In the 1st paragraph of Section 3)\n\n(5) \"The algorithm in full in presented in Algorithm 1...\" ==> \"The algorithm in full is presented in Algorithm 1...\" (In the 1st paragraph of Section 3)\n\n(6) \"We know discuss how another streaming coreset construction...\" ==> \"We now discuss how another streaming coreset construction...\" (In the 1st paragraph of Section 4.2)\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper, the authors investigate the clustering problem in a streaming setting when only approximate nearest neighbor (ANN) search queries are allowed. They present one improved algorithm for k-median clustering and two improved methods for coreset construction. They demonstrate that by using the ANN instantiations instead of the exhaustive linear scan, the time complexity of these three algorithms can be reduced without surrendering the space complexity. Moreover, for the streaming k-median clustering algorithm, the space complexity can be further reduced. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please answer the questions or fix the issues in W1-W6, especially W1, W2, and W5. ", "broader_impact_concerns": "No.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "9iUDMtiCEl", "reviewer": "Reviewer_cdYj", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nStrengths:\n + the exploration of streaming clustering algorithms to exploit fast ANN algorithms is an interesting direction, and establishing that these algorithms work is worth publication at TMLR.  \n\n + the analysis with constant expansion factor is an interesting and novel result.  The experiments with Cover Tree ANNs justify this analysis.  \n\n + the paper is mostly written clearly and accessibly (although a few comments/suggestions below).  \n\n\nWeaknesses:\n - the paper emphasize improvements from log(n) to log(n/k) inside various larger bounds.  These mostly do not provide any real improvement.  Note that O(log (n/k)) = O(log n) unless k = Omega(n / polylog(n)) or so.  In this case, any factor of k = Omega(n / polylog(n)) and then other algorithms that are O(n) or O(n^2) may be preferable.  \n \n - For instance before Corollary 1, the paper asks us to consider when k = O(sqrt{n}) and then states a runtime bound of O(n(q(k log(n/k) + u(k log(n/k)), but in this case the log(n/k) terms are O(log n).  \n\n - Theorem 6 also advertises an algorithm with space complexity that includes a term that is O(k^2 ... + s(k log (n/k)).  Since O(n) space is trivial, then this is only interesting when k = o(sqrt{n}) and hence the log(n/k) = O(log n).  \n\n\n - The claimed (in Intro) improved results for constant expansion constant are stated in the Introduction and probably implied in Table 1, but are not formally stated.  ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies the ability to create streaming coresets for k-median clustering (on n points) when the data can only (or efficiently) accessed via approximate nearest neighbor (ANN) queries.  I'm particular in spaces with \"constant expansion constant\" then a ANN which exploits that can reduce the runtime from O(nk log(n)) to O(n log(k log(n)).  \n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "  - remove discussion of improving log(n) -> log (n/k).  Its mostly (entirely?) not an improvement, and it makes the analysis unnecessarily more complicated.  \n \n  - Explain the claimed results for constant expansion constant more carefully, including carefully stating the ANN results for this case, and providing a theorem.  \n\nMore writing issues:\n  - p5,l3 : rho(x_z) -> rho(x,z)\n\n  - p8,l7 : \"distance ruined by ANN\" -> \"distance returned by ANN\"\n\n  - p8, l-9 : \"due to space constraints\" (there are not space constraints, but the other rational for not writing it out in full detail is sufficient).\n", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposed a streaming coreset construction for k-median clustering using approximate nearest neighbor (ANN) queries.  All reviewers agreed that the problem studied in this paper is interesting and important, and theoretical analysis for the proposed algorithms deserve to be published in TMLR.  We expect that the authors will address the following issues in the final version:

- State explicitly that the improvement on the space complexity manifests only in certain restrictive regimes.
- Add a theorem for the constant expansion setting.
- "Since the reported plot does not have confidence bars, we cannot conclude whether this decrease is statistically significant or not."   Please try to add confidence bars to your plots.
- Revise and add details of existing bounds in Table 1.
- Fix all typos and minor issues mentioned by the reviewers

AC
Decision: Accept (poster)