Wei Hu<EMAIL_ADDRESS>
Princeton University and Zhao Song<EMAIL_ADDRESS>
and Lin F. Yang<EMAIL_ADDRESS>
Princeton University and Peilin Zhong<EMAIL_ADDRESS>
Columbia University

# Nearly Optimal Dynamic $k$-Means Clustering
for High-Dimensional Data

###### Abstract

We consider the $k$-means clustering problem in the dynamic streaming setting,
where points from a discrete Euclidean space $\\{1,2,\ldots,\Delta\\}^{d}$ can
be dynamically inserted to or deleted from the dataset. For this problem, we
provide a one-pass coreset construction algorithm using space
$\widetilde{O}(k\cdot\operatorname{poly}(d,\log\Delta))$, where $k$ is the
target number of centers. To our knowledge, this is the first dynamic
geometric data stream algorithm for $k$-means using space polynomial in
dimension and nearly optimal (linear) in $k$.

###### keywords:

clustering, $k$-means, dynamic data streams, coreset

##  1 Introduction

Clustering is one of the central problems in unsupervised learning. The idea
is to partition data points into clusters in the hope that points in the same
cluster are similar to each other and points in different clusters are
dissimilar. One of the most important approaches to clustering is _$k$
-means_, which has been extensively studied for more than 60 years and has a
wide range of applications (see e.g. (Jain, 2010) for a survey). Given a set
of points $Q\subset\mathbb{R}^{d}$, the $k$-means problem asks for a set of
$k$ _centers_ $Z\subset\mathbb{R}^{d}$ such that the sum of squares of
distances between data points to their closest centers is minimized, i.e., it
tries to solve
$\min\limits_{Z\subset\mathbb{R}^{d},|Z|=k}\operatorname{cost}(Q,Z)$, where
$\operatorname{cost}(Q,Z)$ is a cost function defined as:

$\operatorname{cost}(Q,Z):=\sum_{q\in Q}\min_{z\in
Z}\operatorname{dist}^{2}(q,z).$

Here $\operatorname{dist}(\cdot,\cdot)$ stands for the Euclidean distance.

A major challenge in dealing with massive datasets is that the entire input
data can be too large to be stored. A standard model of study in such settings
is the _streaming_ model, where data points arrive and are processed one at a
time, and only a small amount of useful information (i.e., a _sketch_) about
the data is maintained. See (Muthukrishnan, 2005) for an introduction to the
streaming model.

In this paper we study the $k$-means problem over _dynamic data streams_
(Indyk, 2004), where data points from a discrete space
$\\{1,2,\ldots,\Delta\\}^{d}$ can be either inserted to or deleted from the
dataset. A standard approach to solving $k$-clustering problems like $k$-means
and $k$-median in the streaming setting is to maintain an _$\epsilon$
-coreset_, which is a small number of (weighted) points whose cost with
respect to any $k$ centers is a $(1+\epsilon)$-approximation to the cost of
the entire dataset on the same $k$ centers. As a consequence, at the end of
the stream, we only need to find an approximate $k$-means solution on the
coreset, which is automatically an approximate solution on the entire dataset.
Hence our goal is to design an efficient method to maintain an
$\epsilon$-coreset over a dynamic data stream using as small space as
possible.

###  1.1 Our Result

######  Theorem 1.1 (Main theorem, restatement of Theorem 4.2).

Let $\epsilon\in(0,1/2)$, $k,\Delta\in\mathbb{N}_{+}$, and $L=\log\Delta$. For
dynamic data stream consisting of insertions and deletions of points in
$[\Delta]^{d}$, there is an algorithm which uses a single pass over the stream
and on termination outputs a weighted set $S$ with a positive weight for each
point therein, such that with probability at least $0.9$, $S$ is an
$\epsilon$-coreset for $k$-means of size
$O(k\epsilon^{-2}d^{4}L^{2}\log(kdL))$. The algorithm uses
$\widetilde{O}(k)\cdot\operatorname{poly}(d,L,\epsilon^{-1})$ bits in the
worst case.

To our knowledge, this is the first algorithm for $k$-means in dynamic data
streams that uses space _polynomial in data dimension $d$_ and _nearly optimal
(linear) 111It is easy to see that $k$ points are needed in a coreset – when
there are only $k$ points in the dataset, the optimal $k$-means cost is $0$,
so a coreset has to contain all $k$ points. in the number of clusters $k$_.
Previous algorithms for streaming $k$-means either require space exponential
in $d$ or only work for insertion-only streams.222It is also possible to
obtain an $\widetilde{O}(k^{2}\cdot\operatorname{poly}(d))$ space algorithm
for dynamic streams by combining the techniques from (Chen, 2009) and
(Braverman et al., 2017). See Section 1.3 and Appendix C for detailed
discussions of previous results.

Note that for the $k$-means problem, Cohen et al. (2015) showed that one can
always do a random projection to reduce the dimension to $O(k/\epsilon^{2})$.
Thus, the most interesting setting would be when $d\leq O(k/\epsilon^{2})$ and
$d\gg\log k$.

###  1.2 Our Techniques

At a high level our algorithm is based on a framework called _sensitivity
sampling_ , which was proposed by Feldman and Langberg (2011). For a set
$Q\subseteq[\Delta]^{d}$, the _sensitivity_ of every point $q\in Q$ is defined
as

$s(q):=\max_{Z\subset\mathbb{R}^{d},|Z|=k}\frac{\operatorname{dist}^{2}(q,Z)}{\sum_{p\in
Q}\operatorname{dist}^{2}(p,Z)}.$

Namely, $s(q)$ represents how “sensitive” the cost can be to the removal of
point $q$. A crucial result shown by Feldman and Langberg (2011); Braverman et
al. (2016) is that once we know a good _upper bound_ on each point’s
sensitivity, there is a sampling method to construct an $\epsilon$-coreset.
Specifically, if we know an upper bound $s^{\prime}(q)\geq s(q)$ for each
$q\in Q$, we can sample $q$ with probability $s^{\prime}(q)/(\sum_{p\in
Q}s^{\prime}(p))$. Let $R$ be a set of i.i.d. samples from this procedure with
$|R|\geq\widetilde{\Omega}\left(\sum_{q\in
Q}s^{\prime}(q)/\epsilon^{2}\right)$, and each sample $q$ is assigned a weight
$\frac{\sum_{p\in Q}s^{\prime}(p)}{|R|s^{\prime}(q)}$. Then with high
probability $R$ is an $\epsilon$-coreset for $Q$. Note that if $\sum_{q\in
Q}s^{\prime}(q)=\widetilde{O}(k\cdot\operatorname{poly}(d))$, then an
$\widetilde{O}(k\cdot\operatorname{poly}(d))$-size $\epsilon$-coreset can be
constructed in this way. The formal description of this result is given in
Theorem 2.5.

We give an efficient method to obtain sensitivity upper bounds
$s^{\prime}(\cdot)$ such that: (i) $\sum_{q\in Q}s^{\prime}(q)$ is small, (ii)
we can implement the sensitivity sampling procedure in the dynamic streaming
setting. Then we are able to construct a coreset according to the previous
paragraph.

The key intuition in our sensitivity estimation is the following. Imagine that
there is a small region that is very dense, i.e., it contains a lot of points.
Then the sensitivity of every point in that region must be low, because that
point can be well represented by other points in the same small region.
Therefore, the problem of finding sensitivity upper bound for a point boils
down to figuring out the “right” region this point belongs to that can be
considered “dense.” Intuitively the sensitivity of this point depends on the
size of this dense region – the smaller the size, the smaller the sensitivity.

Figure 1: The grid structure over the point set. From top to bottom, three
levels of grids are shown. Each cell splits into $2^{d}$ cells in the next
level.

We make this intuition formal by using a hierarchical grid structure similar
to (Frahling and Sohler, 2005; Braverman et al., 2017). This structure is
illustrated in Figure 1. The top-level (level $0$) grid consists of cells that
are $d$-dimensional cubes of side-length $\Delta$, and each cell in level
$i-1$ splits into $2^{d}$ cells in level $i$. Each cell in level $i$ has side-
length $\Delta/2^{i}$. For a cell in level $i$, we say that it is _heavy_ if
it contains at least
$T_{i}=\Theta\left(\frac{d^{2}}{k}\cdot\frac{\operatorname{\mathsf{OPT}}}{(\Delta/2^{i})^{2}}\right)$
points in $Q$, where $\operatorname{\mathsf{OPT}}$ is the optimal cost of the
$k$-means problem.333We assume for now that we know
$\operatorname{\mathsf{OPT}}$. Our actual algorithm uses exponential search to
guess the value of $\operatorname{\mathsf{OPT}}$. Since $T_{i}>T_{i-1}$, we
know that if a cell in level $i$ is heavy, then its parent cell in level $i-1$
is heavy as well. Therefore the set of all heavy cells in all levels form a
tree. Now for a point $p\in Q$, denote by $c_{i}(p)$ the cell in level $i$
that contains $p$, and then define $j$ to be the smallest level index such
that $c_{j}(p)$ is not heavy; then we show an upper bound on the sensitivity
$s(p)$ solely based on this index number $j$, namely $s(p)\leq
s^{\prime}(p)=\Theta(d^{3}/T_{j})$. Furthermore, we prove that the sum of our
sensitivity upper bounds is small: $\sum_{p\in
Q}s^{\prime}(p)=O\left(kd^{3}\log\Delta\right)$, which satisfies our
requirement. To establish these bounds we need the total number of heavy cells
to be small, for which we apply a random shift of grid at the beginning, as
illustrated in Figure 2.

To implement the above sensitivity sampling method in the dynamic streaming
setting when the dataset is updated by insertions and deletions of points, the
key difficulties are: 1) we do not know the value of
$\operatorname{\mathsf{OPT}}$, and it changes when the underlying dataset is
updated; 2) we need to compute the sensitivity upper bounds and to sample
points at the same time using limited space.

Let us first assume $\operatorname{\mathsf{OPT}}$ is known and give an
algorithm to implement our sensitivity sampling procedure in the dynamic
streaming setting. Our algorithm makes crucial use of the _$k$ -set_ data
structure in (Ganguly, 2005) for counting _distinct elements_ in a dynamic
stream. The $k$-set data structure ensures that if the number of distinct
elements is at most some predetermined parameter, it will return all distinct
elements and their frequencies; otherwise it will return FAIL. We summarize
its guarantee in Lemma 4.1. Note that in order to implement sensitivity
sampling, we need to know which cells are heavy. Our algorithm dynamically
tracks all heavy cells, using the $k$-set structure as a building block. Then
the sensitivity sampling method has two stages: first sample a level $i$ (with
an appropriate probability for each level), and then uniformly sample a point
from all points associated with level $i$, i.e., all points $p$ such that
$c_{i}(p)$ is not heavy and $c_{i-1}(p)$ is heavy. (Note that for all points
associated with level $i$, they have the same sensitivity upper bounds, which
means uniformly sampling a point from them is enough.) In order to do uniform
sampling, we also maintain for each level $i$ a uniformly random subset of
points associated with $i$. Therefore it suffices to choose a point uniformly
at random from this subset once $i$ is chosen.

For the issue of not knowing $\operatorname{\mathsf{OPT}}$, we run in parallel
multiple copies of our sampling algorithm for different guesses of
$\operatorname{\mathsf{OPT}}$: $1,2,4\ldots,\Delta^{d}\cdot d\Delta$. Our
sampling algorithm ensures that when the guessed value is less than
$\operatorname{\mathsf{OPT}}$ but not too far away, the required space is
small. For other guesses, the required space might be a lot, but since we have
a space budget, our algorithm can return FAIL when the space runs out. Since
at least one guess is accurate, at least one copy of the algorithm will
succeed and output a small $\epsilon$-coreset.

Figure 2: Random shift of grid brings down the number of heavy cells. In the
left panel, we have a bad alignment of points and grids such that many cells
contain lots of points. In the right panel, after the random shift, only two
cells contain many points.

###  1.3 Related Work

It is well known that exactly solving $k$-means is NP-hard even for $k=2$ or
$d=2$ (Aloise et al., 2009; Mahajan et al., 2009). The most successful
algorithm used in practice is Lloyd’s algorithm, which is also known as “the”
$k$-means method (Lloyd, 1982). Because of the NP-hardness, various attempts
were made on approximation algorithms. Kanungo et al. (2002) proved that a
very simple local search heuristic achieves $(9+\epsilon)$-approximation in
polynomial time for any fixed $\epsilon>0$. When $d$ is a constant (Friggstad
et al., 2016; Cohen-Addad et al., 2016) or $k$ is a constant (Feldman et al.,
2007; Kumar et al., 2010; Feldman and Langberg, 2011),
$(1+\epsilon)$-approximation can be achieved in polynomial time.

There is a line of work studying $k$-means and $k$-median in insertion-only
streams, e.g., (Bentley and Saxe, 1980; Guha et al., 2000; Charikar et al.,
2003; Babcock et al., 2003; Agarwal et al., 2004; Har-Peled and Mazumdar,
2004; Har-Peled and Kushal, 2005; Chen, 2009; Feldman and Langberg, 2011;
Feldman and Schulman, 2012; Ackermann et al., 2012; Braverman et al., 2016).
There also have been a lot of interests in dynamic streaming algorithms for
other problems, e.g. (Bar-Yossef et al., 2002; Feigenbaum et al., 2005;
Baswana, 2008; Kelner and Levin, 2011; Ahn et al., 2012b, a; Goel et al.,
2012b, a; Ahn et al., 2012a; Baswana et al., 2012; Crouch et al., 2013; Ahn et
al., 2013; McGregor, 2014; Baswana et al., 2015; Bhattacharya et al., 2015;
Bernstein and Stein, 2016; Abraham et al., 2016a, b; Boutsidis et al., 2016;
Kapralov et al., 2017; Song et al., 2017a, b). In addition, $k$-means and
$k$-median were studied in various different settings, e.g., (Charikar et al.,
1998; Indyk and Price, 2011; Backurs et al., 2016; Bhattacharya et al., 2014;
Sohler and Woodruff, 2018).

The most relevant papers are (Frahling and Sohler, 2005; Feldman and Langberg,
2011; Braverman et al., 2016, 2017). Frahling and Sohler (2005) designed an
algorithm to maintain an $\epsilon$-coreset of size $k\epsilon^{-O(d)}$ for
$k$-means and $k$-median. Feldman and Langberg (2011) introduced the
sensitivity sampling framework for coreset construction, and their approach
was further improved by Braverman et al. (2016), but both of them only work
for insertion-only streams and do not apply to dynamic streams. Braverman et
al. (2017) focused on the $k$-median problem and constructed a coreset of size
$O(k\cdot\operatorname{poly}(d,\log\Delta))$ in the dynamic streaming setting,
but their technique heavily relies on $k$-median and cannot be extended to
$k$-means. In Appendix C we explain in detail the limitations of previous
approaches.

##  2 Preliminaries

#### Notation.

For $n\in\mathbb{N}_{+}$, let $[n]:=\\{1,2,\ldots,n\\}$. We define
$\widetilde{O}(f)$ to be $O\left(f\cdot\log^{O(1)}(f)\right)$. For any
$x\in\mathbb{R}_{\geq 0},\epsilon\in(0,1),$ we use $(1\pm\epsilon)\cdot x$ to
denote the interval $((1-\epsilon)\cdot x,(1+\epsilon)\cdot x)$. For any
$x\in\mathbb{R}$ and $a\in\mathbb{R}_{>0}$, $x\pm a$ denotes the interval
$(x-a,x+a)$.

We denote by $\operatorname{dist}(\cdot,\cdot)$ the Euclidean distance in
$\mathbb{R}^{d}$, i.e., for $p,q\in\mathbb{R}^{d}$,
$\operatorname{dist}(p,q):=\left\lVert p-q\right\rVert_{2}$. For sets
$P,Q\subseteq\mathbb{R}^{d}$ and a point $p\in\mathbb{R}^{d}$, we define
$\operatorname{dist}(p,Q)=\operatorname{dist}(Q,p):=\min_{q\in
Q}\operatorname{dist}(p,q)$ and $\operatorname{dist}(P,Q):=\min_{p\in P,q\in
Q}\operatorname{dist}(p,q).$ For any two sets $Q,Z\subseteq\mathbb{R}^{d}$, we
define $\operatorname{cost}(Q,Z):=\sum_{q\in Q}\operatorname{dist}^{2}(q,Z)$.
We define $\operatorname{diam}(Q)$ to be $Q$’s diameter, i.e.,
$\operatorname{diam}(Q):=\max_{p,q\in Q}\operatorname{dist}(p,q)$.

#### The dynamic streaming model.

We consider the _dynamic streaming model_ , defined below.

######  Definition 2.1 (Dynamic streaming model).

Let $Q\subseteq[\Delta]^{d}$ initially be an empty set. In the dynamic
streaming model, there is a stream of update operations such that the
$t^{\text{th}}$ operation has the form $(p_{t},\pm)$ which indicates that a
point $p_{t}\in[\Delta]^{d}$ is inserted to or deleted from the set $Q$, where
$+$ denotes insertion and $-$ denotes deletion. There is no invalid deletion
during the stream.444At any time during the stream, for any point
$p\in[\Delta]^{d}$, the number of deletions of $p$ so far is always no more
than the number of insertions of $p$. An algorithm is allowed a single pass
over the stream. At the end of the stream, the algorithm stores some
information regarding $Q$. The space complexity of an algorithm in this model
is defined as the total number of bits used by the algorithm during the
stream.

The goal of an algorithm in this model is to store some information which can
be used for a certain computation task, while using as small space as
possible. Although optimizing the running time is not required in this model,
the algorithm in the current paper is actually efficient for each update.

In this paper we suppose that any two points in $Q$ have different
locations555At the end of the stream, for any point $p\in[\Delta]^{d}$, the
number of insertions of $p$ is at most one more than the number of deletions
of $p$. , i.e., $Q$ is not a multiset. Our algorithm can be easily extended to
allow multiple copies of a point by blowing up the total space by an $O(\log
M)$ factor, where $M$ is an upper bound on the number of copies.

####  $k$-means clustering.

Now we introduce the _$k$ -means clustering problem_ and the notion of
_coreset_.

######  Definition 2.2 ($k$-means clustering).

Given a point set $Q\subseteq[\Delta]^{d}$ and a parameter
$k\in\mathbb{N}_{+}$ for the target number of centers, the goal of $k$-means
clustering is to find a set of $k$ points $Z\subseteq\mathbb{R}^{d}$ such that
the objective function, $\operatorname{cost}(Q,Z):=\sum_{q\in
Q}\operatorname{dist}^{2}(q,Z),$ is minimized. Each point in $Z$ is called a
_center_. $\operatorname{\mathsf{OPT}}$ is defined to be the optimal cost of
the $k$-means clustering problem.

However, solving the $k$-means problem exactly is NP-hard (Aloise et al.,
2009). Oftentimes, we only need a good approximation. For the purpose of
finding an approximate solution, an important concept is _coreset_ , which is
a small subset of (weighted) points whose $k$-means solution is a good
approximate solution for the entire dataset. The formal definition is the
following:

######  Definition 2.3 (Coreset for $k$-means).

Given $Q\subseteq[\Delta]^{d}$, $k\in\mathbb{N}_{+}$ and $\epsilon>0$, a set
of point-weight pairs
$S=\\{(s_{1},w_{1}),(s_{2},w_{2}),\ldots,(s_{m},w_{m})\\}\subset[\Delta]^{d}\times\mathbb{R}_{>0}$
is an _$\epsilon$ -coreset_ for $Q$, where $w_{i}$ is the weight of $s_{i}$,
if $S$ satisfies

$\forall
Z\subset\mathbb{R}^{d},|Z|=k:\big{|}\operatorname{cost}(S,Z)-\operatorname{cost}(Q,Z)\big{|}\leq\epsilon\cdot\operatorname{cost}(Q,Z),$

where
$\operatorname{cost}(S,Z):=\sum_{i=1}^{m}w_{i}\operatorname{dist}^{2}(s_{i},Z).$
The size of the coreset is $|S|$.

The main problem studied in this paper is how to construct a small coreset for
$k$-means over a dynamic data stream. The formal description is the following.

######  Definition 2.4 (Coreset for $k$-means over a dynamic stream).

Given a point set $Q\subseteq[\Delta]^{d}$ described by a dynamic stream of
operations (Definition 2.1), a parameter $k\in\mathbb{N}_{+}$ for the target
number of centers, and an error parameter $\epsilon\in(0,0.5)$. The goal is to
design an algorithm in the dynamic streaming model which can with probability
at least $0.9$ output a small size $k$-means $\epsilon$-coreset (Definition
2.3) for $Q$ using as small space as possible.

#### Sensitivity sampling based coreset construction.

Let us briefly review the coreset construction framework proposed by Feldman
and Langberg (2011); Braverman et al. (2016). Given $Q\subseteq[\Delta]^{d}$
and $k\in\mathbb{N}_{+}$, the _sensitivity_ of a point $p\in Q$ is defined as:

$\displaystyle
s(p)=\max_{Z\in\mathbb{R}^{d},|Z|=k}\frac{\operatorname{dist}^{2}(p,Z)}{\sum_{q\in
Q}\operatorname{dist}^{2}(q,Z)}.$

The following theorem gives guarantee of a sensitivity sampling based coreset
construction.

######  Theorem 2.5 (Feldman and Langberg (2011); Braverman et al. (2016)).

Given a set of points $Q\subseteq[\Delta]^{d}$ and a parameter $k$, let $s(p)$
denote the sensitivity of each point $p\in Q$. For each $p\in Q$, let
$s^{\prime}(p)$ be an upper bound on the sensitivity of $p$, i.e.,
$s^{\prime}(p)\geq s(p)$, and let $t^{\prime}=\sum_{p\in Q}s^{\prime}(p).$
Consider a multiset $S$ of $m$ i.i.d. samples from $Q$, where each sample
chooses $p\in Q$ with probability $s^{\prime}(p)/t^{\prime}$. For each sampled
point $p$, a weight $w(p)\in(1\pm\epsilon/2)\cdot t^{\prime}/(ms^{\prime}(p))$
is associated with $p$. If $m\geq\Omega(t^{\prime}\epsilon^{-2}(\log|Q|\log
t^{\prime}+\log(1/\delta)))$, then with probability at least $1-\delta$,
$\\{(p,w(p))\mid p\in S\\}$ is an $\epsilon$-coreset (Definition 2.3) for $Q$.

According to the above theorem, if we can find a good sensitivity upper bound
$s^{\prime}(p)$ for each point $p$, then we are able to construct a coreset
with size nearly linear in $t^{\prime}=\sum_{p}s^{\prime}(p)$. In section 3,
we give an offline algorithm which can estimate a good sensitivity upper bound
for each point, which readily implies an efficient offline coreset
construction algorithm. In section 4, we show how to implement this
sensitivity sampling procedure over a dynamic stream. Notice that Braverman et
al. (2016) gave a sensitivity sampling framework that works for clustering
with general loss functions, and our method can be extended to those problems
as well.

##  3 An Offline Sensitivity Sampling Procedure

In this section, we consider the _offline_ setting in which all the data
points are given. In this setting, we design a coreset construction algorithm
based on sensitivity sampling. In Section 4, we will show how to implement
this algorithm in the dynamic streaming setting.

###  3.1 Randomly Shifted Grids

We consider data points from $[\Delta]^{d}$ and assume without loss of
generality that $\Delta=2^{L}$ for some positive integer $L$. The space
$[\Delta]^{d}$ is partitioned by a hierarchical grid structure as follows. The
first level (level $0$) of the grid contains _cells_ with side-length $\Delta$
such that all the data points are contained in a single cell. For each higher
level, we refine the grid by splitting each cell into $2^{d}$ equal sized sub-
cells. In the finest level, i.e., the $L$-th level, each cell contains a
single point. We further randomly shift the boundary of the grids to achieve
certain properties, which we will show later. Formally, our grid structure is
defined as the following.

######  Definition 3.1 (Grids and cells).

Let $g_{0}=\Delta$. Choose a vector $v$ uniformly at random from
$[0,\Delta]^{d}$. Partition the space $\mathbb{R}^{d}$ into a regular
Cartesian grid $G_{0}$ with side-length $g_{0}$ and translate $G_{0}$ such
that a vertex of this grid falls on $v$. The grid $G_{0}$ can be regarded as
an infinite set of disjoint _cells_ , where each cell $C\in G_{0}$ can be
expressed as

$\displaystyle[v_{1}+n_{1}g_{0},\
v_{1}+(n_{1}+1)g_{0})\times\cdots\times[v_{d}+n_{d}g_{0},\
v_{d}+(n_{d}+1)g_{0})\subset\mathbb{R}^{d}$

for some $(n_{1},n_{2},\ldots,n_{d})\in\mathbb{Z}^{d}$. (Note that each cell
is a Cartesian product of intervals.)

For $i\geq 1$, we define the regular grid $G_{i}$ as the grid with side-length
$g_{i}=g_{0}/2^{i}$ aligned such that each cell in $G_{i-1}$ contains $2^{d}$
cells in $G_{i}$. The finest grid is $G_{L}$ where $L=\log_{2}\Delta$. A cell
of $G_{L}$ has side-length $1$ and thus contains at most one data point.

For convenience, we also define $G_{-1}$ to be the regular grid with side-
length $g_{-1}=2\Delta$, and each cell in $G_{-1}$ is a union of $2^{d}$ cells
in $G_{0}$. Since the data points are in $[\Delta]^{d}$, there must be a
single cell in $G_{-1}$ which contains all the data points. Consider two cells
$C\in G_{i}$ and $C^{\prime}\in G_{j}$ for some $i,j\in\\{-1,0,1,\ldots,L\\}$.
If $C^{\prime}\subset C$, then $C$ is an _ancestor_ of $C^{\prime}$.
Furthermore, if $i=j-1,$ then $C$ is the _parent_ of $C^{\prime}$ and
$C^{\prime}$ is a _child_ of $C$. Thus every cell which is not from $G_{L}$
has exactly $2^{d}$ children cells. For a point $p$ (or a set $P$ of points),
$c_{i}(p)$ (or $c_{i}(P)$) denotes the cell $C$ in grid $G_{i}$ which contains
$p$ (or $P$). If $i$ is clear from the context, we will just use $c(p)$ (or
$c(P)$) for short.

###  3.2 Sensitivity Estimation and Coreset Construction

In Algorithm 1 we describe how to assign a sensitivity upper bound for every
point. It needs an estimate $o$ of the optimal $k$-means cost
$\operatorname{\mathsf{OPT}}$. We will show how to enumerate the guesses $o$
later. According to Theorem 2.5, it directly gives an offline coreset
construction algorithm.

1: predetermined: a guess $o\in[1,\Delta^{d}\cdot d\Delta]$ of the optimal
$k$-means cost $\operatorname{\mathsf{OPT}}$

2: input: a point set $Q\subseteq[\Delta]^{d}$, a parameter
$k\in\mathbb{N}_{+}$

3: Impose randomly shifted grids $G_{-1},G_{0},G_{1},\ldots,G_{L}$ (Definition
3.1).

4: Let $C\in G_{-1}$ be the cell which contains $Q$, i.e., $C=c(Q)$. Mark $C$
as _heavy_.

5: for $i:=0\rightarrow L-1$ do

6: Set the threshold value $T_{i}(o)=(d/g_{i})^{2}\cdot o/k\cdot 1/100$.

7: for $C\in G_{i}$ with $C\cap Q\not=\emptyset$ do

8: Let $z$ be an estimated value of $|C\cap Q|$ up to some precision.

9: If $z\geq T_{i}(o)$, mark $C$ as heavy.

10: Otherwise, if all the ancestors of $C$ are marked as heavy, mark $C$ as
_crucial_.

11: end for

12: end for

13: For $C\in G_{L}$, if all the ancestors of $C$ are marked as heavy, mark
$C$ as crucial.

14: Initialize $Q_{0}=Q_{1}=\cdots=Q_{L}=\emptyset$.

15: For $p\in Q,$ if $c_{i}(p)$ is marked as crucial, add $p$ into set $Q_{i}$
and set $s^{\prime}(p)=10d^{3}/T_{i}(o)$.

16: output: $Q_{0},Q_{1},\ldots,Q_{L}$ and $s^{\prime}(\cdot)$

Algorithm 1 Sensitivity Estimation

We also give an alternative sampling procedure in Algorithm 2 which is useful
for the dynamic streaming model.

1: predetermined: a guess $o$ of the optimal $k$-means cost
$\operatorname{\mathsf{OPT}}$, an error parameter $\epsilon\in(0,0.5)$

2: input: a point set $Q\subset[\Delta]^{d}$, a parameter $k\in\mathbb{N}_{+}$

3: Let $Q_{0},Q_{1},\ldots,Q_{L}$ and $s^{\prime}(\cdot)$ be the output of
Algorithm 1.

4: Let $\widehat{q}_{0},\widehat{q}_{1},\ldots,\widehat{q}_{L}$ be the
estimated values of $|Q_{0}|,|Q_{1}|,\ldots,|Q_{L}|$ respectively.

5: For $i\in\\{0,1,\ldots,L\\},$ set $T_{i}(o)=(d/g_{i})^{2}\cdot o/k\cdot
1/100$ (same as in Algorithm 1).

6: Set $\gamma=\epsilon/(40^{2}Ld^{3})$.

7: Let $I=\\{i\mid 0\leq i\leq L,\widehat{q}_{i}\geq\gamma T_{i}(o)\\}$.

8: Let $Q^{I}=\bigcup_{i\in I}Q_{i}$. $\triangleright$ Only consider the
levels with sufficient number of points.

9: Set $t^{\prime}=\sum_{i\in I}\widehat{q}_{i}\cdot 10d^{3}/T_{i}(o)$.
$\triangleright$ Total estimated sensitivities.

10: Set $m=\Theta(t^{\prime}\epsilon^{-2}Ld\log t^{\prime})$ and initialize
$S=\emptyset$. $\triangleright$ $m$ is the total number of samples.

11: for $j=1\rightarrow m$ do

12: Choose a random level $i\in I$ with probability $(\widehat{q}_{i}\cdot
10d^{3}/T_{i}(o))/t^{\prime}$.

13: Uniformly sample a point $p$ from $Q_{i}$.

14: Add $(p,t^{\prime}/(ms^{\prime}(p)))$ to set $S$.

15: end for

16: output: the set $S$

Algorithm 2 Sensitivity Sampling Based Coreset Construction

######  Theorem 3.2.

Suppose that for any $i\in\\{0,1,\ldots,L\\}$ and for any cell $C\in G_{i}$
with $C\cap Q\not=\emptyset$, the estimated value $z$ in line 8 of Algorithm 1
satisfies either $z\in|C\cap Q|\pm 0.1T_{i}(o)$ or $z\in(1\pm 0.01)\cdot|C\cap
Q|$, and for any $Q_{i}$, the estimated value $\widehat{q}_{i}$ in line 4 of
Algorithm 2 satisfies either $\widehat{q}_{i}\in|Q_{i}|\pm 0.1\epsilon\gamma
T_{i}(o)$ or $\widehat{q}_{i}\in(1\pm 0.01\epsilon)\cdot|Q_{i}|$. Suppose
$o\in(0,\operatorname{\mathsf{OPT}}]$. Then the set $S$ output by Algorithm 2
is an $\epsilon$-coreset (Definition 2.3) for $Q$. Furthermore, with
probability at least $0.93$, $|S|$ is at most
$O(k\epsilon^{-2}d^{4}L^{2}\log(kdL)\cdot(\operatorname{\mathsf{OPT}}/o+1))$.

###  3.3 Analysis

Now we give the proof of Theorem 3.2. All the missing proofs in this section
are given in Appendix A. Let us first state some simple facts.

######  Fact 1.

The point sets $Q_{0},Q_{1},\ldots,Q_{L}$ obtained by Algorithm 1 form a
partition of $Q$, i.e., for all $p\in Q,$ there is exactly one
$i\in\\{0,1,\ldots,L\\}$ such that $p\in Q_{i}$.

######  Fact 2.

For $C\in G_{i}$, if $C$ is marked as heavy, then $|C\cap Q|\geq 0.9T_{i}(o)$;
otherwise $|C\cap Q|\leq 1.1T_{i}(o)$. Similarly, if $i\in I$, then
$|Q_{i}|\geq 0.9\gamma T_{i}(o)$; otherwise $|Q_{i}|\leq 1.1\gamma T_{i}(o)$.

######  Fact 3.

For $Q_{i}$ output by Algorithm 1, every point $p\in Q_{i}$ is assigned the
same sensitivity upper bound $s^{\prime}(p)=10d^{3}/T_{i}(o)$.

In line 7 of Algorithm 2, we set $I$ to be the set of levels such that there
are sufficient number of points in the crucial cells in those levels. The
following lemma shows that the point set $Q^{I}$ (line 8 of Algorithm 2) is a
good representative of the point set $Q$, i.e., for any set of $k$ centers
$Z$, the $k$-means cost $\operatorname{cost}(Q,Z)$ is close to the
$\operatorname{cost}(Q^{I},Z)$.

######  Lemma 3.3.

Let $Q^{I}$ and $\epsilon$ be the same as in Algorithm 2. If
$o\in(0,\operatorname{\mathsf{OPT}}]$, then for any $Z\subseteq\mathbb{R}^{d}$
with $|Z|=k$, we have:
$\operatorname{cost}(Q^{I},Z)\leq\operatorname{cost}(Q,Z)\leq(1+\epsilon/10)\operatorname{cost}(Q^{I},Z).$

Next, instead of showing $s^{\prime}(p)$ (output by Algorithm 1) is a
sensitivity upper bound with respect ot $Q$, we show that $s^{\prime}(p)$ is
also an sensitivity upper bound with respect to $Q^{I}$. This is even stronger
since $Q^{I}$ is a subset of $Q$ and we have:

$\displaystyle\forall Z\subseteq\mathbb{R}^{d}:|Z|=k,\
\frac{\operatorname{dist}^{2}(p,Z)}{\sum_{q\in
Q}\operatorname{dist}^{2}(q,Z)}\leq\frac{\operatorname{dist}^{2}(p,Z)}{\sum_{q\in
Q^{I}}\operatorname{dist}^{2}(q,Z)}.$

######  Lemma 3.4.

Let $Q^{I}$ be the same as in Algorithm 2. If
$o\in(0,\operatorname{\mathsf{OPT}}]$, then for all $i\in\\{0,1,2,\ldots,L\\}$
and $p\in Q_{i}$, we have:

$\displaystyle\max_{Z\subseteq\mathbb{R}^{d}:|Z|=k}\frac{\operatorname{dist}^{2}(p,Z)}{\sum_{q\in
Q^{I}}\operatorname{dist}^{2}(q,Z)}\leq
10\frac{d^{3}}{T_{i}(o)}=s^{\prime}(p).$

Now, we explain the reason of imposing randomly shifted grids. We fix an
optimal set
$Z^{*}=\\{z_{1}^{*},z_{2}^{*},\ldots,z_{k}^{*}\\}\subset\mathbb{R}^{d}$ of $k$
centers for the point set $Q$, i.e.,
$\operatorname{cost}(Q,Z^{*})=\operatorname{\mathsf{OPT}}$. We call a cell
$C\in G_{i}$ a _center cell_ if it is close to a center in $Z^{*}$, namely
$\operatorname{dist}(C,Z^{*})\leq g_{i}/(2d)$. We claim that there will not be
too many center cells since we randomly shift the grids. In other words, each
center of $Z^{*}$ is far from the boundary of every gird.

######  Lemma 3.5.

With probability at least $0.94$, the total number of center cells is at most
$100kL$.

This lemma is similar to Lemma 2.2 in (Braverman et al., 2017). For
completeness, we also provide a proof in Appendix A.

Consider the total estimated sensitivities, i.e., the sum of the sensitivity
upper bounds over all the points. Due to Theorem 2.5, this sum determines the
size of the coreset. We show that if the estimate $o$ of the optimal $k$-means
cost is close to $\operatorname{\mathsf{OPT}}$, then the total estimated
sensitivities can not be too large.

######  Lemma 3.6.

Suppose the number of center cells is at most $100kL$. Let
$Q_{0},Q_{1},\ldots,Q_{L},s^{\prime}(\cdot)$ be the output of Algorithm 1.
Then the total estimated sensitivities satisfies $\sum_{p\in
Q}s^{\prime}(p)\leq
4000kLd^{3}\cdot\left(\operatorname{\mathsf{OPT}}/o+1\right).$

Since $Q^{I}$ is a subset of $Q$, according to the above lemma, we also have
$\sum_{p\in Q^{I}}s^{\prime}(p)\leq
4000d^{3}Lk\cdot\left(\operatorname{\mathsf{OPT}}/o+1\right)$. Now, we are
ready to prove Theorem 3.2.

Proof of Theorem 3.2 By Lemma 3.5, with probability at least $0.94$, the
number of center cells is at most $100kL$. In the following, we condition on
this event.

Algorithm 2 draws $m$ i.i.d. samples. For each sample, a point $p\in
Q_{i}\subseteq Q^{I}$ is chosen with probability

$\displaystyle\frac{\widehat{q}_{i}/T_{i}(o)}{\sum_{j\in
I}\widehat{q}_{j}/T_{j}(o)}\cdot\frac{1}{|Q_{i}|}=\frac{\frac{\widehat{q}_{i}}{|Q_{i}|}\cdot
20\frac{d^{3}}{T_{i}(o)}}{\sum_{j\in I}\sum_{p^{\prime}\in
Q_{j}}\frac{\widehat{q}_{j}}{|Q_{j}|}\cdot 20\frac{d^{3}}{T_{j}(o)}}.$

Each sample $p$ is given a weight

$\displaystyle\frac{t^{\prime}}{ms^{\prime}(p)}=\frac{1}{m}\cdot\frac{\sum_{j\in
I}\sum_{p^{\prime}\in Q_{j}}\frac{\widehat{q}_{j}}{|Q_{j}|}\cdot
20\frac{d^{3}}{T_{j}(o)}}{\frac{\widehat{q}_{i}}{|Q_{i}|}\cdot
20\frac{d^{3}}{T_{i}(o)}}\cdot\frac{\widehat{q}_{i}}{|Q_{i}|}\in(1\pm\epsilon/4)\cdot\frac{1}{m}\cdot\frac{\sum_{j\in
I}\sum_{p^{\prime}\in Q_{j}}\frac{\widehat{q}_{j}}{|Q_{j}|}\cdot
20\frac{d^{3}}{T_{j}(o)}}{\frac{\widehat{q}_{i}}{|Q_{i}|}\cdot
20\frac{d^{3}}{T_{i}(o)}}.$

Let $s^{\prime\prime}(p)=\frac{\widehat{q}_{i}}{|Q_{i}|}\cdot
20\frac{d^{3}}{T_{i}(o)}$. Since $\widehat{q_{i}}/|Q_{i}|\geq 1/2,$ we know
that $s^{\prime\prime}(p)$ is still a sensitivity upper bound of $p$ with
respect to $Q^{I}$ by Lemma 3.4. According to Algorithm 2, we have
$t^{\prime}=\frac{1}{2}\sum_{p\in Q^{I}}s^{\prime\prime}(p)$. Therefore, if we
set $m$ to be a sufficiently large $\Omega(t^{\prime}\epsilon^{-2}Ld\log
t^{\prime})=\Omega(t^{\prime}\epsilon^{-2}(\log(\Delta^{d})\log
t^{\prime}+\log(1/0.01)))$, then according to Theorem 2.5, $S$ output by
Algorithm 2 is an $\epsilon/2$-coreset for $Q^{I}$ with probability at least
$0.99$. By Lemma 3.3, if $S$ is an $\epsilon/2$-coreset for $Q^{I}$, then $S$
is also an $\epsilon$-coreset for $Q$. Thus, the correctness is proved, and
the overall success probability is at least $0.93$ obtained by a simple union
bound. Now let us analyze the size of the coreset $S$. Since $\forall j\in
I,\widehat{q}_{j}/|Q_{j}|\leq 2,$ we have $\sum_{j\in I}\sum_{p^{\prime}\in
Q_{j}}s^{\prime\prime}(p^{\prime})\leq 2t^{\prime}\leq 4\cdot
4000d^{3}Lk\cdot(\operatorname{\mathsf{OPT}}/o+1)$ by Lemma 3.6. Thus, the
size of $S$ is
$m=O(k\epsilon^{-2}d^{4}L^{2}\log(kdL)\cdot(\operatorname{\mathsf{OPT}}/o+1))$.

##  4 Coreset Construction over a Dynamic Stream

In this section, we show how to implement Algorithms 1 and 2 in the dynamic
streaming setting. We defer all the missing details in this section to
Appendix B.

First, we introduce a dynamic storage structure that allows us to insert and
delete points or cells. We then use this data structure combined with hash
functions to estimate the number of points falling into each cell. Lastly, we
combine them with the sensitivity sampling procedure to obtain our final
algorithm.

1: Storing$(G_{i},\alpha,\beta,\delta)$:

2: Input: $\\{((p_{1},l_{1}),\pm),((p_{2},l_{2}),\pm),\ldots\\}$
$\triangleright$ $l_{t}\in[\widehat{m}]$. Only Algorithm 5 uses the case for
$\widehat{m}>1$.

3: Run Distinct$(\alpha,\delta/4)$ on
$\\{(c_{i}(p_{1}),\pm),(c_{i}(p_{2}),\pm),\ldots\\}$ in parallel.

4: Set $r=\lceil\log(4\alpha/\delta)\rceil$ and $h_{1},h_{2},\ldots,h_{r}$,
$\forall j\in[r],$ $h_{j}:G_{i}\rightarrow[2\alpha]$. $\triangleright$ $h_{j}$
is pairwise independent.

5: Run $r\cdot 2\alpha$ copies of Distinct$(\beta,\delta/(2\alpha))$ in
parallel. $\triangleright$ Each copy is indexed by a pair
$(j,b)\in[r]\times[2\alpha]$. The $(j,b)$-th copy is run on the sub-stream
$\\{((p^{\prime}_{1},l^{\prime}_{1}),\pm),((p^{\prime}_{2},l^{\prime}_{2}),\pm),\ldots\\}$,
where each $((p^{\prime}_{t},l^{\prime}_{t}),\pm)$ satisfies
$h_{j}(c_{i}(p^{\prime}_{t}))=b$.

6: If line 3 returns FAIL, output FAIL; otherwise, let
$\mathcal{C},f:\mathcal{C}\rightarrow\mathbb{N}_{+}$ be the output of line 3.
$\triangleright$ $\mathcal{C}\subset G_{i}$ contains all the cells found, and
$f(C)$ denotes the number of points in $C$.

7: Initialize $S\leftarrow\emptyset$.

8: for $C\in\mathcal{C}$ with $f(C)\leq\beta$ do

9: Find $j\in[r]$ s.t. $\forall
C^{\prime}\in\mathcal{C},h_{j}(C)\not=h_{j}(C^{\prime})$ and the
$(j,h_{j}(C))$-th copy in line 5 does not FAIL.

10: If such $j$ does not exist, output FAIL; otherwise $S\leftarrow S\cup
S_{j,h_{j}(C)}$. $\triangleright$ Here $S_{j,h_{j}(C)}$ is the set of distinct
points found by the $(j,h_{j}(C))$-th copy in line 5.

11: end for

12: Output: $\mathcal{C}\subset
G_{i},f:\mathcal{C}\rightarrow\mathbb{N}_{+},S=\\{(\widetilde{p}_{1},\widetilde{l}_{1}),(\widetilde{p}_{2},\widetilde{l}_{2}),\ldots\\}$

Algorithm 3 Point-cell storing procedure

#### The dynamic point-cell storing data structure.

We introduce an algorithm that maintains a set of points and cells in a
dynamic data stream. Before that, let us recall Ganguly (2005)’s result for
finding distinct elements, which we use as a subroutine in our algorithm.

######  Lemma 4.1 (Distinct elements (Ganguly, 2005)).

Given parameters $M\geq 1,N\geq 1,s\geq 1,\delta\in(0,1/2)$, there is an
algorithm Distinct$(s,\delta)$ that requires $O(s(\log M+\log
N)\log(s/\delta))$ bits to process a stream of insertion/deletion of data
items. For each operation $(i,\pm)$ ($i\in[N]$), the algorithm takes
$O(\log(s/\delta))$ time. $M$ is an upper bound of the total frequency of all
items during the stream. At the end of the stream, if the number of distinct
elements is at most $s$, with probability at least $1-\delta$ it returns all
the distinct elements and their frequencies. It returns FAIL otherwise.

We use Distinct as our sub-routine. We set the parameter $M$ and $N$ to be
sufficiently large in our case, i.e., $M=N=\Delta^{2d}$. In Algorithm 3, we
describe a method which can with probability at least $1-\delta$ output all
the non-empty cells in grid $G_{i}$ when the total number of non-empty cells
is not too large (at most $\alpha$). Furthermore, if the number of points in a
particular cell is not too large (at most $\beta$), the algorithm can output
all the points in that cell. Notice that Algorithm 3 is only a subroutine of
our final algorithm and will only work on some sub-stream of the entire data
stream.

#### Estimating the number of points in each cell.

We use Algorithm 3 as a subroutine and design a dynamic streaming algorithm
(Algorithm 4) that can estimate the number of points in each cell up to some
precision. Furthermore, it also estimates the number of points $|Q_{i}|$ in
crucial cells of each level $i$.

1: PointsEstimation$(o,\epsilon,\delta)$:

2: Input: a point set $Q\subseteq[\Delta]^{d}$ described by a stream
$\\{(p_{1},\pm),(p_{2},\pm),\ldots\\}$

3: for $i\in\\{0,1,\ldots,L\\}$, in parallel, do

4: $T_{i}(o)\leftarrow(d/g_{i})^{2}\cdot o/(100k)$, $\alpha\leftarrow
10^{11}kLd\log(1/\delta)$, $\alpha^{\prime}\leftarrow
10^{16}\epsilon^{-3}kL^{2}d^{4}$. $\triangleright$ $T_{i}(o)$: threshold for
heaviness (Algortihm 1); $\alpha,\alpha^{\prime}$: parameters for Storing.

5: Let $h_{i}:[\Delta]^{d}\rightarrow\\{0,1\\}$ be a $\lambda$-wise
independent hash function. $\triangleright$
$\lambda=10\lceil(dL+\log(1/\delta)+1)\rceil$; $\forall
p\in[\Delta]^{d},h_{i}(p)=1$ w.p. $\min(4\cdot 10^{4}\lambda/T_{i}(o),1)$.

6: Run Storing$(G_{i},\alpha,1,0.1\delta/L)$ on a sub-stream
$\\{((p^{\prime}_{1},1),\pm),((p^{\prime}_{2},1),\pm),\ldots\\}$ in parallel.
$\triangleright$ Storing is defined in Algorithm 3. Here $p^{\prime}_{j}$
satisfies $h_{i}(p^{\prime}_{j})=1$. If Storing returns FAIL, output FAIL.

7: Let $\gamma\leftarrow\epsilon/(40^{2}Ld^{3})$. $\triangleright$ Threshold
for discarding levels

8: Let $h^{\prime}_{i}:[\Delta]^{d}\rightarrow\\{0,1\\}$ be a $\lambda$-wise
independent hash function. $\triangleright$ $\forall
p\in[\Delta]^{d},h^{\prime}_{i}(p)=1$ w.p. $\min(4\cdot
10^{4}\epsilon^{-2}\gamma^{-1}\lambda/T_{i}(o),1)$.

9: Run Storing$(G_{i},\alpha^{\prime},1,0.1\delta/L)$ on sub-stream
$\\{((p^{\prime\prime}_{1},1),\pm),((p^{\prime\prime}_{2},1),\pm),\ldots\\}$
in parallel. $\triangleright$ Storing is defined in Algorithm 3. Here
$p^{\prime\prime}_{j}$ satisfies $h_{i}^{\prime}(p^{\prime\prime}_{j})=1$. If
Storing returns FAIL, output FAIL.

10: Let $\mathcal{C}_{i},f_{i},S_{i}$ $\leftarrow$
Storing$(G_{i},\alpha,1,0.1\delta/L)$ in line 6. Let
$\widehat{f}(C)=f_{i}(C)\cdot\min\left\\{T_{i}(o)/(4\cdot
10^{4}\lambda),1\right\\}$. $\triangleright$ Use $\widehat{f}(C)$ as an
estimator for $|C\cap Q|$ and follow Algorithm 1 to determine whether $C$ is
marked as heavy, crucial or nothing. (And conceptually compute
$Q_{0},\ldots,Q_{L}$ for analysis.)

11: Let $\mathcal{C}_{i}^{\prime},f_{i}^{\prime},S_{i}^{\prime}$ $\leftarrow$
Storing$(G_{i},\alpha^{\prime},1,0.1\delta/L)$ in line 9.

12: Let $\widehat{q}_{i}=\min\left\\{\epsilon^{2}\gamma T_{i}(o)/(4\cdot
10^{4}\lambda)\cdot\sum_{C\in\mathcal{C}_{i}^{\prime}:C\text{ is
crucial}}f_{i}^{\prime}(C),1\right\\}$.

13: end for

14: Output: $\widehat{q}_{0},\widehat{q}_{1},\ldots,\widehat{q}_{L}$ and
$\widehat{f}:\bigcup_{i=0}^{L}G_{i}\rightarrow\mathbb{R}_{+}$

Algorithm 4 Estimating the number of points in each cell and in each level

#### Sensitivity sampling over a dynamic stream.

Since using Algorithm 4 we can estimate the number of points in each cell and
the size of each $Q_{i}$, the only remaining thing for simulating Algorithm 2
is to draw samples based on their sensitivity upper bounds. In Algorithm 5, we
show how to achieve this in a dynamic stream.

1: Sampling$(o,\epsilon,\delta)$:

2: Input: a point set $Q\subseteq[\Delta]^{d}$ described by a stream
$\\{(p_{1},\pm),(p_{2},\pm),\ldots\\}$

3: Run PointsEstimation$(o,\epsilon,\delta/2)$ in parallel on the input
stream. If it returns FAIL, output FAIL.

4: $\forall i\in\\{0,1,\ldots,L\\}$, $T_{i}(o)\leftarrow(d/g_{i})^{2}\cdot
o/k\cdot 1/100$. $\triangleright$ Threshold for heaviness (Algorithm 1).

5:
$\widehat{m}\leftarrow\Theta\left(k\epsilon^{-3}L^{4}d^{7}\log\left(\frac{dLk}{\delta}\right)\cdot\frac{1}{\delta}\right)$.
$\triangleright$ $\widehat{m}$ hash functions needed for $m$ independent
samples.

6: $\lambda\leftarrow 10\lceil(dL+\log(1/\delta)+1)\rceil$. $\triangleright$
$\lambda$ is the independence parameter.

7: $\forall i\in\\{0,1,\ldots,L\\},$ choose
$h_{i,1},h_{i,2},\ldots,h_{i,\widehat{m}}:[\Delta]^{d}\rightarrow\\{0,1\\}$.
$\triangleright$ $\forall j\in[\widehat{m}],$ $h_{i,j}$ is $\lambda$-wise
independent, $\forall p\in[\Delta]^{d}$, $h_{i,j}(p)=1$ w.p.
$\min\left\\{1/(10^{4}kLT_{i}(o)),1\right\\}$.

8:
$\alpha\leftarrow\Theta(k\epsilon^{-3}L^{3}d^{7}\log(dLk/\delta)\delta^{-1}),\beta\leftarrow\Theta(\epsilon^{-3}L^{3}d^{7}\log(dLk/\delta)\delta^{-1})$.
$\triangleright$ $\alpha,\beta$: for Storing.

9: For $i\in\\{0,1,\ldots,L\\}$, run Storing$(G_{i},\alpha,\beta,0.1\delta/L)$
(Algorithm 3) in parallel. $\triangleright$ Each instance is run on a new
stream obtained by splitting each operation $(p_{t},\pm)$ from the original
input stream into a set of new operations $\\{((p_{t},j),\pm)\mid
j\in[\widehat{m}],h_{i,j}(p_{t})=1\\}$. If any Storing returns FAIL, output
FAIL.

10: $\widehat{q}_{0},\widehat{q}_{1},\ldots,\widehat{q}_{L}$,
$\widehat{f}:\bigcup_{i=0}^{L}G_{i}\rightarrow\mathbb{R}_{+}$ $\leftarrow$
PointsEstimation$(o,\epsilon,\delta/2)$ in line 3.

11: $\mathcal{C}_{i},f_{i},S_{i}$ $\leftarrow$
Storing$(G_{i},\alpha,\beta,0.1\delta/L)$ in line 9.

12: For $i\in\\{0,1,\ldots,L\\}$, if $\exists C\in\mathcal{C}_{i}$ marked as
crucial in line 3, and $f_{i}(C)>\beta$, output FAIL.

13: $\gamma\leftarrow\epsilon/(40^{2}Ld^{3})$. $\triangleright$ Threshold for
discarding levels.

14: $I\leftarrow\\{i\mid 0\leq i\leq L,\widehat{q}_{i}\geq\gamma T_{i}(o)\\}$.

15: $t^{\prime}\leftarrow\sum_{i\in I}\widehat{q}_{i}\cdot 10d^{3}/T_{i}(o)$.
$\triangleright$ Total estimated sensitivities.

16: $m\leftarrow\Theta(t^{\prime}\epsilon^{-2}Ld\log(t^{\prime}/\delta))$,
$S\leftarrow\emptyset$. $\triangleright$ Total number of samples.

17: For $i\in\\{0,1,\ldots,L\\},$ set $A_{i}=[\widehat{m}]$.

18: for $j=1\rightarrow m$ do

19: Choose a random level $i\in I$ with probability $(\widehat{q}_{i}\cdot
10d^{3}/T_{i}(o))/t^{\prime}$.

20: Choose the minimum $j\in A_{i}$ s.t. $\exists p\in Q_{i}$, $(p,j)\in
S_{i}$. If no such $j$, output FAIL.

21: Uniformly choose a point $p$ from the set $\\{q\in Q_{i}\mid(q,j)\in
S_{i}\\}$.

22: Update $A_{i}\leftarrow\\{j+1,j+2,\ldots,\widehat{m}\\}$.

23: Add $(p,t^{\prime}/(ms^{\prime}(p)))$ to set $S$. $\triangleright$
$s^{\prime}(p)=10d^{3}/T_{i}(o)$.

24: end for

25: Output: the set $S$

Algorithm 5 Sensitivity sampling over a dynamic stream

#### The final algorithm.

Finally, we use exponential search to enumerate the guesses $o$. In Algorithm
6, we show the details of how to run Algorithm 5 with different guesses in
parallel. Our main theorem is the following.

1: DynamicCoreset$(\epsilon)$:

2: input: a point set $Q\subseteq[\Delta]^{d}$ described by a stream
$\\{(p_{1},\pm),(p_{2},\pm),\ldots\\}$

3: Impose randomly shifted grids $G_{-1},G_{0},G_{1},\ldots,G_{L}$ (Definition
3.1).

4: Run Distinct$(10000k,0.001)$ (Lemma 4.1) over the input stream in parallel.

5: If line 4 does not output FAIL, we output the entire point set $Q$.

6: For each $u\in[2dL]$, let $o_{u}=2^{u}\cdot 50k$ and run
Sampling$(o_{u},\epsilon,0.001/(dL))$ (Algorithm 5) over the input stream in
parallel.

7: Set a threshold $h=\Theta(k\epsilon^{-2}L^{2}d^{4}\log(kLd))$.

8: Find the smallest $u^{*}$ such that
Sampling$(o_{u^{*}},\epsilon,0.001/(dL))$ in line 6 does not output FAIL, and
the returned set $S^{*}$ has size at most $h$, i.e., $|S^{*}|\leq h$.

9: If no such $u^{*}$, output FAIL. Otherwise, output $S^{*}$ returned by
Sampling$(o_{u^{*}},\epsilon,0.001/(dL))$.

Algorithm 6 Coreset construction over a dynamic stream

######  Theorem 4.2.

Suppose a point set $Q\subseteq[\Delta]^{d}$ is given by a stream of
insertion/deletion operations in the dynamic streaming model (Definition 2.1).
Let $L=\log\Delta$. For given $\epsilon\in(0,1/2)$, Algorithm 6 uses a single
pass over the stream and on termination outputs a $k$-means $\epsilon$-coreset
$S$ (Definition 2.3) for $Q$ with probability at least $0.9$. Furthermore, the
size of the coreset is at most $O(k\epsilon^{-2}d^{4}L^{2}\log(kdL))$. The
total space used by the algorithm is
$\widetilde{O}(k)\cdot\operatorname{poly}(dL/\epsilon)$ bits.

##  5 Conclusion

This paper gives the first $k$-means coreset construction in the dynamic
streaming model using space polynomial in the dimension $d$ and nearly optimal
(linear) in $k$. The algorithm is based on sensitivity sampling, which we
believe is a powerful tool and can have broader applications.

## References

  * Abraham et al. (2016a) Ittai Abraham, Shiri Chechik, Daniel Delling, Andrew V Goldberg, and Renato F Werneck.  On dynamic approximate shortest paths for planar graphs with worst-case costs.  In _Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , pages 740–753. Society for Industrial and Applied Mathematics, 2016a.
  * Abraham et al. (2016b) Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, and Richard Peng.  On fully dynamic graph sparsifiers.  In _2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 335–344. IEEE, 2016b.
  * Ackermann et al. (2012) Marcel R Ackermann, Marcus Märtens, Christoph Raupach, Kamil Swierkot, Christiane Lammersen, and Christian Sohler.  Streamkm++: A clustering algorithm for data streams.  _Journal of Experimental Algorithmics (JEA)_ , 17:2–4, 2012\.
  * Agarwal et al. (2004) Pankaj K Agarwal, Sariel Har-Peled, and Kasturi R Varadarajan.  Approximating extent measures of points.  _Journal of the ACM (JACM)_ , 51(4):606–635, 2004\.
  * Ahn et al. (2012a) Kook Jin Ahn, Sudipto Guha, and Andrew McGregor.  Graph sketches: sparsification, spanners, and subgraphs.  In _Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on Principles of Database Systems_ , pages 5–14. ACM, 2012a.
  * Ahn et al. (2012b) Kook Jin Ahn, Sudipto Guha, and Andrew McGregor.  Analyzing graph structure via linear measurements.  In _Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms_ , pages 459–467. Society for Industrial and Applied Mathematics, 2012b.
  * Ahn et al. (2013) Kook Jin Ahn, Sudipto Guha, and Andrew McGregor.  Spectral sparsification in dynamic graph streams.  In _Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques_ , pages 1–10. Springer, 2013.
  * Aloise et al. (2009) Daniel Aloise, Amit Deshpande, Pierre Hansen, and Preyas Popat.  Np-hardness of euclidean sum-of-squares clustering.  _Machine learning_ , 75(2):245–248, 2009.
  * Babcock et al. (2003) Brain Babcock, Mayur Datar, Rajeev Motwani, and Liadan O’Callaghan.  Maintaining variance and k-medians over data stream windows.  In _Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems_ , pages 234–243. ACM, 2003.
  * Backurs et al. (2016) Arturs Backurs, Piotr Indyk, Eric Price, Ilya Razenshteyn, and David P Woodruff.  Nearly-optimal bounds for sparse recovery in generic norms, with applications to k-median sketching.  In _Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms_ , pages 318–337. SIAM, 2016.
  * Bar-Yossef et al. (2002) Ziv Bar-Yossef, TS Jayram, Ravi Kumar, D Sivakumar, and Luca Trevisan.  Counting distinct elements in a data stream.  In _International Workshop on Randomization and Approximation Techniques in Computer Science_ , pages 1–10. Springer, 2002.
  * Baswana (2008) Surender Baswana.  Streaming algorithm for graph spanners-single pass and constant processing time per edge.  _Information Processing Letters_ , 106(3):110–114, 2008.
  * Baswana et al. (2012) Surender Baswana, Sumeet Khurana, and Soumojit Sarkar.  Fully dynamic randomized algorithms for graph spanners.  _ACM Transactions on Algorithms (TALG)_ , 8(4):35, 2012.
  * Baswana et al. (2015) Surender Baswana, Manoj Gupta, and Sandeep Sen.  Fully dynamic maximal matching in o($\log n$) update time.  _SIAM Journal on Computing_ , 44(1):88–113, 2015\.
  * Bellare and Rompel (1994) Mihir Bellare and John Rompel.  Randomness-efficient oblivious sampling.  In _Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on_ , pages 276–287. IEEE, 1994.
  * Bentley and Saxe (1980) Jon Louis Bentley and James B Saxe.  Decomposable searching problems i. static-to-dynamic transformation.  _Journal of Algorithms_ , 1(4):301–358, 1980\.
  * Bernstein and Stein (2016) Aaron Bernstein and Cliff Stein.  Faster fully dynamic matchings with small approximation ratios.  In _Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms_ , pages 692–711. Society for Industrial and Applied Mathematics, 2016.
  * Bhattacharya et al. (2014) Sayan Bhattacharya, Parinya Chalermsook, Kurt Mehlhorn, and Adrian Neumann.  New approximability results for the robust k-median problem.  In _Scandinavian Workshop on Algorithm Theory_ , pages 50–61. Springer, 2014.
  * Bhattacharya et al. (2015) Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, and Charalampos Tsourakakis.  Space-and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams.  In _Proceedings of the forty-seventh annual ACM symposium on Theory of computing_ , pages 173–182. ACM, 2015.
  * Boutsidis et al. (2016) Christos Boutsidis, David P Woodruff, and Peilin Zhong.  Optimal principal component analysis in distributed and streaming models.  In _Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC)_ , pages 236–249. ACM, https://arxiv.org/pdf/1504.06729, 2016.
  * Braverman et al. (2016) Vladimir Braverman, Dan Feldman, and Harry Lang.  New frameworks for offline and streaming coreset constructions.  _arXiv preprint arXiv:1612.00889_ , 2016.
  * Braverman et al. (2017) Vladimir Braverman, Gereon Frahling, Harry Lang, Christian Sohler, and Lin F Yang.  Clustering high dimensional dynamic data streams.  In _ICML_. https://arxiv.org/pdf/1706.03887, 2017.
  * Charikar et al. (1998) Moses Charikar, Chandra Chekuri, Ashish Goel, and Sudipto Guha.  Rounding via trees: deterministic approximation algorithms for group steiner trees and k-median.  In _Proceedings of the thirtieth annual ACM symposium on Theory of computing_ , pages 114–123. ACM, 1998.
  * Charikar et al. (2003) Moses Charikar, Liadan O’Callaghan, and Rina Panigrahy.  Better streaming algorithms for clustering problems.  In _Proceedings of the thirty-fifth annual ACM symposium on Theory of computing_ , pages 30–39. ACM, 2003.
  * Chen (2009) Ke Chen.  On coresets for k-median and k-means clustering in metric and euclidean spaces and their applications.  _SIAM Journal on Computing_ , 39(3):923–947, 2009\.
  * Cohen et al. (2015) Michael B Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu.  Dimensionality reduction for k-means clustering and low rank approximation.  In _Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC)_ , pages 163–172. ACM, https://arxiv.org/pdf/1410.6801, 2015.
  * Cohen-Addad et al. (2016) Vincent Cohen-Addad, Philip N Klein, and Claire Mathieu.  Local search yields approximation schemes for k-means and k-median in euclidean and minor-free metrics.  In _Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on_ , pages 353–364. IEEE, 2016.
  * Crouch et al. (2013) Michael S Crouch, Andrew McGregor, and Daniel Stubbs.  Dynamic graphs in the sliding-window model.  In _European Symposium on Algorithms_ , pages 337–348. Springer, 2013\.
  * Feigenbaum et al. (2005) Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang.  On graph problems in a semi-streaming model.  _Theoretical Computer Science_ , 348(2-3):207–216, 2005.
  * Feldman and Langberg (2011) Dan Feldman and Michael Langberg.  A unified framework for approximating and clustering data.  In _Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011_ , pages 569–578, 2011\.
  * Feldman and Schulman (2012) Dan Feldman and Leonard J Schulman.  Data reduction for weighted and outlier-resistant clustering.  In _Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms_ , pages 1343–1354. Society for Industrial and Applied Mathematics, 2012.
  * Feldman et al. (2007) Dan Feldman, Morteza Monemizadeh, and Christian Sohler.  A ptas for k-means clustering based on weak coresets.  In _Proceedings of the twenty-third annual symposium on Computational geometry_ , pages 11–18. ACM, 2007.
  * Frahling and Sohler (2005) Gereon Frahling and Christian Sohler.  Coresets in dynamic geometric data streams.  In _Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (STOC)_ , pages 209–217. ACM, 2005.
  * Frahling et al. (2005) Gereon Frahling, Piotr Indyk, and Christian Sohler.  Sampling in dynamic data streams and applications.  In _Symposium on Computational Geometry 2005_ , pages 142–149, 2005\.
  * Friggstad et al. (2016) Zachary Friggstad, Mohsen Rezapour, and Mohammad R Salavatipour.  Local search yields a ptas for k-means in doubling metrics.  In _Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on_ , pages 365–374. IEEE, 2016.
  * Ganguly (2005) Sumit Ganguly.  Counting distinct items over update streams.  In _International Symposium on Algorithms and Computation_ , pages 505–514. Springer, 2005.
  * Goel et al. (2012a) Ashish Goel, Michael Kapralov, and Sanjeev Khanna.  On the communication and streaming complexity of maximum bipartite matching.  In _Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms_ , pages 468–485. SIAM, 2012a.
  * Goel et al. (2012b) Ashish Goel, Michael Kapralov, and Ian Post.  Single pass sparsification in the streaming model with edge deletions.  _arXiv preprint arXiv:1203.4900_ , 2012b.
  * Guha et al. (2000) Sudipto Guha, Nina Mishra, R. Motwani, and L. O’Callaghan.  Clustering data streams.  In _FOCS_ , pages 359–366, 2000.
  * Har-Peled and Kushal (2005) Sariel Har-Peled and Akash Kushal.  Smaller coresets for k-median and k-means clustering.  In _Proceedings of the twenty-first annual symposium on Computational geometry_ , pages 126–134. ACM, 2005.
  * Har-Peled and Mazumdar (2004) Sariel Har-Peled and Soham Mazumdar.  On coresets for k-means and k-median clustering.  In _Proceedings of the thirty-sixth annual ACM symposium on Theory of computing_ , pages 291–300. ACM, 2004.
  * Indyk (2004) Piotr Indyk.  Algorithms for dynamic geometric problems over data streams.  In _Proceedings of the thirty-sixth annual ACM symposium on Theory of computing_ , pages 373–380. ACM, 2004.
  * Indyk and Price (2011) Piotr Indyk and Eric Price.  K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance.  In _Proceedings of the forty-third annual ACM symposium on Theory of computing_ , pages 627–636. ACM, 2011.
  * Jain (2010) Anil K Jain.  Data clustering: 50 years beyond k-means.  _Pattern recognition letters_ , 31(8):651–666, 2010.
  * Kanungo et al. (2002) Tapas Kanungo, David M Mount, Nathan S Netanyahu, Christine D Piatko, Ruth Silverman, and Angela Y Wu.  A local search approximation algorithm for k-means clustering.  In _Proceedings of the eighteenth annual symposium on Computational geometry_ , pages 10–18. ACM, 2002.
  * Kapralov et al. (2017) Michael Kapralov, Yin Tat Lee, CN Musco, CP Musco, and Aaron Sidford.  Single pass spectral sparsification in dynamic streams.  _SIAM Journal on Computing_ , 46(1):456–477, 2017\.
  * Kelner and Levin (2011) J. Kelner and A. Levin.  Spectral sparsification in the semi-streaming setting.  In _Symposium on Theoretical Aspects of Computer Science (STACS)_ , 2011.
  * Kumar et al. (2010) Amit Kumar, Yogish Sabharwal, and Sandeep Sen.  Linear-time approximation schemes for clustering problems in any dimensions.  _Journal of the ACM (JACM)_ , 57(2):5, 2010.
  * Lloyd (1982) Stuart Lloyd.  Least squares quantization in pcm.  _IEEE transactions on information theory_ , 28(2):129–137, 1982.
  * Mahajan et al. (2009) Meena Mahajan, Prajakta Nimbhorkar, and Kasturi Varadarajan.  The planar k-means problem is np-hard.  In _International Workshop on Algorithms and Computation_ , pages 274–285. Springer, 2009.
  * McGregor (2014) Andrew McGregor.  Graph stream algorithms: a survey.  _ACM SIGMOD Record_ , 43(1):9–20, 2014.
  * Muthukrishnan (2005) Shanmugavelayutham Muthukrishnan.  Data streams: Algorithms and applications.  _Foundations and Trends® in Theoretical Computer Science_ , 1(2):117–236, 2005.
  * Sohler and Woodruff (2018) Christian Sohler and David P. Woodruff.  Strong coresets for k-median and subspace approximation, goodbye dimension.  In _FOCS_. IEEE, 2018.
  * Song et al. (2017a) Zhao Song, David P Woodruff, and Peilin Zhong.  Low rank approximation with entrywise $\ell_{1}$-norm error.  In _Proceedings of the 49th Annual Symposium on the Theory of Computing (STOC)_. ACM, https://arxiv.org/pdf/1611.00898, 2017a.
  * Song et al. (2017b) Zhao Song, David P Woodruff, and Peilin Zhong.  Relative error tensor low rank approximation.  _arXiv preprint arXiv:1704.08246_ , 2017b.

##  Appendix A Missing Details in Section 3

Proof of Fact 1 Consider an arbitrary point $p\in Q.$ Let
$C_{-1},C_{0},\ldots,C_{L}$ be the cells which contain $p$, where $\forall
i\in\\{-1,0,1,\ldots,L\\}$, the cell $C_{i}$ is from the grid $G_{i}$.
According to Algorithm 1, $C_{-1}$ is marked as heavy and $C_{L}$ cannot be
marked as heavy. Let $l$ be the largest integer such that all the cells
$C_{-1},C_{0},\ldots,C_{l-1}$ are marked as heavy. Then the cell $C_{l}$ must
be marked as crucial, and all the cells $C_{l+1},C_{l+2},\ldots,C_{L}$ can not
be crucial. Thus, we have $p\in Q_{l}$ and $\forall
i\in\\{0,1,\ldots,L\\}\setminus\\{l\\},$ $p\not\in Q_{i}$.

Facts 2 and 3 are obvious from the algorithms, so we omit the proofs.

The following claim is useful in the proofs.

######  Claim 4.

Let $Q^{I}$ and $\gamma$ be the same as mentioned in Algorithm 2. For
$i\in\\{0,1,\ldots,L\\}$ and any heavy cell $C\in G_{i-1}$, if all the
ancestors of $C$ are marked as heavy, then we have $|C\cap
Q^{I}|\geq(1-5(L-i)\gamma)\cdot|C\cap Q|$.

######  Proof A.1.

The proof is by induction. When $i=L$, consider a heavy cell $C\in G_{L-1}$
whose ancestors are also heavy. If there is no such cell $C$, then the claim
holds directly for $i=L$. Otherwise, according to the construction of
$Q_{0},Q_{1},\ldots,Q_{L}$, $\forall j\in\\{0,1,\ldots,L-1\\},$ we have
$Q_{j}\cap C=\emptyset$ and $(Q\cap C)\subseteq Q_{L}$. Since $C$ is marked as
heavy, we know that $|Q_{L}\cap C|=|Q\cap C|\geq 0.9T_{L-1}(o)\geq
0.9T_{L}(o)/4$. It implies that
$\widehat{q}_{L}\geq\min(|Q_{L}|-0.1\epsilon\gamma
T_{L}(o),(1-0.01\epsilon)|Q_{L}|)\geq\min(|Q\cap C|-0.1\epsilon\gamma
T_{L}(o),(1-0.01\epsilon)|Q\cap C|)\geq\gamma T_{L}(o)$. Thus, we have
$Q_{L}\subseteq Q^{I}$ which implies that $|C\cap Q^{I}|=|C\cap Q_{L}|=|C\cap
Q|$.

Now assume the claim is true for $i+1,i+2,\ldots,L.$ Consider a heavy cell
$C\in G_{i-1}$ whose ancestors are also marked as heavy. If there is no such
cell $C$, the claim holds directly for $i$. Now consider the case when $C$
exists. If level $i\in I$, i.e., $Q_{i}\subseteq Q^{I}$, we have

$\displaystyle|C\cap Q^{I}|$ $\displaystyle=\sum_{C^{\prime}\in
G_{i}:\text{$C^{\prime}$ is a heavy child of $C$}}|C^{\prime}\cap
Q^{I}|+\sum_{C^{\prime}\in G_{i}:\text{$C^{\prime}$ is a crucial child of
$C$}}|C^{\prime}\cap Q^{I}|$ $\displaystyle=\sum_{C^{\prime}\in
G_{i}:\text{$C^{\prime}$ is a heavy child of $C$}}|C^{\prime}\cap
Q^{I}|+|C\cap Q_{i}|$ $\displaystyle\geq(1-5(L-i-1)\gamma)\sum_{C^{\prime}\in
G_{i}:\text{$C^{\prime}$ is a heavy child of $C$}}|C^{\prime}\cap Q|+|C\cap
Q_{i}|$ $\displaystyle\geq(1-5(L-i-1)\gamma)|C\cap Q|$
$\displaystyle\geq(1-5(L-i)\gamma)|C\cap Q|.$

If level $i\not\in I$, i.e., $Q_{i}\not\subseteq Q^{I}$, we have

$\displaystyle\sum_{C^{\prime}\in G_{i}:\text{$C^{\prime}$ is a heavy child of
$C$}}|C^{\prime}\cap Q|\geq|C\cap Q|-|Q_{i}|\geq|C\cap Q|-1.1\gamma
T_{i}(o)\geq(1-5\gamma)|C\cap Q|.$

Thus,

$\displaystyle|C\cap Q^{I}|$ $\displaystyle\geq\sum_{C^{\prime}\in
G_{i}:\text{$C^{\prime}$ is a heavy child of $C$}}|C^{\prime}\cap Q^{I}|$
$\displaystyle\geq(1-5(L-i-1)\gamma)\cdot\sum_{C^{\prime}\in
G_{i}:\text{$C^{\prime}$ is a heavy child of $C$}}|C^{\prime}\cap Q|$
$\displaystyle\geq(1-5(L-i-1)\gamma)(1-5\gamma)|C\cap Q|$
$\displaystyle\geq(1-5(L-i)\gamma)|C\cap Q|.$

Proof of Lemma 3.3 Since $Q^{I}$ is a subset of $Q$,
$\operatorname{cost}(Q^{I},Z)\leq\operatorname{cost}(Q,Z)$ is trivial. In the
following, we are trying to prove
$\operatorname{cost}(Q,Z)\leq(1+\epsilon/10)\operatorname{cost}(Q^{I},Z)$.

We consider an level $i\not\in I$, i.e., $Q_{i}\not\subseteq Q^{I}$. For a
point $p\in Q_{i}$, all the ancestors of $c_{i}(p)$ must be heavy. By
averaging argument, there must exist a point $q\in c_{i-1}(p)\cap Q^{I}$ such
that

$\displaystyle\operatorname{dist}^{2}(p,Z)\leq$
$\displaystyle\leavevmode\nobreak\
2\operatorname{dist}^{2}(p,q)+2\operatorname{dist}^{2}(q,Z)$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
2dg_{i-1}^{2}+2\operatorname{dist}^{2}(q,Z)$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\ 2dg_{i-1}^{2}+2\frac{1}{|c_{i-1}(p)\cap
Q^{I}|}\sum_{q\in c_{i-1}(p)\cap Q^{I}}\operatorname{dist}^{2}(q,Z)$ (1)

where the first step follows from triangle inequality, the second step follows
from definition of the grids, the last step follows from an averaging
argument.

According to Claim 4, we have

$\displaystyle|c_{i-1}(p)\cap Q^{I}|\geq\frac{1}{2}T_{i-1}(o).$

Let $Q^{N}=Q\setminus Q^{I}$. We can lower bound $\operatorname{cost}(Q,Z)$ in
the following sense,

$\displaystyle\operatorname{cost}(Q,Z)=$ $\displaystyle\leavevmode\nobreak\
\operatorname{cost}(Q^{I},Z)+\operatorname{cost}(Q^{N},Z)$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\ \operatorname{cost}(Q^{I},Z)+\sum_{i\not\in
I}\sum_{p\in Q_{i}}\operatorname{dist}^{2}(p,z)$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\
\operatorname{cost}(Q^{I},Z)+2\sum_{i\not\in I}\sum_{p\in
Q_{i}}\left(dg_{i-1}^{2}+\frac{1}{|c_{i-1}(p)\cap Q^{I}|}\sum_{q\in
c_{i-1}(p)\cap Q^{I}}\operatorname{dist}^{2}(q,Z)\right)$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\
\operatorname{cost}(Q^{I},Z)+2\sum_{i\not\in I}\sum_{p\in
Q_{i}}\left(dg_{i-1}^{2}+\frac{2}{T_{i-1}(o)}\sum_{q\in c_{i-1}(p)\cap
Q^{I}}\operatorname{dist}^{2}(q,Z)\right)$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\
\operatorname{cost}(Q^{I},Z)+2\sum_{i\not\in I}\sum_{p\in
Q_{i}}\left(dg_{i-1}^{2}+\frac{2}{T_{i-1}(o)}\sum_{q\in
Q^{I}}\operatorname{dist}^{2}(q,Z)\right)$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\
\operatorname{cost}(Q^{I},Z)+2\sum_{i\not\in I}1.1\gamma
T_{i}(o)\cdot\left(dg_{i-1}^{2}+\frac{2}{T_{i-1}(o)}\sum_{q\in
Q^{I}}\operatorname{dist}^{2}(q,Z)\right)$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\ \operatorname{cost}(Q^{I},Z)+5L\gamma
T_{i}(o)\cdot\left(dg_{i-1}^{2}+\frac{2}{T_{i-1}(o)}\sum_{q\in
Q^{I}}\operatorname{dist}^{2}(q,Z)\right)$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\ \operatorname{cost}(Q^{I},Z)+5L\gamma
T_{i}(o)\cdot\left(dg_{i-1}^{2}+\frac{2}{T_{i-1}(o)}\operatorname{cost}(Q^{I},Z)\right)$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\operatorname{cost}(Q^{I},Z)+5L\gamma(d^{3}o/(25k)+8\operatorname{cost}(Q^{I},Z))$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\operatorname{cost}(Q^{I},Z)+5L\gamma(d^{3}\operatorname{cost}(Q,Z)/(25k)+8\operatorname{cost}(Q^{I},Z)).$

where the second step follows from the definition of the cost, the third step
follows from Eq. (A), the fourth step follows from $|c_{i-1}(p)\cap Q^{I}|\geq
T_{i-1}(o)/2$, the fifth step follows from $(c_{i-1}(p)\cap Q^{I})\subset
Q^{I}$, the sixth step follows from $|Q_{i}|\leq 1.1\gamma T_{i}(o)$, the
seventh step follows from $L+1-|I|\leq L+1\leq 2L$ and $2\cdot 2\cdot 1.1\leq
5$, the ninth step follows from $T_{i}(o)=4T_{i-1}(o)$ and
$T_{i}(o)=(d/g_{i})^{2}\cdot o/k\cdot 1/100$, and the last step follows from
$o\leq\operatorname{\mathsf{OPT}}\leq\operatorname{cost}(Q,Z)$.

It implies that

$\displaystyle\frac{\operatorname{cost}(Q,Z)}{\operatorname{cost}(Q^{I},Z)}\leq\frac{1+40L\gamma}{1-5L\gamma
d^{3}/(25k)}\leq\frac{1+\epsilon/40}{1-\epsilon/40}\leq 1+\epsilon/10,$

where the second step follows from $\gamma\leq\epsilon/(40^{2}Ld^{3})$, and
the last step follows from $\epsilon<1$.

Proof of Lemma 3.4 Let $Z\subseteq\mathbb{R}^{d}$ be an arbitrary set of $k$
centers. Fix a point $p\in Q$. Suppose $p$ is in $Q_{i}$, i.e., $p$ is in a
crucial cell of $G_{i}$. Let $C=c_{i-1}(p)$, i.e., $C$ is the parent cell of
the crucial cell that contains $p$. By Algorithm 1, $C$ and all of its
ancestors must be heavy. By Claim 4, $C\cap Q^{I}$ cannot be empty. Thus, by
an averaging argument, there is a point $p^{\prime}\in C$ such that

$\displaystyle\operatorname{dist}^{2}(p^{\prime},Z)\leq\frac{1}{|C\cap
Q^{I}|}\sum_{q\in C\cap Q^{I}}\operatorname{dist}^{2}(q,Z).$ (2)

We have

$\displaystyle\frac{\operatorname{dist}^{2}(p,Z)}{\sum_{q\in
Q^{I}}\operatorname{dist}^{2}(q,Z)}\leq$ $\displaystyle\leavevmode\nobreak\
2\frac{\operatorname{dist}^{2}(p^{\prime},Z)}{\sum_{q\in
Q^{I}}\operatorname{dist}^{2}(q,Z)}+2\frac{\operatorname{dist}^{2}(p,p^{\prime})}{\sum_{q\in
Q^{I}}\operatorname{dist}^{2}(q,Z)}$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\ 2\frac{\sum_{q\in C\cap
Q^{I}}\operatorname{dist}^{2}(q,Z)}{|C\cap Q^{I}|\sum_{q\in
Q^{I}}\operatorname{dist}^{2}(q,Z)}+2\frac{dg_{i-1}^{2}}{\sum_{q\in
Q^{I}}\operatorname{dist}^{2}(q,Z)}$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\ 2\frac{\sum_{q\in
Q^{I}}\operatorname{dist}^{2}(q,Z)}{|C\cap Q^{I}|\sum_{q\in
Q^{I}}\operatorname{dist}^{2}(q,Z)}+2\frac{dg_{i-1}^{2}}{\sum_{q\in
Q^{I}}\operatorname{dist}^{2}(q,Z)}$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\ 2\frac{1}{|C\cap
Q^{I}|}+2\frac{dg_{i-1}^{2}}{\sum_{q\in Q^{I}}\operatorname{dist}^{2}(q,Z)}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\ 2\frac{1}{|C\cap
Q^{I}|}+4\frac{dg_{i-1}^{2}}{\operatorname{\mathsf{OPT}}}$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\ 2\frac{1}{|C\cap
Q^{I}|}+16\frac{dg_{i}^{2}}{\operatorname{\mathsf{OPT}}}$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\ 2\frac{1}{|C\cap
Q^{I}|}+\frac{d^{3}o}{T_{i}(o)k\operatorname{\mathsf{OPT}}}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
9\frac{1}{T_{i}(o)}+\frac{d^{3}o}{T_{i}(o)k\operatorname{\mathsf{OPT}}}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
9\frac{1}{T_{i}(o)}+\frac{d^{3}}{T_{i}(o)}$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\ 10\frac{d^{3}}{T_{i}(o)}$

where the first step follows from triangle inequality, the second step follows
from Eq. (2) and $p^{\prime}\in c_{i-1}(p)$, the fifth step follows from
$\sum_{q\in
Q^{I}}\operatorname{dist}^{2}(q,Z)\geq(1-\epsilon)\operatorname{cost}(Q,Z)\geq\operatorname{\mathsf{OPT}}/2$
(Lemma 3.3), the sixth step follows from $g_{i-1}^{2}\leq 4g_{i}^{2}$, the
seventh step follows from $T_{i}(o)=\frac{d^{2}}{g_{i}^{2}}\frac{o}{100k}$,
the eighth step follows from $T_{i}(o)=4T_{i-1}(o)\leq 4.5|C\cap Q^{I}|$
(Claim 4 and $|C\cap Q|\geq 0.9T_{i-1}(o)$), the ninth step follows from
$1/k\leq 1,o\leq\operatorname{\mathsf{OPT}}$.

Proof of Lemma 3.5 Fix an $i\in\\{0,1,\ldots,L\\}$ and consider the grid
$G_{i}$. For each optimal center $z_{j}^{*}$, we use $X_{j,\alpha}$ to denote
the indicator random variable for the event that the distance from $z_{j}^{*}$
to the boundary in dimension $\alpha$ of the grid $G_{i}$ is at most
$g_{i}/(2d)$. Since in each dimension, if the center is close to a boundary,
it contributes a factor at most $2$ to the total number of center cells. It
follows that the number of cells that have distance at most $g_{i}/(2d)$ to
$z_{j}^{*}$ is at most

$\displaystyle N=2^{\sum_{\alpha=1}^{d}X_{j,\alpha}}.$

We denote $Y_{j,\alpha}$ to be $2^{X_{j,\alpha}}$, then

$\displaystyle\operatorname*{{\bf{E}}}[N]=\operatorname*{{\bf{E}}}\left[\prod_{\alpha=1}^{d}Y_{j,\alpha}\right]=\prod_{\alpha=1}^{d}\operatorname*{{\bf{E}}}[Y_{j,\alpha}].$

By using $\Pr[X_{j,\alpha}=1]\leq(2g_{i}/(2d))/g_{i}=1/d$, we obtain

$\displaystyle\operatorname*{{\bf{E}}}[Y_{j,\alpha}]\leq\operatorname*{{\bf{E}}}[1+X_{j,\alpha}]=1+\operatorname*{{\bf{E}}}[X_{j,\alpha}]\leq
1+1/d.$

Thus
$\operatorname*{{\bf{E}}}[N]=\prod_{\alpha=1}^{d}\operatorname*{{\bf{E}}}[Y_{j,\alpha}]\leq(1+1/d)^{d}\leq
e$. The expected number of center cells in a single grid is at most
$(1+1/d)^{d}k\leq ek\leq 3k$. By linearity of expectation, the expected number
of center cells in all grids is at most $ek(L+1)\leq 6kL$. By Markov’s
inequality, the probability that we have more than $100kL$ center cells in all
grids is at most $0.06$.

Proof of Lemma 3.6

$\displaystyle\sum_{p\in Q}s^{\prime}(p)$
$\displaystyle=\sum_{i=0}^{L}\sum_{p\in Q_{i}}10\frac{d^{3}}{T_{i}(o)}$
$\displaystyle=10d^{3}\sum_{i=0}^{L}\frac{1}{T_{i}(o)}\left(\sum_{\text{center
cell }C\in G_{i}}|C\cap Q_{i}|+\sum_{\text{non-center cell }C\in G_{i}}|C\cap
Q_{i}|\right)$ $\displaystyle\leq
10d^{3}\sum_{i=0}^{L}\frac{1}{T_{i}(o)}\left(\sum_{\text{center cell }C\in
G_{i}}1.1T_{i}(o)+\frac{\operatorname{\mathsf{OPT}}}{g_{i}^{2}/(2d)^{2}}\right)$
$\displaystyle\leq 11d^{3}\cdot(\text{\\# of center
cells})+4000d^{3}Lk\cdot\frac{\operatorname{\mathsf{OPT}}}{o}$
$\displaystyle\leq
1100d^{3}Lk+4000d^{3}Lk\cdot\frac{\operatorname{\mathsf{OPT}}}{o}$
$\displaystyle\leq
4000d^{3}Lk\cdot\left(\frac{\operatorname{\mathsf{OPT}}}{o}+1\right),$

where the first step follows from the definition of $s^{\prime}(p)$, the third
step follows from

  1. 1.

if $C\in G_{i}$ and $C\cap Q_{i}\not=\emptyset$, then $|C\cap Q_{i}|=|C\cap
Q|\leq 1.1T_{i}(o)$;

  2. 2.

if $p$ is in a non-center cell $C\in G_{i}$, then
$\operatorname{dist}^{2}(p,Z^{*})\geq g_{i}^{2}/(2d)^{2}$,

the forth step follows from $g_{i}^{2}/d^{2}=o/(100kT_{i}(o))$, the fifth step
follows from that the total number of center cells is bounded by $100kL$.

##  Appendix B Missing Details in Section 4

In this section, we give all the missing details in Section 4.

###  B.1 The Dynamic Point-Cell Storing Data Structure

The following lemma shows the guarantee of Algorithm 3.

######  Lemma B.1.

Given parameters $i\in[L],\alpha,\beta\in\mathbb{N}_{+},\delta\in(0,0.5)$,
Storing$(G_{i},\alpha,\beta,\delta)$ (Algorithm 3) uses $O(\alpha\beta
dL\cdot\log^{2}(\alpha\beta/\delta))$ bits to process a stream
$\\{((p_{1},l_{1}),\pm),((p_{2},l_{2}),\pm),\ldots\\}$ of insertion/deletion
operations of data points. At the end of the stream, if the number of non-
empty cells in $G_{i}$ is at most $\alpha$, then with probability at least
$1-\delta$ it returns the set $\mathcal{C}$ of all the non-empty cells, the
number of points $f(C)$ in each cell $C\in\mathcal{C}$, and the set $S$ of
points in all the non-empty cells that contain at most $\beta$ points. It
returns FAIL otherwise.

######  Proof B.2.

If the number of non-empty cells of $G_{i}$ at the end of the stream is more
than $\alpha$, then according to line 3 of Algorithm 3 and Lemma 4.1,
Algorithm 3 must output FAIL.

Now consider the case when the total number of non-empty cells is at most
$\alpha$. According to Lemma 4.1, with probability at least $1-\delta/4$, line
3 of Algorithm 3 will return the set $\mathcal{C}$ of all the non-empty cells
of $G_{i}$ and the number of points $f(C)$ for each cell $C\in\mathcal{C}$.
For each $C\in\mathcal{C}$ with $|C|\leq\beta$, since
$|\mathcal{C}|\leq\alpha,$ the probability that $\exists j\in[r]$ such that
$\forall C^{\prime}\in\mathcal{C},h_{j}(C^{\prime})\not=h_{j}(C)$ is at least
$1-1/2^{r}\geq 1-\delta/(4\alpha)$ and furthermore the probability that the
$(j,h_{j}(C))$-th copy of Distinct$(\beta,\delta/(2\alpha))$ in line 5 of
Algorithm 3 will output all the points in $C$ is at least
$1-\delta/(2\alpha)$. By taking union bound, the overall probability that
Algorithm 3 does not output FAIL is at most
$1-\delta/4-(\delta/(2\alpha)+\delta/(4\alpha))\cdot\alpha=1-\delta$.

According to Lemma 4.1, the space needed by line 3 of Algorithm 3 is $O(\alpha
dL\cdot\log(\alpha/\delta))$ bits and the space needed of each copy in line 5
of Algorithm 3 is $O(\beta dL\cdot\log(\alpha\beta/\delta))$ bits. Thus, the
total space needed is at most $O(\alpha\beta
dL\cdot\log^{2}(\alpha\beta/\delta))$.

###  B.2 Estimating the Number of Points in Each Cell

Now let us analyze Algorithm 4. We need the following high concentration bound
in our analysis.

######  Theorem B.3 (Bellare and Rompel (1994)).

Let $\lambda$ be an even integer, and let $X$ be the sum of $n$ $\lambda$-wise
independent random variables taking values in $[0,1]$. Let
$\mu=\operatorname*{{\bf{E}}}[X]$ and $a>0$. Then we have

$\Pr\bigg{[}|X-\mu|>a\bigg{]}\leq
8\cdot\bigg{(}\frac{\lambda\mu+\lambda^{2}}{a^{2}}\bigg{)}^{\lambda/2}.$

######  Lemma B.4 (Samples from each cell).

In PointsEstimation$(o,\epsilon,\delta)$ (Algorithm 4), with probability at
least $1-\delta/10$, $\forall i\in\\{0,1,\ldots,L\\}$ with $T_{i}(o)\geq
4\cdot 10^{4}\lambda$, $\forall C\in G_{i}$, we have either

$\displaystyle\sum_{p\in C\cap Q}h_{i}(p)\in|C\cap Q|\cdot\frac{4\cdot
10^{4}\lambda}{T_{i}(o)}\pm 4\cdot 10^{3}\lambda$

or

$\displaystyle\sum_{p\in C\cap Q}h_{i}(p)\in|C\cap Q|\cdot\frac{4\cdot
10^{4}\lambda}{T_{i}(o)}\cdot(1\pm 0.01).$

######  Proof B.5.

Consider a cell $C\in G_{i}$. If $|C\cap Q|\leq T_{i}(o)$, then
$\mu=\operatorname*{{\bf{E}}}\left[\sum_{p\in C\cap Q}h_{i}(p)\right]=4\cdot
10^{4}\lambda|C\cap Q|/T_{i}(o)\leq 4\cdot 10^{4}\lambda.$ According to
Theorem B.3, we have

$\displaystyle\Pr\left[\left|\sum_{p\in C\cap Q}h_{i}(p)-\mu\right|>4\cdot
10^{3}\lambda\right]\leq 8\cdot\left(\frac{4\cdot
10^{4}\lambda^{2}+\lambda^{2}}{(4\cdot
10^{3}\lambda)^{2}}\right)^{\lambda/2}\leq
8\cdot(1/2)^{\lambda/2}\leq(\delta/\Delta^{d})^{5}.$

If $|C\cap Q|>T_{i}(o)$, then $\mu=\operatorname*{{\bf{E}}}\left[\sum_{p\in
C\cap Q}h_{i}(p)\right]=4\cdot 10^{4}\lambda|C\cap Q|/T_{i}(o)>4\cdot
10^{4}\lambda.$ According to Theorem B.3, we have

$\displaystyle\Pr\left[\left|\sum_{p\in C\cap
Q}h_{i}(p)-\mu\right|>0.01\mu\right]\leq
8\cdot\left(\frac{\lambda\mu+\lambda^{2}}{(0.01\mu)^{2}}\right)^{\lambda/2}\leq
8\cdot(1/2)^{\lambda/2}\leq(\delta/\Delta^{d})^{5}.$

By taking union bound over all $i\in\\{0,1,\ldots,L\\}$ and all the cells in
$G_{i}$, the claim is proved.

######  Lemma B.6 (Estimating the number of points in each cell).

If PointsEstimation$(o,\epsilon,\delta)$ (Algorithm 4) does not output FAIL,
then with probability at least $1-\delta/10$, $\forall
i\in\\{0,1,\ldots,L\\},C\in G_{i}$, either $\widehat{f}(C)\in|C\cap Q|\pm
0.1T_{i}(o)$ or $\widehat{f}(C)\in(1\pm 0.01)|C\cap Q|$.

######  Proof B.7.

Suppose PointsEstimation$(o,\epsilon,\delta)$ does not output FAIL. According
to Lemma B.1, $\forall i\in\\{0,1,\ldots,L\\}$ and $\forall C\in G_{i}$,
$f_{i}(C)=\sum_{p\in C\cap Q}h_{i}(p)$. If $T_{i}(o)\leq 4\cdot
10^{4}\lambda$, then $\widehat{f}(C)=f_{i}(C)=\sum_{p\in C\cap
Q}h_{i}(p)=|C\cap Q|$.

Due to Lemma B.4, with probability at least $1-\delta/10$, $\forall
i\in\\{0,1,\ldots,L\\}$ with $T_{i}(o)>4\cdot 10^{4}\lambda$ and $\forall C\in
G_{i}$, either $f_{i}(C)\in|C\cap Q|\cdot\frac{4\cdot
10^{4}\lambda}{T_{i}(o)}\pm 4\cdot 10^{3}\lambda$ or $f_{i}(C)\in|C\cap
Q|\cdot\frac{4\cdot 10^{4}\lambda}{T_{i}(o)}\cdot(1\pm 0.01)$. Thus, either
$\widehat{f}(C)\in|C\cap Q|\pm 0.1T_{i}(o)$ or $\widehat{f}(C)\in(1\pm
0.01)|C\cap Q|.$

######  Lemma B.8 (Samples from each $Q_{i}$).

In PointsEstimation$(o,\epsilon,\delta)$ (Algorithm 4), with probability at
least $1-\delta/10$, $\forall i\in\\{0,1,\ldots,L\\}$ with $T_{i}(o)\geq
4\cdot 10^{4}\epsilon^{-2}\gamma^{-1}\lambda$, $\forall C\in G_{i}$, either

$\displaystyle\sum_{p\in Q_{i}}h^{\prime}_{i}(p)\in|Q_{i}|\cdot\frac{4\cdot
10^{4}\epsilon^{-2}\gamma^{-1}\lambda}{T_{i}(o)}\pm 4\cdot
10^{3}\epsilon^{-1}\lambda$

or

$\displaystyle\sum_{p\in Q_{i}}h^{\prime}_{i}(p)\in|Q_{i}|\cdot\frac{4\cdot
10^{4}\epsilon^{-2}\gamma^{-1}\lambda}{T_{i}(o)}\cdot(1\pm 0.01\epsilon).$

######  Proof B.9.

If $|Q_{i}|\leq\gamma T_{i}(o)$, then
$\mu=\operatorname*{{\bf{E}}}\left[\sum_{p\in
Q_{i}}h_{i}^{\prime}(p)\right]=4\cdot
10^{4}\epsilon^{-2}\gamma^{-1}\lambda|Q_{i}|/T_{i}(o)\leq 4\cdot
10^{4}\epsilon^{-2}\lambda.$ According to Theorem B.3, we have

$\displaystyle\Pr\left[\left|\sum_{p\in
Q_{i}}h_{i}^{\prime}(p)-\mu\right|>4\cdot
10^{3}\epsilon^{-1}\lambda\right]\leq 8\cdot\left(\frac{4\cdot
10^{4}\epsilon^{-2}\lambda^{2}+\lambda^{2}}{(4\cdot
10^{3}\epsilon^{-1}\lambda)^{2}}\right)^{\lambda/2}\leq
8\cdot(1/2)^{\lambda/2}\leq(\delta/\Delta^{d})^{5}.$

If $|Q_{i}|>\gamma T_{i}(o)$, then
$\mu=\operatorname*{{\bf{E}}}\left[\sum_{p\in
Q_{i}}h_{i}^{\prime}(p)\right]=4\cdot
10^{4}\epsilon^{-2}\gamma^{-1}\lambda|Q_{i}|/T_{i}(o)>4\cdot
10^{4}\epsilon^{-2}\lambda.$ According to Theorem B.3, we have

$\displaystyle\Pr\left[\left|\sum_{p\in
Q_{i}}h_{i}^{\prime}(p)-\mu\right|>0.01\epsilon\mu\right]\leq
8\cdot\left(\frac{\lambda\mu+\lambda^{2}}{(0.01\epsilon\mu)^{2}}\right)^{\lambda/2}\leq
8\cdot(1/2)^{\lambda/2}\leq(\delta/\Delta^{d})^{5}.$

By taking union bound over all $i\in\\{0,1,\ldots,L\\}$, the claim is proved.

######  Lemma B.10 ($\widehat{q}_{i}$ can estimate $|Q_{i}|$ well).

If PointsEsitmation$(o,\epsilon,\delta)$ (Algorithm 4) does not output FAIL,
then with probability at least $1-\delta/10$, $\forall
i\in\\{0,1,\ldots,L\\}$, either $\widehat{q}_{i}\in|Q_{i}|\pm
0.1\epsilon\gamma T_{i}(o)$ or $\widehat{q}_{i}\in(1\pm 0.01\epsilon)|Q_{i}|$.

######  Proof B.11.

Suppose PointsEstimation$(o,\epsilon,\delta)$ does not output FAIL. According
to Lemma B.1, $\forall i\in\\{0,1,\ldots,L\\}$, $f_{i}^{\prime}(C)=\sum_{p\in
Q_{i}}h_{i}^{\prime}(p)$. If $T_{i}(o)\leq 4\cdot
10^{4}\epsilon^{-2}\gamma^{-1}\lambda$, then $\widehat{q}_{i}=\sum_{C\in
G_{i}:C\text{ is crucial}}f_{i}^{\prime}(C)=\sum_{p\in
Q_{i}}h_{i}^{\prime}(p)=|Q_{i}|$.

Due to Lemma B.8, with probability at least $1-\delta/10$, $\forall
i\in\\{0,1,\ldots,L\\}$ with $T_{i}(o)>4\cdot
10^{4}\epsilon^{-2}\gamma^{-1}\lambda$, either

$\sum_{C\in G_{i}:C\text{ is
crucial}}f_{i}^{\prime}(C)\in|Q_{i}|\cdot\frac{4\cdot
10^{4}\epsilon^{-2}\gamma^{-1}\lambda}{T_{i}(o)}\pm 4\cdot
10^{3}\epsilon^{-1}\lambda$

or

$\sum_{C\in G_{i}:C\text{ is
crucial}}f_{i}^{\prime}(C)\in|Q_{i}|\cdot\frac{4\cdot
10^{4}\epsilon^{-2}\gamma^{-1}\lambda}{T_{i}(o)}\cdot(1\pm 0.01\epsilon).$

Thus, either $\widehat{q}_{i}\in|Q_{i}|\pm 0.1\epsilon\gamma T_{i}(o)$ or
$\widehat{q}_{i}\in(1\pm 0.01\epsilon)|Q_{i}|$.

######  Lemma B.12 (Number of points sampled from non-center cells).

In PointsEsitmation$(o,\epsilon,\delta)$ (Algorithm 4), with probability at
least $1-\delta/10$, $\forall i\in\\{0,1,\ldots,L\\}$, we have

$\displaystyle\sum_{\text{non-center cell }C\in G_{i}}\sum_{p\in C\cap
Q}h_{i}(p)\leq 4\cdot 10^{3}\lambda+1.01\cdot\frac{4\cdot
10^{4}\lambda}{T_{i}(o)}\sum_{\text{non-center cell }C\in G_{i}}|C\cap Q|$

and

$\displaystyle\sum_{\text{non-center cell }C\in G_{i}}\sum_{p\in C\cap
Q}h_{i}^{\prime}(p)\leq 4\cdot
10^{3}\epsilon^{-1}\lambda+1.01\cdot\frac{4\cdot
10^{4}\epsilon^{-2}\gamma^{-1}\lambda}{T_{i}(o)}\sum_{\text{non-center cell
}C\in G_{i}}|C\cap Q|.$

######  Proof B.13.

The proof is exactly the same as the proofs of Lemmas B.4 and B.8.

######  Lemma B.14.

$\forall i\in\\{0,1,\ldots,L\\}$,

$\displaystyle\sum_{\text{non-center cell }C\in G_{i}}\frac{|C\cap
Q|}{T_{i}(o)}\leq 400k\cdot(\operatorname{\mathsf{OPT}}/o).$

######  Proof B.15.

$\displaystyle\sum_{\text{non-center cell }C\in G_{i}}|C\cap Q|$
$\displaystyle\leq$
$\displaystyle\frac{\operatorname{\mathsf{OPT}}}{(g_{i}/(2d))^{2}}=400kT_{i}(o)\cdot\frac{\operatorname{\mathsf{OPT}}}{o}.$

######  Lemma B.16 (The success probability).

Condition on the number of center cells of all the grids is at most $100kL$.
If $o\in(\operatorname{\mathsf{OPT}}/16,\operatorname{\mathsf{OPT}}]$, then
PointsEstimation$(o,\epsilon,\delta)$ (Algorithm 4) does not output FAIL with
probability at least $1-3\delta/10$.

######  Proof B.17.

Let $o\geq\operatorname{\mathsf{OPT}}/16$, according to Lemma B.14 and Lemma
B.12, with probability at least $1-\delta/10,$ $\forall
i\in\\{0,1,\ldots,L\\}$, we have

$\displaystyle\sum_{\text{non-center cell }C\in G_{i}}\sum_{p\in C\cap
Q}h_{i}(p)\leq 4\cdot 10^{3}\lambda+1.01\cdot 4\cdot 10^{4}\lambda\cdot
6400k\leq 10^{11}kdL\log(1/\delta)$

and

$\displaystyle\sum_{\text{non-center cell }C\in G_{i}}\sum_{p\in C\cap
Q}h_{i}^{\prime}(p)\leq 4\cdot 10^{3}\epsilon^{-1}\lambda+1.01\cdot 4\cdot
10^{4}\epsilon^{-2}\gamma^{-1}\lambda\cdot 6400k\leq
10^{15}\cdot\epsilon^{-3}kL^{2}d^{4}.$

Since the number of center cells is at most $100kL$, the total number of cells
which contains some $p$ with $h_{i}(p)=1$ is at most
$10^{12}kdL\log(1/\delta)\leq\alpha$, and the total number of cells which
contains some $p$ with $h_{i}^{\prime}(p)=1$ is at most
$10^{16}\epsilon^{-3}kL^{2}d^{4}\leq\alpha^{\prime}$. According to Lemma B.1,
with probability at least $1-2\delta/10$, none the call of Storing will return
FAIL. Thus the overall probability that Algorithm 4 does not output FAIL is at
last $1-3\delta/10$.

######  Lemma B.18 (Space of Algorithm 4).

PointsEstimation$(o,\epsilon,\delta)$ (Algorithm 4) uses space at most
$O(k\epsilon^{-3}L^{4}d^{5}\cdot\log^{2}(kLd/(\epsilon\delta)))$ bits.

######  Proof B.19.

The total space used is dominated by the space needed to run $L+1$ copies of
Storing$(G_{i},\alpha^{\prime},1,0.1\delta/L)$ in line 9 of Algorithm 4.
According to Lemma B.1, the total space needed is
$O(L\cdot\alpha^{\prime}dL\log^{2}(L\alpha^{\prime}/\delta))=O(k\epsilon^{-3}L^{4}d^{5}\cdot\log^{2}(kLd/(\epsilon\delta)))$
bits.

###  B.3 Sensitivity Sampling over a Dynamic Stream

Now we analyze Algorithm 5.

######  Fact 5.

If Sampling$(o,\epsilon,\delta)$ (Algorithm 5) does not output FAIL, then line
21 can be implemented, and $p$ is a uniform sample drawn from $Q_{i}$.

######  Proof B.20.

Although $Q_{i}$ cannot be stored explicitly, $\forall p\in Q,$ we are able to
determine whether $p\in Q_{i}$ since we can use $\widehat{f}$ to find all the
crucial cells and check whether $p$ is in a crucial cell of $G_{i}$.

Suppose Sampling$(o,\epsilon,\delta)$ does not output FAIL. According to Lemma
B.1 and the condition in line 12, $\forall j\in[\widehat{m}],$ we have
$\\{(p,j)\mid p\in Q_{i},h_{i,j}(p)=1\\}\subseteq S_{i}$. Since $\forall
x,y\in Q_{i}$, $\Pr[h_{i,j}(x)=1]=\Pr[h_{i,j}(y)=1]$, then the sample $p$ in
line 21 is drawn uniformly from $Q_{i}$.

######  Lemma B.21 (Correctness of Algorithm 5).

Suppose $o\in(0,\operatorname{\mathsf{OPT}}]$. If
Sampling$(o,\epsilon,\delta)$ (Algorithm 5) does not output FAIL, then with
probability at least $1-\delta/5$, the output $S$ by
Sampling$(o,\epsilon,\delta)$ is an $\epsilon$-coreset for $Q$. Furthermore,
the size $|S|$ is at most
$O(k\epsilon^{-2}L^{2}d^{4}\log(kLd)\cdot(\operatorname{\mathsf{OPT}}/o+1))$.

######  Proof B.22.

Due to Lemma B.6 and Lemma B.10, with probability at least $1-\delta/10$,
$\forall C\in\bigcup_{i=0}^{L}G_{i}$, either $\widehat{f}(C)\in|C\cap Q|\pm
0.1T_{i}(o)$ or $\widehat{f}(C)\in(1\pm 0.01)|C\cap Q|$ and $\forall
i\in\\{0,1,\ldots,L\\}$, either $\widehat{q}_{i}\in|Q_{i}|\pm
0.1\epsilon\gamma T_{i}(o)$ or $\widehat{q}_{i}\in(1\pm 0.01\epsilon)|Q_{i}|$,
where $Q_{0},Q_{1},\ldots,Q_{L}$ are defined by using the estimation
$\widehat{f}(\cdot)$ (Algorithm 1 or Algorithm 4). According to Fact 5, the
sampling procedure can be implemented. Then by Theorem666The proof is slightly
different since Theorem 3.2 only claims a constant success probability. See
Section 3.3 for the detailed proof of Theorem 3.2. 3.2, with probability at
least $1-\delta/10$, the output set $S$ is an $\epsilon$-coreset for $Q$. By
taking union bound, with probability $1-\delta/5$, the set $S$ is an
$\epsilon$-coreset for $Q$.

Now let us consider the success probability of Algorithm 5. Since we know the
success probability of PointsEstimation$(o,\epsilon,\delta/2)$ in line 3 of
Algortihm 5 and the success probability of
Storing$(G_{i},\alpha,\beta,0.1\delta/L)$ in line 9, we only need to analyze
the success probability in line 20 of Algorithm 5. To make line 20 succeed, we
need to find enough samples from $Q_{i}$, i.e., we hope that
$\sum_{j=1}^{\widehat{m}}\mathbf{1}(|\\{p\in Q_{i}\mid h_{i,j}(p)=1\\}|>0)$ is
large. In the following analysis, we will show that
$\sum_{j=1}^{\widehat{m}}\mathbf{1}(|\\{p\in Q_{i}\mid h_{i,j}(p)=1\\}|>0)$ is
large. First, we show that the number of samples drawn from level $i$ is
bounded.

######  Lemma B.23 (Number of samples from each level).

Let $I$ be the set computed in Sampling$(o,\epsilon,\delta)$ (Algortihm 5).
With probability at least $1-\delta/10$, $\forall i\in I$, the number of times
that $i$ is chosen in line 19 of Algorithm 5 is at most

$\displaystyle
O\left(\epsilon^{-2}Ld^{4}\log(t^{\prime}/\delta)\cdot\frac{L}{\delta}\cdot\frac{\widehat{q}_{i}}{T_{i}(o)}\right).$

######  Proof B.24.

For $i\in I$, the expected number of times that $i$ is chosen is
$O(m\cdot\widehat{q}_{i}\cdot d^{3}/T_{i}(o)/t^{\prime})$. By Markov’s
inequality, with probability at least $1-\delta/(20L)$, the number of times
that $i$ is chosen in line 19 of Algorithm 5 is at most
$O\left(\epsilon^{-2}Ld^{4}\log(t^{\prime}/\delta)\cdot\frac{L}{\delta}\cdot\frac{\widehat{q}_{i}}{T_{i}(o)}\right).$
By taking union bound over all $i\in I$, we complete the proof.

######  Lemma B.25 (Bounding $t^{\prime}$).

Consider $o\geq\operatorname{\mathsf{OPT}}/16$. Condition on
$\widehat{f}:\bigcup_{i=0}^{L}G_{i}\rightarrow\mathbb{R}_{+}$ (in Algorithm 5)
is good (Lemma B.4), $\widehat{q}_{0},\widehat{q}_{1},\ldots,\widehat{q}_{L}$
(in Algorithm 5) are good (Lemma B.8), and the number of center cells is at
most $100kL$, then we have $t^{\prime}\leq 10^{6}d^{3}Lk$.

######  Proof B.26.

$\displaystyle t^{\prime}$ $\displaystyle=\sum_{i\in I}\widehat{q}_{i}\cdot
10d^{3}/T_{i}(o)$ $\displaystyle\leq\sum_{i\in I}|Q_{i}|\cdot
20d^{3}/T_{i}(o)$ $\displaystyle\leq\sum_{i=0}^{L}|Q_{i}|\cdot
20d^{3}/T_{i}(o)$ $\displaystyle\leq 2\cdot 4000d^{3}Lk\cdot 20$
$\displaystyle\leq 10^{6}d^{3}Lk,$

where the first inequality follows by $\forall i\in
I,\widehat{q}_{i}\geq\gamma T_{i}(o)$ and either $\widehat{q}_{i}\in|Q_{i}|\pm
0.1\epsilon\gamma T_{i}(o)$ or $\widehat{q}_{i}\in(1\pm 0.01\epsilon)|Q_{i}|$,
the second inequality follows by $I\subseteq\\{0,1,\ldots,L\\}$, the third
inequality follows by Lemma 3.6 and $o\geq\operatorname{\mathsf{OPT}}/16$.

######  Lemma B.27 (Number of crucial points in each level).

Consider $o\geq\operatorname{\mathsf{OPT}}/16$. Conditioning on
$\widehat{f}:\bigcup_{i=0}^{L}G_{i}\rightarrow\mathbb{R}_{+}$ (in Algorithm 5)
is good (Lemma B.6) and the number of center cells is at most $100kL$, we
have:

$\displaystyle\frac{|Q_{i}|}{T_{i}(o)}\leq 7000kL.$

######  Proof B.28.

$\displaystyle\frac{|Q_{i}|}{T_{i}(o)}$ $\displaystyle=\sum_{\text{center
crucial cell }C\in G_{i}}\frac{|C\cap Q|}{T_{i}(o)}+\sum_{\text{non-center
crucial cell }C\in G_{i}}\frac{|C\cap Q|}{T_{i}(o)}$ $\displaystyle\leq
110kL+400k(\operatorname{\mathsf{OPT}}/o)$ $\displaystyle\leq 7000kL,$

where the first inequality follows by that the number of center cells is at
most $100kL$, the number points in a crucial cell is at most $1.1T_{i}(o)$ and
Lemma B.14.

######  Lemma B.29 (The number of samples is large).

Consider $o\geq\operatorname{\mathsf{OPT}}/16$. Conditioning on
$\widehat{f}:\bigcup_{i=0}^{L}G_{i}\rightarrow\mathbb{R}_{+}$ (in Algorithm 5)
is good (Lemma B.4), $\widehat{q}_{0},\widehat{q}_{1},\ldots,\widehat{q}_{L}$
(in Algorithm 5) are good (Lemma B.8), and the number of center cells is at
most $100kL$, with probability at least $1-\delta/10$, $\forall i\in I$, we
have:

$\displaystyle\sum_{j=1}^{\widehat{m}}\mathbf{1}(|\\{p\in Q_{i}\mid
h_{i,j}(p)=1\\}|>0)\geq\Omega\left(\epsilon^{-2}Ld^{4}\log\left(\frac{dLk}{\delta}\right)\cdot\frac{L}{\delta}\cdot\frac{\widehat{q}_{i}}{T_{i}(o)}\right).$

######  Proof B.30.

Consider a fixed $i\in I$. $\forall j\in[\widehat{m}],$ by union bound, we
have

$\displaystyle\Pr_{h_{i,j}}\left[\exists p\in
Q_{i},h_{i,j}(p)=1\right]\leq\frac{|Q_{i}|}{10^{4}kLT_{i}(o)}<1,$

where the inequality follows by Lemma B.27. Thus $\lceil
10^{4}kLT_{i}(o)/|Q_{i}|\rceil\leq 2\cdot 10^{4}kLT_{i}(o)/|Q_{i}|$. Let
$b=10\cdot\lceil 10^{4}kLT_{i}(o)/|Q_{i}|\rceil.$ Let
$r=\lfloor\widehat{m}/b\rfloor\geq\widehat{m}\cdot|Q_{i}|/(2\cdot
10^{5}kLT_{i}(o))-1$. Since $i\in I,$ we have
$|Q_{i}|/T_{i}(o)\geq\frac{1}{2}\gamma$. Since $\widehat{m}\geq
10^{9}kL/\gamma$, we have $r\geq\widehat{m}/(4\cdot
10^{5}kL)\cdot|Q_{i}|/T_{i}(o).$ For $s\in[r]$, we can define a random
variable $Y_{s}$,

$\displaystyle Y_{s}=\sum_{j=(s-1)\cdot b+1}^{s\cdot b}\sum_{p\in
Q_{i}}h_{i,j}(p).$

We have $\operatorname*{{\bf{E}}}[Y_{s}]=b\cdot|Q_{i}|/(10^{4}kLT_{i}(o)).$
Thus, $E[Y_{s}]\in[10,20].$ Since $Y_{s}$ is a sum of several (at least)
pairwise independent unit random variables,
$\operatorname*{{\bf{Var}}}[Y_{s}]\leq 20$. Thus, by Chebyshev’s inequality,
we have

$\displaystyle\Pr\left[|Y_{s}-\operatorname*{{\bf{E}}}[Y_{s}]|\geq
9\right]\leq 20/81\leq 0.25.$

Define $X_{s}$ be the random variable such that $X_{s}=\mathbf{1}(Y_{s}\geq
1).$ Then $\operatorname*{{\bf{E}}}\left[\sum_{s\in[r]}X_{s}\right]\geq
0.75r$. By Chernoff bound, we know that

$\displaystyle\Pr\left[\sum_{s\in[r]}X_{s}\leq 0.5r\right]\leq 2^{-r/20}\leq
0.01\delta/L,$

where the last inequality follows by $r\geq\widehat{m}/(4\cdot
10^{5}kL)\cdot\gamma/2\geq 20\log(100L/\delta)$.

Since $\widehat{m}$ is sufficiently large, i.e.,

$\displaystyle\widehat{m}\geq\Omega\left(k\epsilon^{-2}L^{3}d^{4}\log\left(\frac{dLk}{\delta}\right)\cdot\frac{1}{\delta\gamma}\right)\geq\Omega\left(k\epsilon^{-3}L^{4}d^{7}\log\left(\frac{dLk}{\delta}\right)\cdot\frac{1}{\delta}\right),$

we have

$\displaystyle r\geq\widehat{m}/(4\cdot
10^{5}kL)\cdot|Q_{i}|/T_{i}(o)\geq\Omega\left(\epsilon^{-2}Ld^{4}\log\left(\frac{dLk}{\delta}\right)\cdot\frac{L}{\delta}\cdot\frac{\widehat{q}_{i}}{T_{i}(o)}\right),$

where the last inequality follows by $\widehat{q}_{i}=\Theta(|Q_{i}|)$. Notice
that

$\displaystyle\Pr\left[\sum_{j=1}^{\widehat{m}}\mathbf{1}(|\\{p\in Q_{i}\mid
h_{i,j}(p)=1\\}|>0)\geq 0.5r\right]\geq\Pr\left[\sum_{s\in[r]}X_{s}\geq
0.5r\right]\geq 1-0.01\delta/L.$

Thus, with probability at least $1-0.01\delta/L$,

$\displaystyle\sum_{j=1}^{\widehat{m}}\mathbf{1}(|\\{p\in Q_{i}\mid
h_{i,j}(p)=1\\}|>0)\geq\Omega\left(\epsilon^{-2}Ld^{4}\log\left(\frac{dLk}{\delta}\right)\cdot\frac{L}{\delta}\cdot\frac{\widehat{q}_{i}}{T_{i}(o)}\right).$

By taking the union bound over $i\in I$, we complete the proof.

######  Lemma B.31 (Sampling stage succeeds).

Consider $o\geq\operatorname{\mathsf{OPT}}/16$. Conditioning on
$\widehat{f}:\bigcup_{i=0}^{L}G_{i}\rightarrow\mathbb{R}_{+}$ (in Algorithm 5)
is good (Lemma B.4), $\widehat{q}_{0},\widehat{q}_{1},\ldots,\widehat{q}_{L}$
(in Algorithm 5) are good (Lemma B.8), and the number of center cells is at
most $100kL$, if Sampling$(o,\epsilon,\delta)$ does not output FAIL before
line 18 of Algorithm 5, then with probability at least $1-\delta/5$, it will
not output FAIL.

######  Proof B.32.

According to Lemma B.23 and Lemma B.25, with probability at least
$1-\delta/10$, $\forall i\in I$, the sampling procedure will not request too
many samples from level $i$. According to Lemma B.29, with probability at
least $1-\delta/10$, the number of samples needed for each level $i\in I$ is
enough. Thus, with probability at least $1-\delta/5$, the algorithm will not
output FAIL.

######  Lemma B.33 (Samples can fit into the space).

Suppose $o\geq\operatorname{\mathsf{OPT}}/16$. Conditioning on
$\widehat{f}:\bigcup_{i=0}^{L}G_{i}\rightarrow\mathbb{R}_{+}$ (in Algorithm 5)
is good (Lemma B.4), if the total number of center cells is at most $100kL$,
with probability at least $1-\delta/5$, Sampling$(o,\epsilon,\delta)$
(Algorithm 5) will not output FAIL in line 9 nor line 12.

######  Proof B.34.

Consider $i\in\\{0,1,\ldots,L\\}$ and a cell $C\in G_{i}$ which is marked as
crucial by PointsEstimation$(o,\epsilon,\delta/2)$.

$\displaystyle\operatorname*{{\bf{E}}}\left[\sum_{j=1}^{\widehat{m}}\sum_{p\in
C\cap Q}h_{i,j}(p)\right]$ $\displaystyle=\widehat{m}\cdot|C\cap
Q|/(10^{4}kLT_{i}(o))$ $\displaystyle\leq
O(\epsilon^{-3}L^{3}d^{7}\log(dLk/\delta)\delta^{-1}).$

By Theorem B.3,

$\displaystyle\Pr\left[\sum_{j=1}^{\widehat{m}}\sum_{p\in C\cap
Q}h_{i,j}(p)>\operatorname*{{\bf{E}}}\left[\sum_{j=1}^{\widehat{m}}\sum_{p\in
C\cap
Q}h_{i,j}(p)\right]+\epsilon^{-3}L^{3}d^{7}\log(dLk/\delta)\delta^{-1}\right]\leq(\delta/\Delta^{d})^{5}.$

Thus, by taking union bound, with probability at last $1-\delta/10$, $\forall
i\in\\{0,1,\ldots,L\\},$ any cell $C\in G_{i}$ which is marked as crucial, the
total number of points sampled in $C$ is at most $\beta$. Thus, with
probability at least $1-\delta/20$, Sampling$(o,\epsilon,\delta)$ (Algorithm
5) will not output FAIL in line 12.

Consider $i\in\\{0,1\ldots,L\\}$. Let us analyze the number of cells in
$G_{i}$ which contain at least $1$ sample points. The number of points which
are not in the center cell is at most

$\displaystyle\frac{\operatorname{\mathsf{OPT}}}{(g_{i}/(2d))^{2}}\leq
400kT_{i}(o)\cdot\operatorname{\mathsf{OPT}}/o\leq 6400kT_{i}(o).$

Thus, the expected number of sampled points in non-center cell is at most
$O(k\epsilon^{-3}L^{3}d^{7}\log(dLk/\delta)\cdot 1/\delta)$. Since the number
of center cells is at most $100kL$, by Theorem B.3, with probability at least
$1-\delta/(100L)$, the number of cells in $G_{i}$ which contain at least $1$
sample points is $O(k\epsilon^{-3}L^{3}d^{7}\log(dLk/\delta)\cdot 1/\delta)$.
By taking union bound over all $i\in\\{0,1,\ldots,L\\},$ with probability at
least $1-\delta/20$, $\forall i\in\\{0,1,\ldots,L\\}$, the number of sampled
cell in $G_{i}$ is at most $\alpha$.

Due to Lemma B.1, with probability at least $1-\delta/10$, none of the
Storing$(G_{i},\alpha,\beta,0.1\delta/L)$ in line 9 of Algorithm 5 will output
FAIL. By union bound over all the failure probabilities, we complete the
proof.

######  Lemma B.35 (The overall success probability).

Suppose $o\geq\operatorname{\mathsf{OPT}}/16$ and the total number of center
cells is at most $100kL$. With probability at least $1-4\delta/5$,
Sampling$(o,\epsilon,\delta)$ (Algorithm 5) will not output FAIL.

######  Proof B.36.

Due to Lemma B.16, PointsEstimation$(o,\epsilon,\delta/2)$ in line 3 will not
output FAIL with probability at least $1-3\delta/20$. By Lemma B.6 and Lemma
B.8, with probability at least $1-\delta/5$, $\forall i\in\\{0,1,\ldots,L\\},$
either $\widehat{q}_{i}\in|Q_{i}|\pm 0.1\epsilon\gamma T_{i}(o)$ or
$\widehat{q}_{i}\in(1\pm 0.01\epsilon)|Q_{i}|,$ and $\forall C\in G_{i}$,
either $\widehat{f}(C)\in|C\cap Q|\pm 0.1T_{i}(o)$ or $\widehat{f}(C)\in(1\pm
0.01)|C\cap Q|.$ Then by Lemma B.33, with probability at least $1-\delta/5$,
Sampling$(o,\epsilon,\delta)$ will not output FAIL in line 9 nor line 12.
Finally, according to Lemma B.31, with probability at least $1-\delta/5$, the
algorithm does not output FAIL. By taking union bound over all the bad events,
with probability at least $1-3\delta/20-\delta/5-\delta/5-\delta/5\geq
1-4\delta/5$, Sampling$(o,\epsilon,\delta)$ (Algorithm 5) will not output
FAIL.

######  Lemma B.37 (Total space of Algorithm 5).

Sampling$(o,\epsilon,\delta)$ uses space at most
$O(k\epsilon^{-6}L^{8}d^{15}\delta^{-2}\cdot\log^{4}(kLd/(\epsilon\delta)))$
bits.

######  Proof B.38.

According to Lemma B.18, PointsEstimation$(o,\epsilon,\delta/2)$ in line 3 of
Algorithm 5 takes the space
$O(k\epsilon^{-3}L^{4}d^{5}\cdot\log(kLd/(\epsilon\delta)))$ bits. According
to Lemma B.1, line 9 takes the total space:

$\displaystyle O(L\cdot\alpha\beta
dL\cdot\log^{2}(\alpha\beta/\delta))=O(k\epsilon^{-6}L^{8}d^{15}\delta^{-2}\cdot\log^{4}(kLd/(\epsilon\delta))).$

###  B.4 The Final Algorithm

Finally, we prove the guarantees of Algorithm 6, the final algorithm.

######  Lemma B.39 (Correctness and success probability).

With probability at least $0.9$, DynamicCoreset$(\epsilon)$ (Algorithm 6)
outputs an $\epsilon$-coreset for $Q$ and the size of the coreset is at most
$O(k\epsilon^{-2}L^{2}d^{4}\log(kLd))$.

######  Proof B.40.

If $|Q|\leq 10000k$, then according to Lemma 4.1, with probability at least
$0.999$, the entire data set $Q$ will be returned by line 4 in Algorithm 6.

Consider the case when $|Q|\geq 10000k$. According to Lemma 3.5, with
probability at least $0.94$, the total number of center cells is upper bounded
by $100kL$. Now, we condition on this happens. Since $|Q|\geq 10000k$, we know
that $\operatorname{\mathsf{OPT}}\geq 1000k$. There exists $u\in[2dL]$ such
that $o_{u}\in[\operatorname{\mathsf{OPT}}/16,\operatorname{\mathsf{OPT}}]$.
According to Lemma B.35, with probability at least $0.999$,
Sampling$(o_{u},\epsilon,0.001/(dL))$ will not output FAIL. By Lemma B.21,
with probability at least $0.999$, the set $S$ returned by
Sampling$(o_{u},\epsilon,0.001/(dL))$ is an $\epsilon$-coreset and $|S|\leq
O(k\epsilon^{-2}L^{2}d^{4})$. Thus, with probability at least $0.998$,
DynamicCoreset$(\epsilon)$ (Algorithm 6) will not output FAIL. Consider
another $u^{\prime}<u$. If Sampling$(o_{u^{\prime}},\epsilon,0.001/(dL))$ does
not output FAIL, and the set $S^{\prime}$ returned has size at most $h$, then
according to Lemma B.21, with probability at least $1-0.001/(dL),$
$S^{\prime}$ is an $\epsilon$-coreset for $Q$. By taking union bound over all
the such $u^{\prime}$, then with probability at least $0.999$, $S^{*}$
returned by Sampling$(o_{u^{*}},\epsilon,0.001/(dL))$ is an $\epsilon$-coreset
for $Q$. By taking union bound over all the bad events, we complete the proof.

######  Lemma B.41 (Total space needed for Algortihm 6).

DynamicCoreset$(\epsilon)$ (Algorithm 6) uses space at most
$O(k\epsilon^{-6}L^{11}d^{18}\log^{4}(kLd/\epsilon))$ bits.

######  Proof B.42.

DynamicCoreset$(\epsilon)$ (Algorithm 6) runs $\Theta(dL)$ copies of
Sampling$(o_{u},\epsilon,0.001/(dL))$. By Lemma B.37, the total space needed
is

$\displaystyle O(dL\cdot
k\epsilon^{-6}L^{8}d^{15}\cdot(dL)^{2}\cdot\log^{4}(kLd/\epsilon))=O(k\epsilon^{-6}L^{11}d^{18}\log^{4}(kLd/\epsilon))$

bits.

Proof of Theorem 4.2 The algorithm is shown by Algorithm 6. Lemma B.39 shows
the correctness and the success probability of the algorithm. Lemma B.41 shows
the total space needed by the algorithm.

##  Appendix C Why Do Previous Techniques Fail?

In this section, we describe some previous techniques in more detail and
explain why they fail in our setting.

#### Uniform sampling method.

(Frahling et al., 2005) is one of the early papers using sampling procedures
to solve dynamic streaming geometric problems. They showed that it is possible
to use point samples from a dynamic point set to solve several geometric
problems, e.g., Euclidean Minimum Spanning Tree. However, they only showed how
to implement _uniform_ sampling by using counting distinct elements and
subsampling procedure as subroutines. In our setting, we require different
sampling probabilities for different points. Although the bottom-level uniform
sampling scheme of ours is similar to theirs, our overall sampling method is
more complicated.

#### Estimating the cost.

Indyk (2004) used a critical observation to _estimate_ the cost of $k$-median,
that is: let $Z$ be a set of centers and $P$ be the point set, then
$\operatorname{cost}(Z,P)=\int_{0}^{\infty}|P-B(Z,r)|\mathrm{d}r$, where
$B(Z,r)$ is the union of balls of radius $r$ centered at all points in $Z$.
Then this integration is approximated by a summation with logarithmic levels,
i.e.,
$\int_{0}^{\infty}|P-B(Z,r)|\mathrm{d}r\approx\sum_{i=0}^{\infty}\big{|}P-B(Z,r^{(i+1)})\big{|}\cdot\left(r^{(i+1)}-r^{(i)}\right)$,
where $r^{(i)}=O(\epsilon(1+\epsilon)^{i})$. The critical part is to estimate
$\big{|}P-B(Z,r^{(i)})\big{|}$. Indyk (2004) constructed a counting data
structure based on grids with side length $O\left(r^{(i)}\right)$. Then every
input point is snapped to a grid point. To obtain sufficiently accurate
estimates for all $\left|P-B(Z,r^{(i)})\right|$, the data structure needs to
query $|Z|/\epsilon^{O(d)}$ many grid points per $Z$. Such a data structure is
implemented using pair-wise independent hash functions, and uses memory
$|Z|/\epsilon^{O(d)}$. Notice that this method only gives an _estimate_ of the
cost, and does not construct a coreset. In order to obtain a $k$-median
solution, an exhaustive search is needed. Furthermore, this technique fails to
extend to $k$-means which does not have an integration formula for the cost
function.

#### Exponential size coreset.

Frahling and Sohler (2005) constructed an $\epsilon$-coreset of size
$k\epsilon^{-O(d)}$ for $k$-means and $k$-median. They also used the same grid
structure as we use. A cell is marked as “heavy” if the cell contains enough
points such that moving all points in the cell to the center of this cell
incurs too much error in the optimal cost of $k$-means/median. Since the side-
lengths of cells decrease as level increases, the number of points required to
have this effect becomes larger. Eventually, all cells are non-heavy after
some level. As such we also have a tree of heavy cells. The coreset is
constructed by looking at each heavy cell and assigning each point in its non-
heavy children cells to its center. It turns out that if we want an
$\epsilon$-coreset, the threshold of non-heavy cells is exponential in $d$,
i.e., each non-heavy cell in level $i$ cannot contain more than
$\widetilde{O}\left(\epsilon^{O(d)}\cdot\operatorname{\mathsf{OPT}}/2^{i}\right)$
points. This small threshold gives rise to
$\widetilde{O}\left(1/\epsilon^{O(d)}\right)$ many heavy cells.

#### Insertion-only streams.

Many of the previous _insertion-only_ streaming coreset construction
algorithms (e.g., (Feldman and Schulman, 2012)) heavily depend on a “merge-
reduce” technique, i.e. reading some points in the stream, constructing a
coreset, reading another part, constructing a new coreset, and then merging
the two coresets. This procedure is repeated until the stream ends. This
technique works well in the insertion-only streaming model, but it fails
immediately when deletions are allowed. Although Braverman et al. (2016) gave
a new framework other than merge-reduce, their algorithm relies on a non-
deleting structure of data streams as well.

Figure 3: Telescope sum (Braverman et al., 2017) fails for $k$-means. In the
$k$-median problem, for a fixed set of centers $Z$, the total cost can be
written as a telescope sum $\sum_{p\in
P}(\operatorname{dist}(c^{i}_{p},Z)-\operatorname{dist}(c^{i-1}_{p},Z))$. For
each piece,
$|\operatorname{dist}(c^{i}_{p},Z)-\operatorname{dist}(c^{i-1}_{p},Z)|$ is
always upper bounded by $\operatorname{dist}(c^{i-1}_{p},c^{i}_{p})$ which is
independent from the choice of $Z.$ However, in the $k$-means problem, the
telescope sum of the total cost is $\sum_{p\in
P}(\operatorname{dist}(c^{i}_{p},Z)^{2}-\operatorname{dist}(c^{i-1}_{p},Z)^{2})$.
For each piece, the upper bound of
$|\operatorname{dist}(c^{i}_{p},Z)^{2}-\operatorname{dist}(c^{i-1}_{p},Z)^{2}|$
may depend on the location of $Z$, and it can be larger than $\Delta$ in the
worst case.

#### Algorithm for $k$-median only.

Although some $k$-median coreset construction techniques can be easily
extended to $k$-means (see e.g. (Feldman and Schulman, 2012; Braverman et al.,
2016)), those constructions can only be implemented in the insertion-only
streaming model. Braverman et al. (2017) gave a $k$-median coreset
construction in the dynamic streaming model, but their construction cannot be
extended to $k$-means directly, as we explain now. Their $k$-median algorithm
heavily relies on writing the cost of each point as a telescope sum. For
example, we consider the $1$-median problem. let $z$ be a candidate center
point and $p\in P$ be a point, then
$\operatorname{dist}(p,z)=\operatorname{dist}(p,z)-\operatorname{dist}(c^{L-1}_{p},z)+\operatorname{dist}(c^{L-1}_{p},z)-\operatorname{dist}(c^{L-2}_{p},z)+\cdots-\operatorname{dist}(c^{0}_{p},z)$,
where each $c^{i}_{p}$ is the center of the cell in the $i$-th level
containing $p$. Therefore, the total $1$-median cost $\sum_{p\in
P}\operatorname{dist}(p,z)$ of point set $P$ on $z$ can be split into $L$
pieces, i.e., $\sum_{p\in
P}(\operatorname{dist}(c^{i}_{p},z)-\operatorname{dist}(c^{i-1}_{p},z))$ for
each $i\in[L]$. Braverman et al. (2017) estimated each of the $L$ pieces by
sampling points, i.e., let $S^{i}$ be the samples in the $i$-th level, then
the estimator of $\sum_{p\in
P}(\operatorname{dist}(c^{i}_{p},z)-\operatorname{dist}(c^{i-1}_{p},z))$ is
$\sum_{p\in
S^{i}}(\operatorname{dist}(c^{i}_{p},z)-\operatorname{dist}(c^{i-1}_{p},z))/\zeta_{p}^{i}$
where $\zeta_{p}^{i}$ is the probability that point $p$ is sampled. A crucial
observation is that we have
$|\operatorname{dist}(c^{i},z)-\operatorname{dist}(c^{i-1},z)|\leq\Delta/2^{i}$
– the cell size in level $i$ which is independent of the location of $z$.
Using this nice upper bound on
$|\operatorname{dist}(c^{i},z)-\operatorname{dist}(c^{i-1},z)|$, Braverman et
al. (2017) applied Bernstein inequality to get high concentration of the
estimator $\sum_{p\in
S^{i}}(\operatorname{dist}(c^{i}_{p},z)-\operatorname{dist}(c^{i-1}_{p},z))/\zeta_{p}^{i}$
with only $\widetilde{O}(1/\epsilon^{2})$ samples per level. However, this
framework does not work for $1$-means even though one can still write the
telescope sum structure
$\sum_{p}(\operatorname{dist}^{2}(c^{i}_{p},z)-\operatorname{dist}^{2}(c^{i-1}_{p},z))$
and can still setup an estimator $\sum_{p\in
S^{i}}(\operatorname{dist}^{2}(c^{i}_{p},z)-\operatorname{dist}^{2}(c^{i-1}_{p},z))/\zeta_{p}^{i}$.
But
$|\operatorname{dist}^{2}(c_{p}^{i},z)-\operatorname{dist}^{2}(c_{p}^{i-1},z)|$
is not upper bounded by the cell size anymore. Instead, it depends on the
location of $z$. For example, it can be as large as
$|\operatorname{dist}^{2}(c_{p}^{i},z)-\operatorname{dist}^{2}(c_{p}^{i-1},z)|\geq\Delta$.
See Figure 3. If we apply Bernstein inequality here, we will need too many
samples to save any space.