The Library
Subspace exploration : bounds on projected frequency estimation
Tools
Tools
Tools
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
|
PDF
WRAP-Subspace-exploration-bounds-projected-frequency-2021.pdf - Accepted Version - Requires a PDF viewer. Download (1348Kb) | Preview |
Official URL: https://doi.org/10.1145/3452021.3458312
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 > 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: |
|
||||||||||||
| Page Range: | pp. 273-284 | ||||||||||||
| DOI: | 10.1145/3452021.3458312 | ||||||||||||
| Status: | Peer Reviewed | ||||||||||||
| Publication Status: | Published | ||||||||||||
| Access rights to Published version: | Open Access | ||||||||||||
| RIOXX Funder/Project Grant: |
|
||||||||||||
| 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: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
