Before revision:  } Our third positive result is a probabilistic data structure based on locality-sensitive hashing, which achieves space in \mathcal{O}(  nm) and query time in \mathcal{O}(k  ), and which answers queries with an approximation factor in \mathcal{O}(k).
After revision:  } Our third positive result is a probabilistic data structure based on locality-sensitive hashing, which achieves space in \mathcal{O}( n\log n+ nm) and query time in \mathcal{O}(k ), and which answers queries with an approximation factor in \mathcal{O}(k).