Before revision:  In particular, we develop an online sketching algorithm that can compress N vectors into a tiny sketch consisting of small arrays of counters whose size scales as O(N ^{b\log^2{N}) } ) in O(N^{b+1} \log^3{N}) time} , where b < 1 depending on the stability of the near-neighbor search. This sketch is sufficient to identify the top-v near-neighbors with high probability. To the best of our knowledge, this is the first near-neighbor search algorithm that breaks the linear memory (O(N)) barrier. We achieve sub-linear memory by combining advances in locality sensitive hashing (LSH) based estimation, especially the recently-published ACE algorithm, with compressed sensing and heavy hitter techniques.
After revision:  In particular, we develop an online sketching algorithm that can compress N vectors into a tiny sketch consisting of small arrays of counters whose size scales as O(N ^{b\log^2{N}) } ) in O(N^{b+1} \log^3{N}) time} , where b < 1 depending on the stability of the near-neighbor stability condition. We achieve data-dependent sublinear space by combining recent advances in locality sensitive hashing (LSH) based estimation, especially the recently-published ACE algorithm, with compressed sensing and heavy hitter techniques.