Before revision:  Our online sketching algorithm can compress an N-element dataset to a sketch of size O(N^b \log ^3{N ) in O(N^{  b+1  } \log ^3{N ) time, where b < 1 when the query satisfies a data-dependent near-neighbor stability condition .
After revision:  Our online sketching algorithm can compress an N-element dataset to a sketch of size O(N^b \log ^3{N ) in O(N^{ b+1 } \log ^3{N ) time, where b < 1. This sketch can correctly report the nearest neighbors of any query that satisfies a stability condition parameterized by b .