Cormode, Graham, Dickens, Charlie and Woodruff, David P. (2021) Subspace exploration : bounds on projected frequency estimation. In: The 2021 ACM SIGMOD/PODS Conference, Virtual conference, 20-25 Jun 2021. Published in: PODS'21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems pp. 273-284. ISBN 9781450383813. doi:10.1145/3452021.3458312
![[thumbnail of WRAP-Subspace-exploration-bounds-projected-frequency-2021.pdf]](https://cdn.statically.io/img/wrap.warwick.ac.uk/152102/1.hassmallThumbnailVersion/WRAP-Subspace-exploration-bounds-projected-frequency-2021.pdf)  Preview |
PDF
WRAP-Subspace-exploration-bounds-projected-frequency-2021.pdf - Accepted Version - Requires a PDF viewer. Download (1MB) | Preview |
Abstract
Given an n×d dimensional dataset A, a projection query specifies a subset C⊆[d] of columns which yields a new n×|C| array. We study the space complexity of computing data analysis functions over such subspaces, including heavy hitters and norms, when the subspaces are revealed only after observing the data. We show that this important class of problems is typically hard: for many problems, we show 2Ω(d) lower bounds. However, we present upper bounds which demonstrate space dependency better than 2d. That is, for c,c′∈(0,1) and a parameter N=2d an Nc-approximation can be obtained in space min(Nc′,n), showing that it is possible to improve on the naïve approach of keeping information for all 2d subsets of d columns. Our results are based on careful constructions of instances using coding theory and novel combinatorial reductions that exhibit such space-approximation tradeoffs.
| Item Type: | Conference Item (Paper) |
|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science |
| Library of Congress Subject Headings (LCSH): | Computer algorithms, Database management, Computational complexity, Querying (Computer science) |
| Journal or Publication Title: | PODS'21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems |
| Publisher: | ACM |
| ISBN: | 9781450383813 |
| Official Date: | 20 June 2021 |
| Dates: | Date Event 20 June 2021 Published 20 April 2021 Accepted |
| Page Range: | pp. 273-284 |
| DOI: | 10.1145/3452021.3458312 |
| Status: | Peer Reviewed |
| Publication Status: | Published |
| Access rights to Published version: | Open Access (Creative Commons open licence) |
| Date of first compliant deposit: | 6 May 2021 |
| Date of first compliant Open Access: | 1 September 2021 |
| RIOXX Funder/Project Grant: | Project/Grant ID RIOXX Funder Name Funder ID |
| Conference Paper Type: | Paper |
| Title of Event: | The 2021 ACM SIGMOD/PODS Conference |
| Type of Event: | Conference |
| Location of Event: | Virtual conference |
| Date(s) of Event: | 20-25 Jun 2021 |
| Related URLs: | |
| Open Access Version: | |
| Persistent URL: | https://wrap.warwick.ac.uk/152102/ |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |