Before revision:  Our data structure uses only a constant number of probes per query and does not have any dependency on L. We apply similar techniques for proving cell-probe lower bounds for the discrete Fr\'echet distance matching known upper bounds .
After 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 O(nm) and query time in O(k), and which answers queries with an approximation factor in O(k). Both of our data structures make use of the concept of signatures, which were originally introduced for the problem of clustering time series under the Fr\'echet distance matching known upper bounds .