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 sublinear memory performance on stable queries by combining recent advances in locality sensitive hashing (LSH)-based estimators with compressed sensing.