Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Coresets for Minimum Enclosing Balls over Sliding Windows   \emph{Coresets} 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.

31
The categories of this paper are: ao-sci
35
The categories of this paper are: mtrl-th
36
The categories of this paper are: cmp-lg
15
The categories of this paper are: nucl-ex
30
The categories of this paper are: q-alg
11
The categories of this paper are: hep-lat
29
The categories of this paper are: funct-an
4
The categories of this paper are: cond-mat
9
The categories of this paper are: nlin
7
The categories of this paper are: hep-th
0
The categories of this paper are: hep-ph
13
The categories of this paper are: quant-ph
33
The categories of this paper are: plasm-ph
6
The categories of this paper are: astro-ph
19
The categories of this paper are: eess
34
The categories of this paper are: chem-ph