Before revision:  We achieve data-dependent sublinear space by combining recent advances in locality sensitive hashing (LSH)-based estimators with compressed sensing.
After revision:  We achieve data-dependent sublinear space by combining recent advances in locality sensitive hashing (LSH)-based estimators , online kernel density estimation, and compressed sensing.