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 hash (LSH)-based estimators with compressed sensing.