are important tools to generate concise summaries of massive datasets for approximate analysis. A coreset is a small subset of points extracted from the original point set such that certain geometric properties are preserved with provable guarantees. This paper investigates the problem of maintaining a coreset to preserve the minimum enclosing ball (MEB) for a sliding window of points that are continuously updated in a data stream. Although the problem has been extensively studied in batch and append-only streaming settings, no efficient sliding-window solution is available yet. In this work, we first introduce an algorithm, called AOMEB, to build a coreset for MEB in an append-only stream. AOMEB improves the practical performance of the state-of-the-art algorithm while having the same approximation ratio. Furthermore, using AOMEB as a building block, we propose two novel algorithms, namely SWMEB and SWMEB+, to maintain coresets for MEB over the sliding window with constant approximation ratios. The proposed algorithms also support coresets for MEB in a reproducing kernel Hilbert space (RKHS). Finally, extensive experiments on real-world and synthetic datasets demonstrate that SWMEB and SWMEB+ achieve speedups of up to four orders of magnitude over the state-of-the-art batch algorithm while providing coresets for MEB with rather small errors compared to the optimal ones.
Several methods are proposed to approximate MEBs or coresets for MEB in streaming and dynamic settings. @cite_3 and Chan @cite_24 propose algorithms to build @math -coresets for MEB in append-only streams. Though working well in low dimensions, both algorithms become impractical for higher dimensions (i.e., @math ) due to @math complexity. Zarrabi-Zadeh and Chan @cite_0 propose a @math -approximate algorithm to compute MEBs in append-only streams. Agarwal and Sharathkumar @cite_7 design a data structure that can maintain @math -coresets for MEB and @math -approximate MEBs over append-only streams. Chan and Pathak @cite_4 propose a method for maintaining @math -approximate MEBs in the dynamic setting, which supports the insertions and deletions of random points. To the best of our knowledge, none of the existing methods can maintain coresets for MEB over the sliding window efficiently. All of them have to store the entire window of points and recompute from scratch for every window slide, which is expensive in terms of time and space.
@cite_4 @cite_7 @cite_3 @cite_24 @cite_0
2055900608 1985548569 1981313592 2218835040 2114303587
At [email protected]?10, Agarwal and Sharathkumar presented a streaming algorithm for approximating the minimum enclosing ball of a set of points in d-dimensional Euclidean space. Their algorithm requires one pass, uses O(d) space, and was shown to have approximation factor at most (1+3) [email protected] 1.3661. We prove that the same algorithm has approximation factor less than 1.22, which brings us much closer to a (1+2) 2 1.207 lower bound given by Agarwal and Sharathkumar. We also apply this technique to the dynamic version of the minimum enclosing ball problem (in the non-streaming setting). We give an O(dn)-space data structure that can maintain a 1.22-approximate minimum enclosing ball in O(dlogn) expected amortized time per insertion deletion. We develop (single-pass) streaming algorithms for maintaining extent measures of a stream S of n points in Rd. We focus on designing streaming algorithms whose working space is polynomial in d (poly(d)) and sublinear in n. For the problems of computing diameter, width and minimum enclosing ball of S, we obtain lower bounds on the worst-case approximation ratio of any streaming algorithm that uses poly(d) space. On the positive side, we introduce the notion of blurred ball cover and use it for answering approximate farthest-point queries and maintaining approximate minimum enclosing ball and diameter of S. We describe a streaming algorithm for maintaining a blurred ball cover whose working space is linear in d and independent of n. We present a general technique for approximating various descriptors of the extent of a set P of n points in Rd when the dimension d is an arbitrary fixed constant. For a given extent measure μ and a parameter e > 0, it computes in time O(n + 1 eO(1)) a subset Q ⊆ P of size 1 eO(1), with the property that (1 − e)μ(P) ≤ μ(Q) ≤ μ(P). The specific applications of our technique include e-approximation algorithms for (i) computing diameter, width, and smallest bounding box, ball, and cylinder of P, (ii) maintaining all the previous measures for a set of moving points, and (iii) fitting spheres and cylinders through a point set P. Our algorithms are considerably simpler, and faster in many cases, than previously known algorithms. We speed up previous (1 + e)-factor approximation algorithms for a number of geometric optimization problems in fixed dimensions: diameter, width, minimum-radius enclosing cylinder, minimum-width enclosing annulus, minimum-width enclosing cylindrical shell, etc. Linear time bounds were known before; we further improve the dependence of the "constants" in terms of e.We next consider the data-stream model and present new (1 + e)-factor approximation algorithms that need only constant space for all of the above problems in any fixed dimension. Previously, such a result was known only for diameter.Both sets of results are obtained using the core-set framework recently proposed by Agarwal, Har-Peled, and Varadarajan. Published by Elsevier B.V. We analyze an extremely simple approximation algorithm for computing the minimum enclosing ball (or the 1-center) of a set of points in high dimensions. We prove that this algorithm computes a 3 2-factor approximation in any dimension using minimum space in just one pass over the data points.