Abstract

We provide a deterministic data summarization algorithm that approximates the mean = of a set P of n vectors in by a weighted mean of a subset of O(1/ε) vectors, i.e., independent of both n and d. We prove that the squared Euclidean distance between and is at most ε multiplied by the variance of P . We use this algorithm to maintain an approximated sum of vectors from an unbounded stream, using memory that is independent of d, and logarithmic in the n vectors seen so far. Our main application is to extract and represent in a compact way friend groups and activity summaries of users from underlying data exchanges. For example, in the case of mobile networks, we can use GPS traces to identify meetings; in the case of social networks, we can use information exchange to identify friend groups. Our algorithm provably identifies the Heavy Hitter entries in a proximity (adjacency) matrix. The Heavy Hitters can be used to extract and represent in a compact way friend groups and activity summaries of users from underlying data exchanges. We evaluate the algorithm on several large data sets.