## G. Cormode, C. Dickens, and D. Woodruff.
Subspace exploration: Bounds on projected frequency estimation.
In *ACM Principles of Database Systems (PODS)*, 2021.

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 2^{d}.
That is, for *c*,*c*' in(0,1) and a parameter *N*=2^{d} an *N*^{c}-approximation can be obtained
in space min(*N*^{c'},*n*), showing that it is possible to improve on the naïve approach
of keeping information for all 2^{d} 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.

[ bib |
Alternate Version ]
Back

*This file was generated by
bibtex2html 1.92.*