Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review
Data summarization is an effective approach to dealing with the 'big data' problem. While data summarization problems traditionally have been studied is the streaming model, the focus is starting to shift to distributed models, as distributed/parallel computation seems to be the only viable way to handle today's massive data sets. In this paper, we study ε-approximations, a classical data summary that, intuitively speaking, preserves approximately the density of the underlying data set over a certain range space. We consider the problem of computing ε-approximations for a data set which is held jointly by k players, and give general communication upper and lower bounds that hold for any range space whose discrepancy is known.
Original language | English |
---|---|
Title of host publication | 56th IEEE Symposium on Foundations of Computer Science (FOCS) Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |
Number of pages | 20 |
Publisher | IEEE Computer Society Press |
Publication year | 2015 |
Publication status | Published - 2015 |
Event | IEEE Symposium on Foundations of Computer Science - Berkeley, United States Duration: 18 Oct 2015 → 20 Oct 2015 Conference number: 56 |
Conference | IEEE Symposium on Foundations of Computer Science |
---|---|
Nummer | 56 |
Land | United States |
By | Berkeley |
Periode | 18/10/2015 → 20/10/2015 |
See relations at Aarhus University Citationformats
ID: 87497673