Before revision:  All 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  .
After revision:  All 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 . In addition, we show lower bounds for this problem. Consider any data structure which achieves an approximation factor less than 2 and which supports curves of arclength up to L and answers the query using only a constant number of probes. We show that under reasonable assumptions on the word size any such data structure needs space in L^{\Omega(k) .