Adaptive k-center and diameter estimation in sliding windows

In the standard static sequential setting, it is well known that for general metric space the k-center problem is NP-hard, admits a 2-approximation algorithm, and, for any \(\epsilon > 0\), it is not \((2-\epsilon )\)-approximable unless P=NP [20].

The problem has also been studied in the fully dynamic setting where the input pointset changes dynamically through insertions of new points or deletions of existing points, and, at any time, the algorithm must be able to return an accurate solution for the current pointset in a time substantially smaller than the time required to compute the solution from scratch. In [13] the authors developed a \((2 + \epsilon )\)-approximation algorithm for the fully dynamic k-center problem on general metric spaces, with update time independent of the input size. For a given query point x, the algorithm can establish whether x is a center in constant time, and return the cluster of x (i.e., all points whose closest center is x) in time proportional to the cluster size. These results have been recently improved in [21] for spaces of constant doubling dimension using a navigating net data structure, and in [5] for general metric spaces using a reduction to the fully-dynamic maximal independent set problem. However, we remark that these fully dynamic algorithms store in memory a number of points linear with the size of the set of interest, as they rather target good query time/approximation tradeoffs, irrespective of the memory usage. For this reason they cannot be utilized in the sliding window model, where the size of the working memory, which is the premium resource to be optimized, must be substantially smaller than (and possibly independent of) the size of the set of interest.

In the standard streaming model, McCutchen and Khuller [33], and, independently, Guha [23], presented algorithms which maintain a \((2 +\epsilon )\)-approximation to the k-center problem for the entire set of points processed from the beginning of the stream, using working memory polynomial in k and \(1/\epsilon \). In the more restrictive sliding window model, which is the focus of this paper, Cohen-Addad et al. [14] presented an algorithm which is able to compute a \((6+\epsilon )\)-approximation to the k-center problem for the current window, from only \(O\left( k\epsilon ^{-1}\log \alpha \right) \) points stored in the working memory, where \(\alpha \) is the aspect ratio of the entire stream, that is, the ratio between the maximum and minimum distance between any two points of the stream. At any time, the algorithm requires \(O\left( k\epsilon ^{-1}\log \alpha \right) \) update time for handling the new point arrived from the stream, and \(O\left( k^2\epsilon ^{-1}\log \alpha \right) \) time to return the approximate solution for the current window. One of the practical limitations of this algorithm is that it assumes prior knowledge of the aspect ratio \(\alpha \), thus the algorithm is inapplicable for unknown or unbounded values of \(\alpha \). In the same paper, the authors also show that, for general metric spaces, any algorithm for the 2-center problem that achieves an approximation ratio less than 4 requires working memory of size \(\varOmega \left( N^{1/3}\right) \), where N is the window length. In a recent unpublished manuscript, Kim [28] improved the result in [14] for Euclidean spaces, by presenting an algorithm which attains a \((2 + 2\sqrt{3} +\epsilon )\)-approximation through a coreset-based approach. The algorithm makes crucial use of specific properties of Euclidean spaces, hence, it is not immediately portable to general spaces. The author also claims that a \((2 + \epsilon )\)-approximation is achievable for constant-dimensional Euclidean spaces, and that the algorithm can be made oblivious to the aspect ratio \(\alpha \). However, due to the missing details, it is not immediate to fully reconstruct these stated improvements.

For what concerns diameter estimation, it is shown in [23] that, in the streaming setting, in order to approximate the diameter within any factor strictly less than 2 for general metrics, a working memory at least proportional to the size of the stream is required. For Euclidean spaces of low dimension d, there is a streaming \((1+\epsilon )\)-approximate algorithm requiring \(O\left( (1/\epsilon )^{(d-1)/2}\right) \) working memory [2], while for streams of higher dimensionality [3] presents an algorithm returning \((\sqrt{2}+\epsilon )\)-approximate solutions using \(O\left( d \epsilon ^{-3}\log (1/\epsilon )\right) \) working memory, and [27] presents an algorithm which can approximate the diameter within a factor \(c > \sqrt{2}\) using \(O\left( d n^{1/(c^2-1)} \log n\right) \) working memory, where n is the size of the stream. A naive 2-approximation for the diameter of the entire stream is attainable in constant working memory by simply accumulating the maximum distance of all points in the stream from the first one. However, this approach cannot be effectively used in the sliding window model, because of the difficulty of maintaining the maximum distance from the first point of each window.

In [14], a streaming algorithm under the sliding window model is presented which, for any constant \(\epsilon > 0\), is able to return a \((3+\epsilon )\)-approximation to the diameter of the current window in general metric spaces using working memory of size \(O\left( \log (\alpha )/\epsilon \right) \), where, again, \(\alpha \) represents the aspect ratio of the entire stream and must be known in advance. In the same paper, the authors prove that, under reasonable assumptions, obtaining an approximation ratio less than 3 in general spaces requires \(\varOmega \left( N^{1/3}\right) \) working memory, where N is the length of the window. For Euclidean spaces of dimension d, a \((1+\epsilon )\)-approximation algorithm in the sliding window model is presented in [18], which uses a working memory of \(O\left( (1/\epsilon )^{(d+1)/2} \log ^3 N(\log \alpha + \log \log N+(1/\epsilon ))\right) \) bits. For constant d, the working memory requirement has been improved to \(O\left( (1/\epsilon )^{(d+1)/2} \log (\alpha /\epsilon )\right) \) [12].

For the smallest enclosing ball problem, which is closely related to the diameter estimation, [3] presents a streaming algorithm that can maintain a \(((1+\sqrt{3})/2+\epsilon )\)-approximate solution using \(O\left( d \epsilon ^{-3}\log (1/\epsilon )\right) \) working memory. In the more restrictive sliding window model, only a \((9.66+\epsilon )\)-approximation is known [42] which uses sub-polynomial working memory.

In the realm of large graph analytics, diameter approximation (under the shortest path metric) has been extensively addressed in the distributed setting (see [8, 39] and references therein).

Another relevant variation on the diameter estimation problem is the computation of the \(\alpha \)-effective diameter, which is defined as the \(\alpha \)-th quantile of the distances between all pairs of elements. This concept was first introduced in [34] as a noise-robust alternative to diameter in the context of network analysis, but can be easily generalized to arbitrary metric spaces. Recently, both [37] and [17] independently presented sliding window algorithms for the effective diameter estimation problem in general metric spaces.

Finally, the sliding window model has recently been addressed in a large number of research papers, which provide algorithms for a wide variety of optimization problems, including k-means and k-medians [6], diversity maximization [7], k-center with outliers [17, 37], submodular optimization [19], and heavy hitters [41].

In this work, we present streaming algorithms for the k-center and diameter estimation problems under the sliding window model. Our algorithms are coreset based, in the sense that they maintain a small subset of representative points embodying an accurate solution for the current window. More specifically, our algorithms rely on the data structures used in [14] to obtain an initial reasonable estimate of the optimal k-center radius, or the diameter, for the current window. These structures are paired with additional ones which leverage the initial estimate to maintain a coreset containing better representatives for the points of the current window. The working memory used by the algorithms is analyzed as a function of k, of a precision parameter \(\epsilon \), related to the desired approximation guarantee, and of the doubling dimension and of the aspect ratio of the current window. The doubling dimension, which is formally defined in Sect. 2, generalizes the notion of Euclidean dimensionality, and, as our results show, is related to the increasing difficulty of approximating the solution to the above problems when its value grows.

Consider a stream S of points from a metric space under the sliding window model. Let \(\epsilon >0\) denote a fixed, user-defined, precision parameter, and let \(\alpha _W\) and \(D_W\) denote, respectively, the aspect ratio and the doubling dimension of the current window W. The two main theoretical results in this paper are the following:It is important to remark that our algorithms are fully oblivious to both the aspect ratio \(\alpha _W\) and to the doubling dimension \(D_W\), in the sense that these values are not used explicitly by the algorithms but they are only employed to analyze their space and time requirements. This is a crucial feature since, in practice, estimates for \(\alpha _W\) and \(D_W\) would be very difficult to obtain. Moreover, as desirable in the sliding window model, the amount of working memory used by the algorithms is independent of the window length, and, for constant \(\epsilon \) and \(D_W\), they grow asymptotically only as a function of \(\alpha _W\) and k (resp., only as a function of \(\alpha _W\)), for the k-center (resp., diameter) problem.

The main improvements of our algorithms with respect to the state-of-the-art for general metric spaces [14] are:Finally, to gauge the practicality of our approach, we implemented our algorithms and the ones by [14], and compared their performance. The experiments provide clear evidence that, when endowed with similar amounts of working memory, on real-world datasets almost always our algorithms yield significantly better approximation with comparable update and query times.

A preliminary version of this work appeared in the Proceedings of the 7th IEEE International Conference on Data Science and Advanced Analytics, (DSAA 2020) [36]. The novel contributions of this work with respect to the preliminary conference version are the following:

The rest of the paper is organized as follows. Section 2 defines the problems formally, and introduces a number of technical notions which will be used throughout the paper. Section 3.1 contains the description and the analysis of the algorithm for the k-center problem. In particular, Sects. 3.1 and 3.2 describe and analyze a simpler version of the algorithm assuming that the aspect ratio of the entire stream be known. Section 3.3 shows how to make the algorithm oblivious to the aspect ratio, and how to weaken the dependence from the aspect ratio of the entire stream to the one of current window. Section 4 describes and analyzes our algorithm for diameter estimation. Section 5 presents the experimental results. Finally, Sect. 6 offers some concluding remarks.

We consider the k-center problem for a target number k of centers, an input stream S, and a window length N. Let \({\textit{minDist}}\) and \({\textit{maxDist}}\) denote, respectively, the minimum and maximum distances between any two distinct points of S. To simplify the presentation of the algorithm, we assume that the values \({\textit{minDist}}\) and \({\textit{maxDist}}\), hence the aspect ratio of S \(\alpha = {\textit{maxDist}}/{\textit{minDist}}\) are known to the algorithm.

For each point p we define its Time-To-Live (TTL), denoted by \(\mathrm{TTL}(p)\), as \(N-(t-t(p))\), where t is the current time. When p arrives (\(t=t(p)\)), its TTL is N, the window length, and, from that time on, \(\mathrm{TTL}(p)\) decreases of one unit at every new arrival. To avoid repeated updates of the TTL of points stored in the working memory, we assume that with each point p in the working memory we store the value t(p), which allows to immediately compute its TTL, given the current time t and N. We say that a point p expires when it leaves the current window W, that is, when \(\mathrm{TTL}(p) = 0\). In the analysis we will also consider points with negative TTL, that is, points that have expired at some previous time step.

For a user-defined constant \(\beta >0\), letand note that \(|\varGamma | = O\left( \log (\alpha )/\log (1+\beta )\right) \). As in [14], our algorithm runs several parallel instances, where each instance uses a different value \(\gamma \in \varGamma \) as a guess of the optimal radius of a clustering of the current window. For each guess \(\gamma \), the algorithm maintains two types of points belonging to the current window W: validation points (v-points for short) which enable to assess whether \(\gamma \) is a constant approximation to the optimal radius \(\mathrm{OPT}_{k,W}\), and coreset points (c-points for short) which are those from which the coreset is extracted.

For each \(\gamma \in \varGamma \), validation points are in turn organized into three (not necessarily disjoint) sets, namely \(AV_{\gamma }\), \(RV_{\gamma }\) and \(OV_{\gamma }\). Coreset points are similarly partitioned into sets \(A_{\gamma }\), \(R_{\gamma }\) and \(O_{\gamma }\). The sets of validation points serve the same purpose as those used in [14]. In broad terms, the set \(AV_{\gamma }\) (attraction v-points), whose size is upper bounded by \(k+2\), contains centers of clusters of radius at most \(2 \gamma \), which cover all points of W when \(\gamma \) is a valid guess for \(\mathrm{OPT}_{k,W}\) (that is, \(\mathrm{OPT}_{k,W}\le \gamma \)). We say that a point p is v-attracted by \(v \in AV_{\gamma }\) if \(\mathrm {dist}(p, v) \le 2\gamma \). The set \(RV_{\gamma }\) (representative v-points) contains, for each \(v \in AV_{\gamma }\), its representative \(\mathrm{repV}_{\gamma }(v)\), defined as the newest point (that is, the point with the largest \(\mathrm{TTL}\)) among those v-attracted by v. When v expires, its representative \(\mathrm{repV}_{\gamma }(v)\) becomes an orphan, and it is moved to the set \(OV_{\gamma }\) (orphan v-points).

Let \(\epsilon >0\) be a user-defined precision parameter. The three sets of coreset points are used to refine the coverage provided by the validation points, so to make sure that, for valid guesses of \(\gamma \), they contain an \(\epsilon \)-coreset for the current window. Let \(\delta = \epsilon /(1+\beta )\). The set \(A_{\gamma }\) (attraction c-points) contains centers that refine the clusters around the attraction v-points by reducing their radius by a factor \(O\left( \delta \right) \). We say that a point p is c-attracted by \(a \in A_{\gamma }\) if \(\mathrm {dist}(p, a) \le \delta \gamma /2\). The sets \(R_{\gamma }\) and \(O_{\gamma }\) play, for c-points, the same role played by \(RV_{\gamma }\) and \(OV_{\gamma }\) for v-points. Thus, the set \(R_{\gamma }\) (representative c-points) contains a representative \(\mathrm{repC}_{\gamma }(a)\) for each \(a \in A_{\gamma }\), which is the newest point among those c-attracted by a. When a expires, its representative \(\mathrm{repC}_{\gamma }(a)\) becomes an orphan and it is moved to the set \(O_{\gamma }\) (orphan c-points).

Observe that a point q can be a representative for several attraction v-points (resp., c-points). In that case, we assume that a distinct copy of q is maintained in \(RV_{\gamma }\) (resp., \(R_{\gamma }\)), one for each \(v \in AV_{\gamma }\) (resp., \(a \in A_{\gamma }\)) such that \(q=\mathrm{repV}_{\gamma }(v)\) (resp., \(q=\mathrm{repC}_{\gamma }(a)\)).

At every time step, a number of points, including those that expires at that step, are removed from the sets of validation and coreset points, so to keep their sizes under control. The interplay between validation and coreset points is the following. At any time t, the validation points enable to identify a suitable guess \({\hat{\gamma }}\) which is within a constant factor from the optimal value \(\mathrm{OPT}_{k,W}\). Then, the set \(R_{{\hat{\gamma }}}\cup O_{{\hat{\gamma }}}\) provides a good coreset from which an accurate final solution to k-center for W can be computed, using algorithm gon.

Our approach is described in detail by the following pseudocode, which consists of three procedures: \(\textsc {update}(p)\) describes the processing of each point p of the stream; \(\textsc {insertValidation}(p,\gamma )\) is invoked inside \(\textsc {update}(p)\) when p must be added to \(AV_{\gamma }\); finally, \(\textsc {query}()\), if invoked at time t, returns the coreset where algorithm gon can be run to return the solution.

We remark that values of \(\delta \ge 4\) would be uninteresting since, in this case, the coreset points would not offer any refinement over the coverage provided by the validation points. Therefore, in what follows, we assume that \(\epsilon \) and \(\beta \) are fixed so that \(\delta \le 4\).

Suppose that Procedure \(\textsc {update}(p)\) is applied to every point p of the input stream S, upon arrival. In this section, we show that, at any time, Procedure \(\textsc {query}\) (if invoked after \(\textsc {update}(p)\) has finished processing the latest point p arrived) returns an \(\epsilon \)-coreset for the current window W, and that, by running gon on such a coreset, a \((2+\epsilon )\)-approximate solution to the k-center problem for W is obtained. Moreover, we will analyze the amount of working memory the time required to process each point of the stream.

The following technical lemma states the main invariants maintained by Procedure \(\textsc {update}\), which will be crucial for the analysis.

Consider a time step t and let \(T\) be the set of points returned by Procedure \(\textsc {query}\) invoked after the execution of \(\textsc {update}(p)\), where p is the t-th point of the stream. Let also W be the current window containing p as its last point. We have:

The next theorem establishes the approximation factor of our algorithm.

The next two theorems establish the space and time requirements of our algorithm.

We remark that the first term in the running time of Procedure \(\textsc {query}()\) can be improved to \(O\left( k^2 \log (\log (\alpha )/\log (1+\beta ))\right) \), by using binary search over the values of \(\varGamma \).

The following theorem summarizes the main features of our algorithm.

We remark that the amount of working memory required by the algorithm to analyze the entire stream S will depend on the maximum value of \(D_W\), which is upper bounded by the doubling dimension of the entire stream but can in fact be substantially smaller.

For convenience, the algorithm presented in Sect. 3.1 assumed explicit knowledge of the aspect ratio \(\alpha \) of the entire stream S. In this section, we show how to make the algorithm oblivious to the aspect ratio, while keeping the same approximation quality, time and space requirements. In fact, the analysis will also show that the dependence on \(\alpha \) of the time and space requirements of the oblivious algorithm can be weakened into a dependence on the value \(\alpha _W\) the aspect ratio restricted to the current window W.

We observe that the knowledge of \(\alpha \) required by the algorithm presented in Sect. 3.1 serves solely the purpose of identifying a spectrum of feasible values for the optimal cluster radius. This is reflected in the definition of \(\varGamma \), which contains a geometric progression of values spanning the interval between the minimum and maximum distance of any two points of the stream. In the oblivious version, at any time t the algorithm maintains an analogous set \(\varGamma _t\), spanning an interval delimited by a lower bound and an upper bound to the radius of the optimal clustering for the current window W.

Let \(p_1, p_2, \ldots \) be an enumeration of all points of the stream S based on the arrival order. At every time \(t > k\), let \(r_t\) be the minimum pairwise distance between the last \(k+1\) points of the stream (\(p_{t-k}, \ldots , p_{t-1}, p_t\)). It is easy to see that, for the current window W, \(\mathrm{OPT}_{k,W} \ge r_t/2\). We require that, together with the other structures, the algorithm stores the last \(k+1\) points arrived and maintains the value \(r_t\), which can be computed with an extra \(O\left( k^2\right) \) operations per step.

We also require that the algorithm maintains a tight upper bound on the diameter \(\varDelta _W\) of the current window W. More precisely, we require that the algorithm maintains, at any time t, a value \(M_t\) such that \(M_t \ge \varDelta _W\), with \(M_t = \varTheta \left( \varDelta _W\right) \). To ease presentation, let us assume for now that \(M_t\) is available. At the end of this subsection, we will show how to augment the algorithm so that \(M_t\) can indeed be efficiently computed at each step.

Let the values \(\beta \), \(\epsilon \) and \(\delta =\epsilon /(1+\beta )\) be defined as in Secti. 3.1, and recall that we assumed that \( \delta \le 4\) since larger values of \(\delta \) are uninteresting for our algorithm. We defineand observe that the definition of \(\varGamma _t\) is independent of \(\alpha \). The structure of the \(\alpha \)-oblivious algorithm is identical to the one presented in the previous subsections, except that at each time t, the set of guesses \(\varGamma _t\) substitutes the fixed set of guesses \(\varGamma \). The following claim shows that at any step t, it is sufficient that the algorithm maintains structures for guesses \(\gamma \) belonging to \(\varGamma _t\).

We now show how to modify the algorithm so that, without the knowledge of \(\alpha \), at the end of each step t it is able to maintain the sets \(AV_\gamma \), \(RV_\gamma \), \(OV_\gamma \), \(A_\gamma \), \(R_\gamma \), and \(O_\gamma \) satisfying the invariants stated in Lemma 1, limited to the guesses \(\gamma \in \varGamma _t\). Suppose that this is the case for up to some time \(t-1 > k\) and consider the arrival of \(p_t\). First, the algorithm computes the new values \(r_t\) (as described above) and \(M_t\) (to be described later), and removes all sets relative to values of \(\gamma \in \varGamma _{t-1}-\varGamma _t\). Then, if \(r_t < r_{t-1}\), for each \(\gamma \in \varGamma _t\) with \(\gamma < \min \varGamma _{t-1}\), the algorithm sets \(AV_\gamma = \{p_{t-k-1}, \ldots , p_{t-1}\} = RV_\gamma = A_\gamma = R_\gamma \) and \(OV_\gamma = O_\gamma = \emptyset \). It is easy to argue that, for these values of \(\gamma \), these sets satisfy the invariants of Lemma 1 at the end of step \(t-1\). Also, if \(M_t > M_{t-1}\), then for each \(\gamma \in \varGamma _t\) with \(\gamma > \max \varGamma _{t-1}\), the algorithm sets \(AV_\gamma = \{p_{t-1}\} = RV_\gamma = A_\gamma = R_\gamma \) and \(OV_\gamma = O_\gamma = \emptyset \). Again, for these values of \(\gamma \), the sets satisfy the invariants of Lemma 1 at the end of step \(t-1\), since for every point q in the window at that time we have \(\mathrm{dist}(q, RV_\gamma ) = \mathrm{dist}(q, R_\gamma ) = \mathrm{dist}(q, p_{t-1}) \le M_{t-1} \le \delta \gamma /2 \le 2 \gamma \le 4\gamma \), since we are assuming \(\delta \le 4\).

At this point, for every \(\gamma \in \varGamma _t\) the algorithm has available sets \(AV_\gamma \), \(RV_\gamma \), \(OV_\gamma \), \(A_\gamma \), \(R_\gamma \), and \(O_\gamma \) which satisfy the invariants of Lemma 1 at the end of step \(t-1\). Then, it is sufficient to run \(\textsc {update}(p_t)\) to complete step t.

Computation of \(M_t\) It remains to show how to compute \(M_t\) at each step. To this purpose, we require that, for every \(\gamma \in \varGamma _t\), a separate concurrent process to the main algorithm described above maintains a set of validation points for \(k=1\), which we refer to as \(AV^{(1)}_\gamma \), \(RV^{(1)}_\gamma \), \(OV^{(1)}_\gamma \). Clearly, for each step \(t \le k+1\), maintaining these three sets and an upper bound \(M_t\) to \(\varDelta _W\) is trivial. Suppose now that these sets are available at the end of some step \(t-1 > k\), for every \(\gamma \in \varGamma _{t-1}\). and consider the arrival of \(p_t\). We operate as follows. We first compute \(r_t\). Then, for each \(\gamma = (1+\beta )^i\), with \(i \ge \lfloor \log _{1+\beta } r_t/2 \rfloor \), we perform the following sequence of steps until a given value \({\hat{\gamma }}\) is determined: Observe that this procedure is akin to the search for a feasible value of \(\gamma \) performed by Procedure query, and will surely stop at a value \({\hat{\gamma }} = O\left( \varDelta _W\right) \). Once \({\hat{\gamma }}\) is computed, \(M_t\) is set equal to \(12 {\hat{\gamma }}\), which, together with \(r_t\) computed before, determines the set \(\varGamma _t\). At this point, Steps 1) and 2) above are repeated for all values of \(\gamma \in \varGamma _t\), with \(\gamma > {\hat{\gamma }}\), so to have the sets \(AV^{(1)}_\gamma \), \(RV^{(1)}_\gamma \), \(OV^{(1)}_\gamma \) updated at the end of time t for every \(\gamma \in \varGamma _t\).

The following lemma shows that \(M_t\) is indeed a tight upper bound on \(\varDelta _W\).

The following theorem summarizes the main result regarding the \(\alpha \)-oblivious version of our algorithm presented in this subsection.

Similarly to what we remarked at the end of the previous subsection for the doubling dimension, we observe that now the amount of working memory required by the algorithm to analyze the entire stream S will depend on the maximum value of \(\alpha _W\), which is upper bounded by the aspect ratio \(\alpha \) of the entire stream but can in fact be substantially smaller.

We experimented with datasets often used in the clustering literature. Specifically, we used both a low-dimensional dataset, Higgs, and for a higher-dimensional dataset, Covertype, which serves as a stress test for our dimensionality-sensitive approach. The Higgs dataset² contains 11 million points representing high-energy particle features generated through Monte-Carlo simulations. The points of this dataset have 28 attributes, 7 of which are a function of all the others. We considered only these seven “high-level” features, hence regard the data as points in \({\mathbb {R}}^{7}\) using Euclidean distance. The Covertype dataset³ contains \(\simeq \) 500 thousand 54-dimensional points from geological observations of US forest biomes. We interpret the data as points in \({\mathbb {R}}^{54}\) using Euclidean distance. In some experiments, we will also use artificial datasets consisting points randomly extracted from (subspaces of) \({\mathbb {R}}^{100}\), using again Euclidean distance.

We designed implementations of the non-oblivious and of the \(\alpha \)-oblivious version of our k-center strategy, respectively referred to as our-sliding and our-oblivious hereinafter, and an implementation of the state-of-the art sliding window algorithm in [14], referred to as css-sliding. Due to the NP-hardness of the k-center problem, it is unfeasible to compute the optimal solution for each window so to measure the exact approximation factor of the solutions returned by the algorithms. As a workaround, we assess the quality loss incurred by our space-restricted streaming algorithms with respect to the most accurate, polynomial-time sequential approximation gon running on the entire window, hence using unrestricted space.

For the Higgs dataset, we tested several values of k in [10, 100], and several window sizes N in \([10^3,10^6]\). For brevity we report only the results for \(k=20\), since the behaviors observed for the other values exhibit a similar pattern. For our-sliding and our-oblivious, we set \(\epsilon = 1\) and \(\beta = 0.2\). For a fair comparison, we searched the parameter space of css-sliding so to determine a value of its parameter \(\epsilon \) (the equivalent of our parameter \(\beta \)) so to enforce that the algorithms use approximately the same working memory. As a result, for css-sliding we set \(\epsilon = 0.01\) which, in all of our tests, makes its working memory comparable yet slightly larger than the one used by our-sliding and our-oblivious, which gives a competitive advantage to css-sliding in the comparison with respect to the approximation quality. Similarly, for Covertype we report experiments with \(k = 20\) and window lengths in \([10^3,3 \cdot 10^5]\). Due to the higher dimensionality of the dataset, which calls for a finer control on accuracy, we set \(\epsilon = 0.5\) and \(\beta = 0.1\) for both our-sliding and our-oblivious, which brings us to set \(\epsilon = 0.01\) for css-sliding to attain a similar, yet higher, memory usage of the latter w.r.t to the former algorithms.

The results are reported in the plots of Figs. 1, 2, 3, and 4 for the dataset Higgs, and in the plots of Figs. 5, 6, 7, and 8 for Covertype. In the plots, the blue lines refer to css-sliding, the orange lines to our-sliding, the yellow lines to our-oblivious, and the purple ones to the execution of the sequential algorithm gon on the entire window. Each point in a plot represents an average over 10,000 consecutive windows.

The comparison of the algorithms’ memory usage is reported in Figs. 1 and 5. As expected, the working memory required by both css-sliding and our algorithms is mostly insensitive to the the window length, while the memory usage of gon clearly grow linearly with it. Note that our-oblivious maintains consistently less points in memory than our-sliding, as it does not maintain the data structures relative to infeasible estimates, rebuilding them on the fly when needed. Figures 2 and 6 compare the clustering radii obtained by the four algorithms. Remarkably, on the Higgs dataset our-sliding and our-oblivious, even for the relatively large value of \(\epsilon = 1\), return a clustering whose radius essentially coincides with the one returned by running gon on the full window, and it is consistently and decidedly smaller than the one returned by css-sliding. Similarly on the Covertype dataset, the radii returned by our algorithms are consistently smaller than the ones returned by css-sliding, albeit not quite matching the radius of gon. By lowering the \(\epsilon \) parameter one would obtain better results at the cost of an increased memory usage. The update time (Figs. 3 and 7), seems rather insensitive to N for both css-sliding  our-sliding and our-oblivious, while it is clearly negligible for gon, where it simply entails discarding the oldest point of the window and inserting the new one. Finally, as shown in Figs. 4 and 8, the query times of css-sliding  our-sliding and our-oblivious are clearly much smaller than the one of gon, which grows linearly with the window length. The query times of our-sliding and our-oblivious are comparable to those of css-sliding but slightly higher especially in the case of the Covertype dataset, which is conceivably due to its higher dimensionality.

Overall, the experiments provide evidence that, with respect to the state-of-the-art algorithm in [14], our algorithms our-sliding and our-oblivious offer an approximate solution whose quality is much closer to the one guaranteed by best sequential algorithm run on the entire window, within comparable space and time budgets. Moreover the experiments show that the \(\alpha \)-oblivious version of our algorithm consistently maintains less points in the working memory, without compromising neither execution times nor the quality of the solution.

One of the prominent features of our algorithms is their ability to adapt to the inherent complexity of the window \(W_t\), as captured by its dimensionality \(D_W\), and, in the case of our-oblivious, also by its aspect ratio \(\alpha _W\). The experiments reported below are aimed at testing such adaptiveness.

First, we investigate the dependency of the memory usage as a function of \(D_W\). To this purpose, we used several artificial datasets consisting of points of \({\mathbb {R}}^{100}\) randomly extracted from the unit subcube \([0,1]^d\) with d ranging from 1 up to 25 (by fixing \(100-d\) components to zero), making sure to fix the aspect ratio for all the datasets by periodically injecting “extreme” points in the stream⁴. For each of the datasets, we report the number of points maintained in the working memory by our-sliding (we omit for brevity the results of our-oblivious, as they exhibit the same behavior) when used on a window of length \(N = 10^5\) points with parameters \(\beta = 0.1\), \(\epsilon = 1\) and \(k = 20\). All quantities are averaged over 10,000 consecutive windows and reported together with their 95% confidence intervals. As plotted in Fig. 9, for dimensions in the range [1, 15] the memory growth is clearly exponential with the dimension of the subspace, as suggested by the theory. For larger values of the subspace dimension, the growth slows down as the coreset size approaches the window length.

In a second experiment, we assessed the capability of our algorithms to adapt to the dimensionality of the data dynamically, as the window slides over sets of points of varying dimensionality. We generated an artificial dataset (DD) of random points in \({\mathbb {R}}^{100}\), where the first portion of points belongs to a subspace of dimension 1 (i.e., a line), the middle portion of points belongs to a subspace of dimension 10, and the last portion belongs again to a line. In order to fix other features of the dataset that may influence memory usage, the points are generated so to make sure that the aspect ratio of all the windows is roughly the same, so that our-oblivious is not influenced by the variability of \(\alpha _W\). As before, we set \(\beta = 0.1\), \(\epsilon = 1\) and \(k = 20\) for both our-sliding and our-oblivious. The windows length is \(N = 10^4\). The memory usage of our-sliding and our-oblivious, plotted in respectively Figs. 10 and  11, respectively, is low in the windows that cover the points in the first and third portion, and much higher in the windows that cover the points in the second portion, with a transition phase for the windows spanning the two types of subspaces. This property is very appealing, as the algorithms automatically adapt to the dimension \(D_W\) of the active window \(W_t\) to maintain as few points as possible, even without any prior knowledge on the doubling dimension. We observe that the higher level of noise in the plot for our-oblivious is due to the higher variability of the range of guesses \(\varGamma _t\) (which mostly depends on the variability of \(r_t\)), as opposed to the fixed range \(\varGamma \) used by our-sliding.

Finally, we present some experiments on an artificial dataset (alpha) of random points in \({\mathbb {R}}^{100}\), where the aspect ratio varies substantially from window to window while the doubling dimension remains stable. In order to have multiple aspect ratios in the same dataset, we generated the points as follows. All the points have the first five coordinates distributed uniformly in some range and the others set to 0. In the first portion of the stream 90% of the points have coordinates in [0, 10] and 10% of the points have coordinates in [0, 100]. In the second portion of the stream 90% of the points have coordinates in [0, 0.01], hence the minimum distance among any two points will be around \(10^3\) times smaller than before, and 10% of the points have coordinates in [0, 10], hence the diameter will be around 10 times smaller than before, for an overall factor 100 increase in the aspect ratio. Finally, the last part of the stream has the same distribution as the first one.

Once again we set \(\beta = 0.1\), \(\epsilon = 1\) and \(k = 20\) for both our-sliding and our-oblivious and set the window length \(N = 10^4\). Figure 12a and b show the memory usage of the two algorithms, as a function of the step t, while Fig. 12c plots how the extremal values \(r_t/2\) and \(2M_t/\delta \) of range \(\varGamma _t\) (used by our-oblivious to attain obliviousness to the aspect ratio) evolve with t. We first observe that the memory usage of our-oblivious is slightly lower than the one of our-sliding. This feature, as seen in previous experiments, does not arise only in tailor-made artificial datasets but also in real-world ones (see Figs. 1 and 5), giving a competitive advantage to the oblivious version of the algorithm over the non-oblivious one. Somewhat surprisingly, however, the memory usage of our-sliding also seems to adapt to the shape of \(\varGamma _t\) although it uses a fixed range \(\varGamma \) for the guesses. This phenomenon is due to the fact that at each time t, for each guess \(\gamma \in \varGamma - \varGamma _t\), the number of validation and coreset points maintained by our-sliding is rather small.

As for the k-center algorithm, we implemented our diameter approximation algorithm, hereinafter referred to as our-diameter, and we tested it against the sliding window algorithm in [14], which we will refer to as css-diameter. For efficiency, we substituted the expensive quadratic-time naive computation of the exact diameter, wherever it was required, with the following greedy heuristic (referred to greedy-diameter) proposed in [32]: starting from a random point \(p_0\), select the point \(p_1\) farthest away from \(p_0\), then select the point \(p_2\) farthest from \(p_1\), and return \(\mathrm{dist}(p_1, p_2)\). While, theoretically, \(\mathrm{dist}(p_1, p_2)\) is only guaranteed to be within a factor 2 from the actual diameter, it has been observed that, in most cases, the difference between the two quantities is, in fact, very small [32]. In light of this fact, in the experiments we used greedy-diameter both as a baseline to compute the diameter \(\varDelta _W\) of the window W, using the entire window as an input, and as a means of computing the diameter \(\varDelta _T\) of the coreset T. Thus, in the experiments we do not differentiate between the two variants to obtain \(\varDelta _T\) (exactly or approximately) described in Sect. 4.

For what concerns the Higgs dataset, we experimented with window lengths varying in \([10^3, 10^6]\) and parameters \(\epsilon = 0.5\) and \(\beta = 0.1\), for our-diameter, and \(\epsilon = 0.001\), for css-diameter, so to make sure, for fairness, that css-diameter requires approximately the same amount of working memory as our-diameter (but not less). All the quantities in the plots are averaged over 10,000 consecutive windows. Figure  13, reports the memory usage of both algorithms together the (linear) memory usage of the baseline. Figure 14 compares the accuracy exhibited by the algorithms. Specifically, for each value of the window length the figure reports the ratio of the distance returned by each algorithm to the distance computed by greedy-diameter when run on the entire window. Surprisingly, the solution of css-diameter already exhibits rather good accuracy albeit, in theory, the algorithm only guarantees a \((3+\epsilon )\) approximation. Our algorithm our-diameter turns out slightly more accurate than css-diameter, offering a good trade-off between the quality of the solution and the memory usage. We remark that css-diameter delivers results of comparable quality also for larger values of \(\epsilon \) (that is, smaller memory usage), hence it seems that the algorithm is less effective in exploiting larger memory budgets.

For what concerns the Covertype dataset, we repeated the same experiment with window lengths varying in \([10^3, 2*10^5]\) and parameters \(\epsilon = 1\) and \(\beta = 1\), for our-diameter, and \(\epsilon = 0.001\), for css-diameter, again to ensure, for fairness, that css-diameter requires approximately the same amount of working memory. The results concerning the memory requirements and the approximation are reported in Figs. 15 and  16.

Due to higher dimensionality of the dataset we were forced to increase the values of \(\epsilon \) and \(\beta \) for our-diameter in order to keep the memory requirements reasonable and below the window length. Nonetheless the approximation quality featured by our-diameter is superior to the one of css-diameter and matches the one of the baseline for smaller window lengths, while it degrades for larger windows, remaining however always within 10% of the estimate provided by the baseline. This degradation is probably caused by the high dimensionality of the dataset, which forced us to use larger values of \(\epsilon \) and \(\beta \) to keep memory under control.

Regarding update and query times, for both the Higgs and Covertype datasets, we observed for all algorithms the same behaviors discussed for the k-center problem (plots are omitted for brevity). Namely, update and query times are independent of the window length and linear in the working memory, for both our-diameter and css-diameter. Also, the query times our-diameter and css-diameterare comparable, with the former being slightly larger for the higher dimensional Covertype dataset.