Before revision:  Our data structure uses only a constant number of probes per query and does not have any dependency on L. In particular, this shows that our solution is optimal if only a constant number of probes is allowed. Our second 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}(nm) and query time in \mathcal{O}(k), and which answers queries with an approximation factor in \mathcal{O}(k).