For a data set with 20 000 polygonal curves with around 250 vertices each, we reach up to 1 000 queries per second.
To achieve this, we use a datastructure based on quadtrees and multiple upper and lower bounds to restrict the number of curves that have to be considered. We also describe a new recursive variant of the O(n^2) Frechet distance decision algorithm that is much faster in practice despite being slightly slower in the worst case.