Timezone: »

 
Poster
Coresets for k-Segmentation of Streaming Data
Guy Rosman · Mikhail Volkov · Dan Feldman · John Fisher III · Daniela Rus

Thu Dec 11 11:00 AM -- 03:00 PM (PST) @ Level 2, room 210D
in Poster Session »

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 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(klog n /eps^2) that provides a (1+eps)-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 eduction 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.

[ PDF] 

Author Information

Guy Rosman (Massachusetts Institute of Technology)
Mikhail Volkov (Massachusetts Institute of Technology)
Dan Feldman (Massachusetts Institute of Technology)
John Fisher III (MIT)
Daniela Rus (Massachusetts Institute of Technology)

More from the Same Authors