# Coresets for Vector Summarization with Applications to Network Graphs

arXiv: https://arxiv.org/abs/1706.05554 · HTML: https://mlsanity.com/paper/1706.05554/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Jun 2017.

## Built on by (most cited first, 2 of 2)

- [AutoCoreset: An Automatic Practical Coreset Construction Framework](https://mlsanity.com/paper/2305.11980/) (2023)
- [COREKG: Coreset-Guided Personalized Summarization of Knowledge Graphs](https://mlsanity.com/paper/2605.14900/) (2026)

## Abstract (arXiv)

We provide a deterministic data summarization algorithm that approximates the mean barp=frac1nsump∈ P p of a set P of n vectors in REALd, by a weighted mean tildep of a subset of O(1/eps) vectors, i.e., independent of both n and d. We prove that the squared Euclidean distance between barp and tildep is at most eps 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 it 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.