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