Before revision: We demonstrate the first possibility of a sub-linear memory sketch for solving the approximate near-neighbor search problem. 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.
After revision: We present the first sublinear memory sketch which can be queried to find the v nearest neighbors in a dataset. Our 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.