Paper Info
Title
Coresets for k-Segmentation of Streaming Data.
Abstract
Life-logging video streams, financial time series, and Twitter tweets are a few examples of high-dimensional signals over practically unbounded time. We consider the problem of computing optimal segmentation of such signals by a k-piecewise linear function, using only one pass over the data by maintaining a coreset for the signal. The coreset enables fast further analysis such as automatic summarization and analysis of such signals. A coreset (core-set) is a compact representation of the data seen so far, which approximates the data well for a specific task - in our case, segmentation of the stream. We show that, perhaps surprisingly, the segmentation problem admits coresets of cardinality only linear in the number of segments k, independently of both the dimension d of the signal, and its number n of points. More precisely, we construct a representation of size O(k log n/epsilon(2)) that provides a (1+epsilon)-approximation for the sum of squared distances to any given k-piecewise linear function. Moreover, such coresets can be constructed in a parallel streaming approach. Our results rely on a novel reduction of statistical estimations to problems in computational geometry. We empirically evaluate our algorithms on very large synthetic and real data sets from GPS, video and financial domains, using 255 machines in Amazon cloud.
Year
Venue
Field
2014
ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 27 (NIPS 2014)
Automatic summarization,Binary logarithm,Data set,Segmentation,Computer science,Computational geometry,Cardinality,Artificial intelligence,Linear function,Machine learning,Coreset
DocType
Volume
ISSN
Conference
27
1049-5258
Citations 
PageRank 
References 
12
0.51
16
Authors
6
Name
Order
Citations
PageRank
Guy Rosman117418.86
Mikhail V. Volkov2202.07
Dan Feldman3467.55
John W. Fisher III487874.44
Daniela Rus57128657.33
Fisher III, John W.6120.51