Timezone: »
Poster
Coresets for Vector Summarization with Applications to Network Graphs
Dan Feldman · Sedat Ozer · Daniela Rus
We provide a deterministic data summarization algorithm that approximates the mean $\bar{p}=\frac{1}{n}\sum_{p\in P} p$ of a set $P$ of $n$ vectors in $\REAL^d$, by a weighted mean $\tilde{p}$ of a \emph{subset} of $O(1/\eps)$ vectors, i.e., independent of both $n$ and $d$. We prove that the squared Euclidean distance between $\bar{p}$ and $\tilde{p}$ 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.
Author Information
Dan Feldman (The University of Haifa)
Sedat Ozer (MIT)
Daniela Rus (MIT CSAIL)
Related Events (a corresponding poster, oral, or spotlight)
-
2017 Talk: Coresets for Vector Summarization with Applications to Network Graphs »
Mon. Aug 7th 03:30 -- 03:48 AM Room C4.4
More from the Same Authors
-
2021 : Is Bang-Bang Control All You Need? »
Tim Seyde · Igor Gilitschenski · Wilko Schwarting · Bartolomeo Stellato · Martin Riedmiller · Markus Wulfmeier · Daniela Rus -
2022 Poster: Generic Coreset for Scalable Learning of Monotonic Kernels: Logistic Regression, Sigmoid and more »
Elad Tolochinksy · Ibrahim Jubran · Dan Feldman -
2022 Spotlight: Generic Coreset for Scalable Learning of Monotonic Kernels: Logistic Regression, Sigmoid and more »
Elad Tolochinksy · Ibrahim Jubran · Dan Feldman -
2021 : Introduction to Coresets and Open Problems »
Dan Feldman -
2021 : Invited Talk 2: Addressing Model Bias and Uncertainty via Evidential Deep Learning »
Daniela Rus -
2021 Poster: The Logical Options Framework »
Brandon Araki · Xiao Li · Kiran Vodrahalli · Jonathan DeCastro · Micah Fry · Daniela Rus -
2021 Poster: On-Off Center-Surround Receptive Fields for Accurate and Robust Image Classification »
Zahra Babaiee · Ramin Hasani · Mathias Lechner · Daniela Rus · Radu Grosu -
2021 Spotlight: On-Off Center-Surround Receptive Fields for Accurate and Robust Image Classification »
Zahra Babaiee · Ramin Hasani · Mathias Lechner · Daniela Rus · Radu Grosu -
2021 Oral: The Logical Options Framework »
Brandon Araki · Xiao Li · Kiran Vodrahalli · Jonathan DeCastro · Micah Fry · Daniela Rus -
2020 Poster: A Natural Lottery Ticket Winner: Reinforcement Learning with Ordinary Neural Circuits »
Ramin Hasani · Mathias Lechner · Alexander Amini · Daniela Rus · Radu Grosu -
2020 Poster: Sets Clustering »
Ibrahim Jubran · Murad Tukan · Alaa Maalouf · Dan Feldman -
2020 Poster: Prediction-Guided Multi-Objective Reinforcement Learning for Continuous Robot Control »
Jie Xu · Yunsheng Tian · Pingchuan Ma · Daniela Rus · Shinjiro Sueda · Wojciech Matusik