Locality-sensitive hashing of curves∗
Anne Driemel1 and Francesco Silvestri2
1

Department of Mathematics and Computer Science, Eindhoven University of
Technology, The Netherlands
adriemel@tue.nl
Department of Information Engineering, University of Padova, Italy
Theoretical Computer Science, IT University of Copenhagen, Denmark
silvestri@dei.unipd.it

arXiv:1703.04040v1 [cs.CG] 11 Mar 2017

2

Abstract
We study data structures for storing a set of polygonal curves in IR d such that, given a query
curve, we can efficiently retrieve similar curves from the set, where similarity is measured using
the discrete Fréchet distance or the dynamic time warping distance. To this end we devise the first
locality-sensitive hashing schemes for these distance measures. A major challenge is posed by the
fact that these distance measures internally optimize the alignment between the curves. We give
solutions for different types of alignments including constrained and unconstrained versions. For
unconstrained alignments, we improve over a result by Indyk from 2002 [17] for short curves. Let
n be the number of input curves and let m be the maximum complexity of a curve in the input. In
α
log n, for some fixed α > 0, our solutions imply an approximate
the particular case where m ≤ 4d
near-neighbor data structure for the discrete Fréchet distance that uses space in O(n1+α log n)
and achieves query time in O(nα log2 n) and constant approximation factor. Furthermore, our
solutions provide a trade-off between approximation quality and computational performance: for
any parameter k ∈ [m], we can give a data structure that uses space in O(22k mk−1 n log n + nm),
answers queries in O(22k mk log n) time and achieves approximation factor in O(m/k).
1998 ACM Subject Classification F.2.2 Nonnumerical Algorithms and Problems
Keywords and phrases Locality-Sensitive Hashing, Fréchet distance, Dynamic Time Warping

1

Introduction

We study nearest-neighbor searching for polygonal curves under the discrete Fréchet distance
or the dynamic time warping distance. This problem has various applications in machine
learning, information retrieval and classification where the recorded instances are curves.
Dynamic time warping has shown to be useful for classification of various types of data: surgical processes [10], whale singing [5], chromosomes [23], fingerprints [22], electrocardiogram
(ECG) frames [14], and vessel trajectories [30]. Originally conceived for speech recognition,
it is now being deployed as universal similarity measure for time series in the field of data
mining. The Fréchet distance is considered a useful similarity measure for trajectories of
moving objects [6, 11, 20, 31].
Indyk and Motwani [19, 13] introduced the idea that hashing could enable faster nearestneighbor searching in high-dimensional Euclidean spaces using a hashing scheme where near
points are more likely to collide than far ones. They showed that such an approach can
be used for the (c, r)-near neighbor problem which is defined as follows. Preprocess a set S
∗

Driemel has been supported by NWO Veni project “Clustering time series and trajectories (10019853)”.
Silvestri has been supported by the European Research Council project “Scalable Similarity Search”
(no. 614331) and by MIUR of Italy under project AMANDA.

2

Locality-sensitive hashing of curves

of n points into a data structure that answers queries in the following way: if there exists
a point p ∈ S that lies within distance r from the query point q, then the data structure
reports a point p′ ∈ S that lies within distance cr from q. In this paper, we study such
locality-sensitive hashing schemes for the space of curves.

1.1

State of the art

In 2002, Indyk gave a deterministic and approximate near-neighbor data structure for the
discrete Fréchet distance [17]. This data structure is to date the only result known for
this task and represents the state of the art. The data structure achieves approximation
factor O(log m + log log n), where m is the maximum length of a curve and n is the maximum
of elements
in the data structure. Further, the data structures uses space in

 number
√
√
O |X| m (m m n)2 , where |X| is the size of the domain on which the curves are defined.

The query time is O mO(1) log n . The data structure precomputes all answers to queries
√
with curves of length m, leading to a very high space consumption.1
In the group of ℓp distances, the Fréchet distance most resembles the ℓ∞ -distance, which
is notoriously hard to embed into a low-dimensional ℓp -space, see also the discussion by Indyk
in [15]. Indyk’s data structure for the discrete Fréchet distance is in fact an extension of his
data structure for the ℓ∞ -distance [15]. Any subset of ℓd∞ can be embedded into the Fréchet
metric2 [18]. This embedding implies that, unless the strong exponential-time hypothesis
fails, there exists no data structure for near-neighbor searching
under the discrete Fréchet

distance that achieves preprocessing time in O n2−ε poly m , query time in O n1−ε poly m
for any ε > 0, and approximation factor c < 3. (see Appendix A for details). This suggests
that the problem becomes hard for long curves, i.e., m ∈ ω(log n). Recently, Backurs
and Sidiropoulos showed how to embed finite subsets of the Hausdorff distance into ℓ∞
using constant distortion and constant dimension of the host space [2]. However, for the
Fréchet distance, no non-trivial embeddings are known, see also the discussion in [18]. It is
possible to embed any finite metric space into ℓp , for example, using the embedding due to
Bourgain [25]. However, the high cost of computing the embedding makes it unfit for use in a
nearest-neighbor data structure. Another known approach to proximity searching in metric
spaces is to exploit a low doubling-dimension [1, 12]. However, the doubling dimension of
the Fréchet distance is infinite, even if the metric space is restricted to curves of constant
length [9]. Recently Bartal et al. [3] gave lower bounds for embedding doubling spaces. Their
result implies that a metric embedding of the Fréchet distance into an ℓp -space would have
at least super-constant distortion. However, as noted earlier, it is not even known how to
obtain such an embedding.
In general, there is little known in terms of data structures for the Fréchet distance.
The authors are aware of the following few results which were developed for the classic
(continuous) Fréchet distance. De Berg, Cook and Gudmundsson [7] study range counting
queries for the set of subcurves that lie within distance r to a query line segment. Their data
structure uses a partition tree to store compressed subcurves. For any parameter n ≤ s ≤ n2 ,
the space used by the data structure is in O(s poly log n). The queries are computed in time

1

Indyk also claims (without proof) a slightly different
parameter t ≥ 2: approx
 bound using a trade-off
imation factor O((log m + log log n)(t−1) ), space O

2

tm1/t

m2 |X|

n2t

and query time (m + log n)O(t) .

The space bound decreases at the cost of approximation and query time as soon as t < log m; however,
the trade-off disappear for larger values of t since all bounds increase in t as soon as t ≥ log m.
In particular, one can use 3d vertices to express each d-dimensional vector as a curve on a real line.

A. Driemel and F. Silvestri


in O √ns poly log n and uses a constant approximation factor. However, the data structure
does not support more complex query curves than line segments. A second data structure
is due to Driemel and Har-Peled [8]. This data structure answers queries for the Fréchet
distance of a subcurve to a query curve (the subcurve is specified in the query). If the queries
are line segments, an approximation factor of (1 + ε) can be achieved with logarithmic query
time and linear space. Unlike the ℓ∞ -metric, which can be evaluated in time that is linear
in the dimension, evaluating a single Fréchet distance is believed to take time that is at
least roughly quadratic in the complexity of the curves (the number of vertices) in the worst
case [4]. The high time complexity can be credited to the fact that the distance measure
optimizes over all possible monotone alignments of the two input sequences. Computing
the discrete Fréchet distance, as well as dynamic time warping, can be solved via dynamic
programming. In both cases, the naive linear scan leads to O(nm2 ) query time for finding
the nearest neighbor. For dynamic time warping (DTW) no data structures exist that give
provable guarantees, however there exist many heuristics, see the work of Rakthanmanon
et al. [26] (and references therein). Since DTW does not satisfy the triangle inequality, it
cannot be embedded into an ℓp -space.

1.2

Our results

Our first result is a basic LSH scheme for the discrete Fréchet distance, which leads to a
very efficient LSH with approximation factor that is linear in the number of curve vertices.
The scheme is described in Section 3 and it is surprisingly simple: We snap the curves to
a randomly shifted grid and remove consecutive duplicate vertices. It turns out that this
simple scheme alleviates the alignment problem which sets the Fréchet distance computation
apart from the ℓ∞ -distance. Next, we show in Section 4 that it is even possible to get
constant approximation, at the cost of a lower collision probability for near curves. The
second scheme randomly perturbs the vertices of the input curves independently and snaps
the vertices to a fixed grid instead of a randomly shifted grid. It is natural to ask if there
exists an LSH scheme exhibiting a full-spectrum trade-off between collision probability and
approximation. We positively answer to this question in Section 5, with a scheme based on
a random partition of the input curves, inspired by Indyk’s data structure [17], followed by
the application of the basic scheme to each subsequence independently.3
All the LSH schemes achieve zero false-positives, meaning that no collisions happen
between far curves. When applied to solve the (c, r)-near neighbor problem, we obtain the
results summarized in Table 1 (see also Section 2.3). It is interesting to compare our bounds
with the state of the art. The basic scheme of Theorem 7 provides a data structure using
almost linear space and O(m log n) query time by allowing a linear approximation c = O(m).
This query time always beats
 the trivial exact solution of scanning all input curves for each
query, which needs O nm2 time. In comparison, Indyk’s result [17] provides a better
approximation when m = Ω(log log n) but it uses exponential space and slightly higher
query time. More generally, when curves are short m = o(log n), our basic result provides a
good alternative to Indyk’s result due to the improved space. In the particular case where
α
log n for some fixed α > 0, we can answer queries using a constant approximation
m ≤ 4d
factor in O(nα log2 n) time and using O(n1+α log n) space, using Theorem 9. When curves

3

Indeed, in Theorem 10, the collision probability for near curves is bounded by 2−3M for K = M (using
Stirlings approximation for the binomial coefficient), however when summarizing our bounds we use
the simplified bound from Corollary 11.

3

4

Locality-sensitive hashing of curves

Table 1 Our approximate near-neighbor data structure results for the discrete Fréchet distance
in comparison with the result by Indyk, assuming d = O(1) for simplicity. The first four rows
refer to the standard discrete Fréchet distance dF , while the last two rows dw,aF and dw,sF refer to
the anchored and speed constraints respectively. The input consists of n polygonal curves in IRd ,
each of complexity at most m. The corresponding query results are achieved with high probability.
The parameters k ≥ 1 and ℓ ≥ 1 trade-off space/query time and approximation, and parameter w
constrains the possible alignments. The first entry in bi-criteria (·, ·) denotes the distance approximation, while the second is the alignment approximation.

dF

dw,aF
dw,sF

Space
Query time
Approximation
Reference
√
√


O |X| m (m m n)2
O mO(1) log n
O(log m + log log n)
[17]
O(n log n + nm)
O(m log n)
O(m)
Thm. 7
O(24md n log n + nm)
O(24md m log n)
O(1)
Thm. 9
O(22k mk−1 n log n + nm)
O(22k mk log n)
O(m/k)
 Cor. 11
√ 
 √ 

 3
2m/ℓ
2m/ℓ
O
2w
n log n + nm O
2w
m log n bi-criteria 4d 2 ℓ, 2ℓ − 2 Thm. 14
√
 3 
 √

2m/ℓ
2m/ℓ
O
2wℓ
2wℓ
Thm. 17
n log n + nm O
m log n bi-criteria 4d 2 ℓ, ℓ

have constant complexity, the basic LSH gives the first efficient data structure with constant
approximation.
We then address LSH for the discrete Fréchet distance under alignment constraints in
Section 6. It is natural to constrain the alignments between the vertices of a curve: this
preserves important characteristics of the input curves and it also reduces the actual time
to compute the distance between curves (see e.g., [27, 21]). We target the anchored and
bounded speed constraints that require, respectively, a vertex to be aligned with at most w
vertices or to be aligned with vertices whose indices differ by at most w/2, for a suitable
parameter w ≥ 1 (for formal definitions see Section 2.2). Our scheme provides the first data
structures for the (c, r)-near neighbor problem with alignment constraints. Further, they
exhibit a bi-criteria approximation: it is possible to reduce space and query time with a
weaker approximation on the distance but also on the alignment parameter w. Bounds are
summarized in Table 1.
In Section 7, we study which one of our schemes work for DTW. We show that the basic
LSH applies to DTW with the same linear approximation, space and query bounds of the
discrete Fréchet distance. In contrast, the techniques to improve the approximation factor
under the Fréchet distance do not provide improvements for DTW. The LSH schemes for
constrained distances also yields linear approximation for DTW distance, but maintains the
trade-off between space/query time and the approximation on the alignment parameter w.
We remark that a data structure for the (c, r)-approximate near neighbor problem can
be used as a building block for solving the c-approximate nearest neighbor problem. We
refer to [28] for more details.

2
2.1

Preliminaries
Distance measures for curves

A time series (or trajectory)4 is a series (p1 , t1 ), . . . , (pm , tm ) of measurements pi of a signal
taken at times ti . We assume 0 = t1 < t2 < . . . < tm = 1 and m is finite. A time series
4

Usually, these are referred to as time series when d = 1 and trajectories when d > 1.

A. Driemel and F. Silvestri

may be viewed as a continuous function P : [0, 1] → IRd by linearly interpolating p1 , . . . , pm
in order of ti , i = 1, . . . m. We obtain a polygonal curve with vertices p1 = P (t1 ), . . . , pm =
P (tm ) and segments between pi and pi+1 called edges pi pi+1 = {xpi + (1 − x)pi+1 |x ∈ [0, 1]}.
We will simply refer to P as a curve. We denote the space of all curves in IRd with ∆d .
We now recall the definitions of discrete Fréchet distance and of the dynamic time warping
distance between two curves. To this end we define the concept of traversal. Given two
polygonal curves P = p1 , . . . , pm1 and Q = q1 , . . . , qm2 , a traversal
T = {(i1 , j1 ), (i2 , j2 ), . . . , (iℓ , jℓ )}
is a sequence of pairs of indices referring to a pairing of vertices from the two curves with
the following properties:
(i) i1 = 1, j1 = 1, iℓ = m1 , and jℓ = m2
(ii) ∀(ik , jk ) ∈ T : (ik+1 − ik ) ∈ {0, 1} ∧ (jk+1 − jk ) ∈ {0, 1}.
(iii) ∀(ik , jk ) ∈ T : (ik+1 − ik ) + (jk+1 − jk ) ≥ 1.
Intuitively, one can think of the traversal as a prescribed schedule for simultaneously traversing the two curves, starting at the first vertex of each curve, in every step the traversal
advances by one vertex, either on one of the curves, or on both curves simultaneously, finally
the traversal has to end at the last vertices of the two curves.
We consider the maximum distance of two vertices paired by a traversal as the cost
incurred by this traversal. Let T be the set of possible traversals for two curves P and Q,
then the Fréchet distance corresponds to the minimal cost of a traversal of the two curves.
Likewise, if we define the cost of a traversal as the sum of distances between paired vertices,
then the traversal with minimum cost corresponds to the dynamic time warping distance.
◮ Definition 1. Let T be the set of possible traversals for two curves P and Q. The discrete
Fréchet distance dF (P, Q) between curves P and Q is defined as
dF (P, Q) = min

max kpik − qjk k.

T ∈T (ik ,jk )∈T

◮ Definition 2. Let T be the set of possible traversals for two curves P and Q. The dynamic
time warping (DTW) distance dDTW (P, Q) between curves P and Q is defined as
X
kpik − qjk k.
dDTW (P, Q) = min
T ∈T

(ik ,jk )∈T

The discrete Fréchet distance satisfies the triangle inequality and is a pseudo-metric.
This is not true for the DTW distance, since it does not satisfy the triangle inequality.
We refer to a traversal realizing the distance of two curves as an optimal traversal. We
can interpret a traversal as the edges of a bipartite graph where the nodes are the vertices
of the two curves and the edges connect the pairs. The following simple lemma holds for
all distance measures. As a consequence, we assume in the paper that an optimal traversal
consists of disconnected stars, that we call components.
◮ Lemma 3. For any two curves P = p1 , . . . , pm1 and Q = q1 , . . . , qm2 , there always exists
an optimal traversal T with the following two properties:
(i) T consists of at most m = min{m1 , m2 } disconnected components.
(ii) Each component is a star, i.e., all edges of this component share a common vertex.
Proof. The first part is immediate, since we can charge each component to a vertex of the
shorter curve that is contained in it. To see the second part of the claim, assume for the sake

5

6

Locality-sensitive hashing of curves

of contradiction that an optimal traversal has the pairs (i, j), (i, j + 1)(i + 1, j + 1) for some
i, j (or the symmetric configuration (i, j), (i + 1, j)(i + 1, j + 1)). In this case, the middle pair
(i, j + 1) can be removed without increasing the cost and without invalidating the traversal
◭
properties. We can apply this reasoning repeatedly until each component is a star.

2.2

Distances measures with constraints

Anchored distances. A traversal T is said w-anchored traversal if each vertex is paired with a
vertex at distance at most w/2 (for simplicity we assume w to be even): namely, |i−j| ≤ w/2
for each (i, j) ∈ T . Parameter w is called the width of the traversal. Such a traversal exists
only if |m1 − m2 | ≤ w/2, otherwise there would be unpaired vertices (e.g., the last vertex
of the longest curve). For two curves P and Q with lengths satisfying |m1 − m2 | ≤ w/2, we
define the w-anchored discrete Fréchet distance dw,aF (P, Q) and w-anchored DTW distance
dw,aDTW (P, Q) as in Definitions 1 and 2 where T is defined as the set of all possible wanchored traversals.
Speed-constrained distances. A traversal T is a w-speed traversal if each vertex is aligned
with at most w vertices of the other curve: in other terms, the bipartite graph representing
the traversal has degree at most w. Parameter w is called the speed of the traversal. (We
overload the meaning of w since the width and speed parameters play a similar role in our
algorithms.) Note that a w-anchored traversal is a (w + 1)-speed traversal, but the opposite
is not necessary true. A w-speed traversal exists only if 1/w ≤ m1 /m2 ≤ w. For two curves
P and Q with lengths satisfying 1/w ≤ m1 /m2 ≤ w, we defined the w-speed discrete Fréchet
distance dw,sF (P, Q) and w-speed DTW distance dw,sDTW (P, Q) as in Definitions 1 and 2
where T is defined as the set of all possible w-speed traversals.

2.3

Locality-sensitive hashing

We use the notion of asymmetric locality-sensitive hashing (see, e.g. [29]), defined as follows:
◮ Definition 4. Let S be the set of curves in IRd and let d : S × S → IR+ be a distance
measure defined on them. Given real values r > 0, c > 1, 0 ≤ α1 ≤ 1 and 0 ≤ α2 ≤ 1 with
α1 > α2 , a family H of pairs of hash functions (h1 , h2 ) is called (r, c, α1 , α2 )-sensitive if for
any two curves P, Q ∈ S
(i) if d(P, Q) ≤ r, then P r(h1 ,h2 )∈H (h1 (P ) = h2 (Q)) ≥ α1 ;
(ii) if d(P, Q) > cr, then P r(h1 ,h2 )∈H (h1 (P ) = h2 (Q)) ≤ α2 .
When h1 = h2 , we have the traditional definition of (symmetric) locality-sensitive hashing.
The above scheme is asymmetric in the sense that there are two different schemes and the
guarantees only hold for curves P and Q where P was hashed using the first scheme and Q
was hashed using the second scheme. This is useful, e.g., if the application of the LSH is
a nearest neighbor data structure, where comparisons only need to be done between input
objects and query objects.
The results reported in Table 1 follow by applying the standard framework for solving
the (c, r)-near neighbor problem with an (r, c, α1 , α2 )-sensitive hashing scheme H. For the
sake of completeness, we sketch this process here.5 A new family H′ of hashing is constructed by concatenating k = max{1, logα2 (1/n)} hash functions from H, so that the collision
5

We observe that the LSH schemes presented in this paper have long hash values (curves or array
of curves). However, they can be shortened with traditional hashing (i.e., by mapping each value
in [0, O(n)]), that allows for a more efficient search in the hash tables generated by the LSH. This
technique increases α2 by an additive O(1/n) term.

A. Driemel and F. Silvestri

7

probability of far points is at most 1/n. Then, each point in S is inserted into L = (1/α1 )k
hash tables, each corresponding to a different randomly chosen hash function from H′ . For
a query point q, the algorithm searches among all points that collide with q in the L hash
tables and stops as soon
 as a cr-near neighbor is found. Whenρ α2 > 0, the data structure
1+ρ
requires O n
+ nm memory words and query time O(Γn ), where Γ = Ω(m) is the
time required for computing the distance between two curves and ρ = log α1 / log α2 . When
α2 = 0, the data structure requires O(n/α1 ) memory words and query time O(m/α1 ). Note
that in this case the query time does not include Γ: the algorithm does not need to compute
distances between q and points in the buckets since there are no false positives. For a given
query, the data structures returns an approximate cr-near neighbor with constant probability. In order to obtain high probability (i.e., at least 1 − 1/n) we repeat the above process
log n times, leading to log n different data structures. This increases space and query time
by a O(log n) term.

3

Linear approximation factor

We first present the basic LSH scheme in Section 3.1, and then in Section 3.2 we analyze
its correctness and performance for the discrete Fréchet distance. The basic LSH has an
approximation factor that is linear in the number of vertices that a curve can have.

3.1

Algorithm

We use a randomly shifted grid in our hashing scheme. Let the canonical d-dimensional grid
of resolution δ be defined as an evenly spaced point set in IRd , as follows:
n
o
Gδ = (x1 , . . . , xd ) ∈ IRd | ∀ 1 ≤ i ≤ d ∃ j ∈ IN : xi = j · δ .
Consider a family of such grids parametrized by a shift t:
bt = {p + t | p ∈ Gδ } .
G
δ

Choosing t uniformly at random from the half-open hypercube [0, δ)d we obtain a family of
randomly shifted grids. Let P ∈ ∆d be a polygonal curve with vertices p1 , . . . , pm and let
htδ : ∆d → ∆d be a hash function. The curve htδ (P ) is defined as the result of the following
two-stage construction.
bt . More precisely, we replace each vertex pi with its
(i) We snap the curve to the grid G
δ
′
′
closest grid point pi = arg minq∈G
bt kpi − qk to obtain the curve P .
δ

(ii) We remove consecutive duplicates in P ′ . That is, we remove the vertex p′i if it is
identical to p′i−1 .
Let HδL be the family of hash functions htδ constructed this way.

3.2

Analysis

◮ Lemma 5. Let P, Q ∈ ∆d be two curves with m1 and m2 points, respectively, and let
m = min{m1 , m2 }. For any δ > 0, it holds that



dF (P, Q)
t
t
L
.
P rHδ hδ (P ) = hδ (Q) ≥ 1 − 2dm ·
δ
Proof. We bound the probability that P and Q do not hash to the same sequence. To
this end, consider an optimal traversal T of P and Q with respect to the discrete Fréchet

8

Locality-sensitive hashing of curves

distance. By Lemma 3, we can assume that |T | ≤ m and each component is a star. Let ℓ
denote the number of components of T . For 1 ≤ k ≤ ℓ denote with Ek the event that not
all vertices of the k-th component are snapped to the same grid point. This happens only if
at least one pair of vertices is separated in at least one dimension by the random shift t.
Since the component is a star, there exists a vertex v of either P or Q, such that v is
involved in all pairs of T in the k-th component. Therefore, all vertices in this component
have distance at most dF (P, Q) to v. Since t is uniformly distributed in [0, δ)d , the probability
that any pair is separated along any fixed dimension is 2dF (P, Q) /δ. As a consequence, event
Ek happens with probability at most 2d · dF (P, Q) /δ.
By a union bound over the ℓ components in T , we have that the probability of P and Q
not being hashed to the same sequence is bounded by


[
X
dF (P, Q)
P r
Ek  ≤
P r(Ek ) = 2dm ·
δ
1≤k≤ℓ

1≤k≤ℓ

and the lemma follows.

◭

◮ Lemma 6. For any value of δ and for any P, Q ∈ ∆d ,√if there exists a value of t ∈ [0, δ)d
such that htδ (P ) = htδ (Q), then it holds that dF (P, Q) ≤ d · δ.
Proof. In the case that htδ (P ) = htδ (Q), it holds that dF (htδ (P ), htδ (Q)) = 0. Snapping
a
√
curve to the randomly shifted grid changes the position of each vertex by at most 2d · δ.
√

Therefore, it holds that dF (P, htδ (P )) ≤ 2d · δ and similarily dF (Q, htδ (Q)) ≤
triangle inequality,
 √


dF (P, Q) ≤ dF htδ (P ), P + dF htδ (P ), htδ (Q) + dF htδ (Q), Q ≤ d · δ.

√

d
2

· δ. By the

◭
The next theorem follows by plugging in the bounds of Lemmas 5 and 6.
◮ Theorem 7. Let P, Q ∈ ∆d be two curves with m1 and m2 points, respectively, and let
3
m = min{m1 , m2 }, δ = 4dmr and c = 4d 2 m. It holds that:
(i) if dF (P, Q) < r, then P rHLδ (htδ (P ) = htδ (Q)) > 21 ;
(ii) if dF (P, Q) > cr, then P rHLδ (htδ (P ) = htδ (Q)) = 0.
Proof. The first claim follows by plugging in the bounds of Lemma 5:



dF (P, Q)
1
dF (P, Q)
>1−
> .
P r htδ (P ) = htδ (Q) > 1 − 2dm ·
δ
2r
2
On the other hand, the second claim follows from Lemma 6:
√
dF (P, Q) > c · r = 4d3/2 mr = d · δ ⇒ htδ (P ) 6= htδ (Q).
◭

4

Constant approximation factor

In the previous section we analyzed a very efficient LSH with linear approximation factor.
On the other end of the spectrum, we can also design an LSH with constant approximation
factor, but higher running time. Conceptually, the easiest way to do this is to randomly and
independently perturb the vertices of each curve and snap them to a fixed grid.

A. Driemel and F. Silvestri

4.1

Algorithm

The described scheme is asymmetric. We assume that we have two types of curves, which
we call input curves and query curves. Consider an input curve P = p1 , . . . , pm , and let Gδ
be the canonical d-dimensional grid of resolution δ defined in the previous section. Let tP =
t1 , . . . , tm be a sequence of independent random variables which are uniformly distributed

d
in − 2δ , 2δ . We perturb the vertices of P : Let P ′ = p′1 , . . . , p′m be the perturbed curve with
p′i = pi + ti . We snap the curve P ′ to the grid Gδ . More precisely, we replace each vertex p′i
with its closest grid point p′′i = arg minq∈Gδ kp′i − qk to obtain the curve P ′′ . In the next step
we remove consecutive duplicates in P ′′ . That is, we remove the vertex p′′i if it is identical
to p′′i−1 . We define htδP (P ) to be the result of this algorithm.
For a query curve Q, the hash function is the same. However, a different random sequence
tQ is used for randomly perturbing the curve. We let HδC denote the LSH scheme defined
t
this way: namely, HδC contains all pairs (htδP , hδQ ), where vectors tP and tQ consist of entries
 δ δ d
independent and identically distributed in − 2 , 2 .

4.2

Analysis

◮ Lemma 8. Let P, Q ∈ ∆d be two curves with m1 and m2 points, respectively. Let m =
min{m1 , m2 } and let M = max{m1 , m2 }. For any δ > 0, it holds that
P rHCδ



htδP (P )

=



t
hδQ (Q)

 dm 
dM
1
1 dF (P, Q)
≥
·
−
2
2
δ

In particular, if δ > 4dF (P, Q), then the probability is strictly lower bounded by 2−2d(m1 +m2 ) .
Proof. Note that for dF (P, Q) ≥ δ2 the claim is trivially true. Therefore, assume that
dF (P, Q) < 2δ . For simplicity assume first that d = 1. We bound the probability that P
and Q do not hash to the same sequence. To this end, consider an optimal traversal T of
P and Q with respect to the discrete Fréchet distance. By Lemma 3, we can assume that
|T | ≤ m1 + m2 and each component is a star. Let ℓ denote the number of components of
T . For 1 ≤ k ≤ ℓ denote with Ek the event that not all vertices of the k-th component
are snapped to the same grid point. Assume that the center of the k-th star is a vertex
pi of P and that the other vertices of the component are vertices qj , . . . , qj+ck of Q. The
analysis for the case where the center is a vertex of Q is analogous. There must be a grid
point in either one of the two intervals to the left and to the right of pi : Il = [pi − 2δ , pi )
and Ir = [pi , pi + 2δ ). We analyze the case that there is a grid point in Ir , the other case is
m1
, it
analogous. Let Xi be the event that p′i ∈ Ir . Since tP is uniformly random in − δ2 , 2δ
1
′
holds that P r(Xi ) ≥ 2 . Now, let Yj be the event that qj ∈ Ir . If qj was in pi ’s component,
then there are two cases. Either qj lies in Il or in Ir . In the first case, we have
P r(Yi ) ≥

δ
2

− |pi − qj |
1 d(P, Q)
≥ −
,
δ
2
δ

and in the second case we have P r(Yi ) ≥ 12 . We can bound the probability that all vertices
in the k-th component snap to the same grid point
c


1
1 d(P, Q) k
P r Ek ≥ P r(Xi ∩ Yj ∩ · · · ∩ Yj+ck ) ≥ ·
−
2
2
δ
If all components are preserved, then the two curves will hash to the same sequence,

9

10

Locality-sensitive hashing of curves

therefore



t
P r htδP (P ) = hδQ (Q)



≥ P r
≥

\

1≤k≤ℓ

Ek  ≥

Y

1≤k≤ℓ

P r Ek



Y 1 1 d(P, Q) ck  1 ℓ  1 d(P, Q) m1 +m2 −ℓ
≥
.
−
−
2 2
δ
2
2
δ

1≤k≤ℓ






P
= m1 + m2 − ℓ. Indeed, each center of
The last inequality follows since
c
k
1≤k≤ℓ
a component can be charged to this component and the remaining vertices make up the
sum of the leaves of all components. The lemma is now implied for d = 1 observing that
ℓ ≤ min{m1 , m2 }, as implied by Lemma 3. We get the lemma for general d by observing
that the dimensions are independent.
◭
The following result then holds.
◮ Theorem 9. Let P, Q ∈ ∆d be two curves with m1 and m2 points, respectively, and let
δ = 4dr and c = 4d3/2 . It holds that


2d(m1 +m2 )
t
(i) if dF (P, Q) < r, then P rHCδ htδP (P ) = hδQ (Q) > 12
;


t
(ii) if dF (P, Q) > cr, then P rHCδ htδP (P ) = hδQ (Q) = 0.
Proof. The theorem follows by plugging in the bounds of Lemma 8 and by using same
◭
arguments as in the proof of Lemma 6.

5

Trade-off between approximation factor and query time

In the previous two sections we have seen schemes with linear and constant approximations.
We now suggest a scheme exhibiting a trade-off between the collision probability of near
points and the approximation factor. The basic idea is to randomly partition the input
curves and to concatenate the outcome of the basic LSH (Section 3) applied to the different
parts of the curves.

5.1

Algorithm

The scheme is asymmetric.
call input and query curves.
the partition. For an input
subsequences. To this end,

Again, we assume that we have two types of curves, which we
The difference in how they are handled lies in the way we create
curve P = p1 , . . . , pm , we randomly sample a partitioninto K
we denote a partition of P with Φs (P ) = Pb1 , . . . , PbK where

the subsequences are defined by a monotone sequence s ∈ [m]K−1 as follows.

PbK = psK−1 , . . . , pm .
∀ 1 < i < K : Pbi = psi−1 , . . . , psi ;

There are at most m+K−1
ways to partition a curve of length m in this way. We denote
K−1
with PK the family of all valid partitions for a given m. Let t = t1 , . . . , tK be a sequence
of independent random values evenly distributed in [0, δ)d . Once we have partitioned the
input curve P into K (overlapping) subsequences, we apply the basic LSH to each individual
subsequence and concatenate the resulting curves:
 
 
 
t,s
gδ,K
(P ) = htδ1 Pb1 ⊕ htδ2 Pb2 ⊕ · · · ⊕ htδK PbK .
Pb1 = p1 , . . . , ps1 ;

A. Driemel and F. Silvestri

11

A query curve Q = q1 , . . . , qm is subdivided into K equal-sized subsequences (deterministically), where the last subsequence may be shorter and two consecutive sequences overlap
by one element. We denote with Φ∗ (Q) this partitioning into equal-sized subsequences. For
t,∗
query curves, we define gδ,K
(Q) to be the resulting curve given by applying the basic LSH
to each individual subsequence and concatenating the resulting curves.
T
For any given δ > 0 and K ≥ 1, we denote with Hδ,K
the family of asymmetric hash
t,s
t,∗
T
functions created this way: that is, Hδ,K
consists of tuples (gδ,K
, gδ,K
) where the entries of
d
s
t are independently and identically distributed in [0, δ) and Φ (P ) is uniformly chosen at
random from PK .

5.2

Analysis

We have the following theorem which generalizes Theorem 7. Using the parameter K we
get a tradeoff between approximation factor and query time.
◮ Theorem 10. Let P, Q ∈ S be two curves with m1 and m2 points,

 Mlet
 M respectively, 3and
2
M = max{m1 , m2 }. Let K ≥ 1 be a given integer and let δ = 4dr · K and c = 4d · K .
It holds that


K M+K−1−1
t,s
t,∗
(P ) = gδ,K
(Q) ≥ 21
(i) if dF (P, Q) < r, then P rHTδ,K gδ,K
· K−1
;


t,s
t,∗
(P ) = gδ,K
(Q) = 0.
(ii) if dF (P, Q) > cr, then P rHTδ,K gδ,K
Proof. We first prove (i). Let T be an optimal traversal of P and Q. We say two partitions
Φs (P ) and Φr (Q) are consistent with respect to T if and only if (si , ri ) ∈ T for all 1 ≤
i ≤ K − 1. Let E denote the event that the partition Φs (P ) used in the hash functions
is consistent with Φ∗ (Q) with respect to T . By construction this happens for at least
one of the partitions in PK . Therefore, P r(E) ≥ |P1K | . Now, let Ei be the event that
 
 
b i . By Lemma 5 we have that
htδi Pbi = htδi Q



  
bi
dF Pbi , Q
dF (P, Q)
1
M
′


·
≥
≥ 1 − 2d
P r(Ei | E) ≥ 1 − 2dm ·
δ
K
δ
2


 
in the above inequality, since m′ is the length of the
Note that we can assume m′ ≤ M
K
b
shorter
 Mof the two subsequences in the lemma. By construction, the length of Qi will be at
most K .
Since the values ti are chosen pairwise independent, we have


 K


Y
1
1
t,s
t,∗


·
P rHTδ,K gδ,K (P ) = gδ,K (Q) ≥
P r(Ei | E) · P r(E) ≥
2
|PK |
1≤i≤K


Using |PK | ≤ M+K−1
, the first part of the claim follows.
K−1
As for the second part of the claim, we can use Lemma 6 applied to the subsequences.
If there
of P , and there exist t = t1, . . . , tK, such that for all 0 ≤ i ≤ K

  existsa partition
√
ti b
ti b
b i ≤ d · δ. In this case, we can
hδ Pi = hδ Qi , then it holds by Lemma 6 that dF Pbi , Q
combine the traversals of the subsequences to a traversal of the entire
√ curves. This combined
traversal has the same cost, therefore it follows that dF (P, Q) ≤ d · δ. Consequently, if
√
4d 2 M
r = d · δ,
K
3

dF (P, Q) > cr =

12

Locality-sensitive hashing of curves
then it cannot happen that gδt,s (P ) = gδt,∗ (Q) for any combination of t = t1 , . . . , tK and
◭
s.
◮ Corollary 11. Let P, Q ∈ S be two curves with m1 and m2 points,

 Mlet
 respectively, 3and
2 ·
and
c
=
4d
M = max{m1 , m2 }. Let K ≥ 1 be a given integer and let δ = 4dr · M
K
K .
It holds that


K 1 K−1
t,s
t,∗
· M
;
(i) if dF (P, Q) < r, then P rHTδ,K gδ,K
(P ) = gδ,K
(Q) > 14


t,s
t,∗
(P ) = gδ,K
(Q) = 0.
(ii) if dF (P, Q) > cr, then P rHTδ,K gδ,K
Proof. The result just follows from the previous Theorem 10 by observing that
1/(2M )k−1 .

6


M+K−1 −1
K−1

≥
◭

Handling constrained alignments

We now focus on LSH for discrete Fréchet distance with constraints on the alignment. We
first target the w-anchored distance in Section 6.1, and then the w-speed distance in Section 6.2. As in the previous sections, the schemes are asymmetric and consist of a partitioning
of the curve into subsequences and on the application of the basic LSH scheme to each subsequence. However, the partitions are different since they leverage on random processes on
both input and query curves, consecutive subsequences do not overlap, and the constraints
are exploited. We let ℓ ≥ 1 denote an arbitrary given integer that allows to trade-off the
collision probability of near curves with a bi-criteria approximation on the distance and on
the anchored alignment.

6.1

LSH for anchored distances

Consider an input curve P = p1 , . . . , pm and let rP = rP,1 , rP,2 , . . . rP,m and t = t1 , t2 , . . . , tm
denote sequences of independent and identically distributed random variables in [1, w/2] and
[0, δ)d respectively, where δ is a suitable parameter defined later. The partition of P consists
of a fixed partitioning into subsequences of length ℓ, followed by a random perturbation of
subsequence lengths. Specifically, the following three operations are performed:
c′ 1 , . . . , P
c′ K ′ with K ′ = ⌈m/ℓ⌉ of size ℓ, with the
(i) Partition P into subsequences P
′
possible exception of the last subsequence. Let s′ ∈ [m]K +1 be the vector denoting
the final indexes of each subsequence, that is Pbi = p(s′ +1) , . . . , ps′i : we have s′0 = 0,
i−1

s′K ′ = m and s′i = iℓ for each 1 ≤ i < K ′ .
(ii) Random perturb the final index of each subsequence with the random vector rP : for
each 1 ≤ i < K ′ , set si = min{si + rp,2 , m}.
(iii) Clean the partition by removing overlaps among subsequences: for each 1 ≤ i < K ′
and starting from i = 1, remove each subsequence where s′i ≤ s′j for some j < i. We


let ΦrP (P ) = Pb1 , . . . , PbK denote the resulting partition of P with K ≤ ⌈m/ℓ⌉ and

let sP ∈ [m]K+1 be the resulting vector denoting the final indexes of each subsequence
(note that each subsequence has now length at most ℓ + w).
Once curve P has been partitioned into K subsequences, we apply the basic LSH in
Section 3 to each subsequence using the random shifts given by sequence t. Specifically, we
snap the i-th subsequence Pbi on a grid of side δ shifted by the random value ti and remove
consecutive duplicates within each subsequence;
the remaining values denote the hash value
 
t,rP
(P ) of curve P is the
of Pbi and we denote them with htδi Pbi . The final hash value gw,δ,ℓ

A. Driemel and F. Silvestri

array containing the hash of each subsequence, specifically:
 
 
  
t,rP
(P ) = htδ1 Pb1 , htδ2 Pb2 , . . . , htδK PbK .
gw,δ,ℓ

We observe that the final hash value is not a curve as in previous sections, but an array of
curves. Equality between two curves then holds only if the two hash values have the same
length and coincide in each position (i.e., the hash values ((a, b), (c)) and ((a), (b, c)) do not
collide, but they collide if their are considered as a single curve (a, b, c)). This enforces the
alignment constraint.
The hash process of a query curve Q is the same: however, a different random sequence
rQ is used to partition the curve, while the same sequence t of random shifts is kept. Due
A
to the different random bits in rQ the proposed LSH scheme is asymmetric. We let Hw,δ,ℓ


t,rQ
t,rP
.
, gw,δ,ℓ
denote the hash family consisting of all possible pairs of hash functions gw,δ,ℓ
The next Theorem 14 shows that the scheme has a bi-criteria approximation: In addition
to the distance approximation c, the scheme has also an approximation on the alignment.
As an example, we observe that two curves with a w-anchored distance larger than cr can
still collide if they have a w + 2(ℓ − 1)-anchored distance lower than cr. In order to prove
the theorem, we introduce the two following lemmas.
◮ Lemma 12. Let P, Q ∈ S be two curves with m1 and m2 points, respectively and let
m = min{m1 , m2 }. Let w be the
integer, δ = 4drℓ. If
 traversal width, ℓ ≥1 be an√arbitrary
2m/ℓ
t,rQ
t,rP
dw,aF (P, Q) < r, then P rHAw,δ,ℓ gw,δ,ℓ (P ) = gw,δ,ℓ(Q) > 1/ 2w
.

Proof. Let T be an optimal w-anchored traversal of P and Q, and let c1 , . . . cv denote the
v non-overlapping components, and let πi and γi denote the indexes of the components
containing pi and qi , respectively. The two curves collide when the following two events
happen for every 1 ≤ i ≤ ⌈m/ℓ⌉:
Event E1,i : sP,i = MP,i and sQ,i = MQ,i , where MP,i and MQ,i are the indexes of the
rightmost vertices of P and Q in cπiℓ−1 and cγiℓ−1 .
Event
values of the i-th subsequences of P and Q are the same (i.e.,

 hash
 E2,i : the
ti b
ti b
h Pi = h Qi ).
δ

δ

Intuitively, the first event guarantees that the components of T are not cut by the random
partition, while the second event requires the basic LSH to work on each subsequence. We
Tj
show by induction that event Ej = i=1 (E1,i ∩ E2,i√) (i.e., both events hold for the first j
subsequences) happens with probability at least 1/( 2w)2j , for 1 ≤ j < K = ⌈m/ℓ⌉.
Assume j = 1. By definition of w-anchored traversal, we have iℓ ≤ MP,1 , MQ,1 ≤ iℓ+w/2.
Event E1,1 happens with probability 1/w2 , that is when the random shift moves the final
b i in MP,i and MQ,1 , respectively. Conditioning on E1,1 , event E2,1 holds
indexes of Pbi and Q
with probability at least 1/2: indeed by Lemma 5 we have that





bi
dF Pbi , Q
1
dw,aF (P, Q)


≥ .
≥ 1 − 2dℓ ·
P r(E2,1 | E1,1 ) ≥ 1 − 2dℓ ·
δ
δ
2
Therefore, event E1 happens with probability 1/(2w2 ). √
Suppose now that Ej−1 holds with probability 1/( 2w)2(j−1) and let j < K. Since
b j−1 , we have P r(E1,j | Ej−1 ) =
MP,j−1 and MQ,j−1 are the last indexes in segments Pbj−1 and Q
2
1/w by mimic the argument with j = 1. Further, we have that
2,j | E1,j ) ≥ 1/2. There√ P r(E
2j
fore P r(Ej | Ej−1 ) = P r(E1,j | Ej−1 ) ∗ P r(E2,j | E1,j ) ≥ 1/( 2w) .

13

14

Locality-sensitive hashing of curves
bK
When j = K, we have that P r(E1,K | EK−1 ) = 1 since the end points of PbK and Q
are fixed on pm1 and Qm2 . By the inductive assumption, the shortest sequence between PbK
b K contains less than x = m mod ℓ vertices. Then, we have
and Q



bi
dF Pbi , Q
≥1− x ≥ 1 .
P r(E2,K | E1,K ) ≥ 1 − 2dx ·
δ
2ℓ
2x/ℓ
Since K = ⌈m/ℓ⌉ and x = m mod ℓ, the two curves
and Q collide with probability
√ P
2m/ℓ
2 K−1
x/ℓ
.
◭
P r(EK−1 ) P r(E2,K ) ≥ (1/(2w )
)(1/2 ) ≥ 1/( 2w)
◮ Lemma 13. Let P, Q ∈ S be two curves with m1 and m2 points, respectively and let
m = min{m1 , m2 }. Let w be the traversal width, ℓ ≥ 1 be an arbitrary integer,
 δ = 4drℓ,
3
t,rQ
t,rP
2
and c = 4d ℓ. If d(w+2(ℓ−1)),aF (P, Q) > cr, then P rHAw,δ,ℓ gw,δ,ℓ(P ) = gw,δ,ℓ(Q) = 0.

Proof. By hypothesis, the two curves P and Q have wℓ-anchored Fréchet distance larger
than cr, which implies there cannot be a wℓ-anchored traversal with cost smaller than or
equal to cr. Assume that P and Q collide under the described hashing scheme; then both
b
curves have been split into K subsequence and the hash values of Pbi and
√ Qi , for each
1 ≤ i ≤ K collide. By Lemma 6, there exists a traversal of cost at most dδ between Pbi
b i , for each i. Moreover, this traversal is a w + 2(ℓ − 1)-anchored traversal since the
and Q
b i differ by at most w/2+ℓ−1.
partitioning guarantees that the indexes of vertices in Pbi and Q
This
√ however implies that there exist a w + 2(ℓ − 1)-traversal of P and Q of cost at most
dδ = cr, which is a contradiction. Therefore, two curves with (w + 2(ℓ − 1))-anchored
◭
discrete Fréchet distance cannot collide.
◮ Theorem 14. Let P, Q ∈ S be two curves with m1 and m2 points, respectively and let
3
m = min{m1 , m2 }. Let ℓ ≥ 1 be an arbitrary integer, δ = 4drℓ, and c = 4d 2 ℓ. Then, it
holds that:


√ 2m/ℓ
t,rQ
t,rP
(Q) > 1/ 2w
(P ) = gw,δ,ℓ
(i) if dw,aF (P, Q) < r, then P rHAw,δ,ℓ gw,δ,ℓ
;


t,rQ
t,rP
(Q) = 0.
(P ) = gw,δ,ℓ
(ii) if d(w+2(ℓ−1)),aF (P, Q) > cr, then P rHAw,δ,ℓ gw,δ,ℓ
Proof. The theorem follows from Lemmas 12 and 13.

6.2

◭

LSH for bounded-speed distances

Consider an input curve P = p1 , . . . , pm and let rP = rP,1 , rP,2 , . . . , rP,m and t = t1 , t2 , . . . tm
denote sequences of independent and identically distributed random variables in [1, wℓ] and
[0, δ)d respectively. We random partition curve P into non overlapping
subsequences
of


s
b
b
length given by the random sequence rp . Specifically, let Φ (P ) = P1 , . . . , PK denote

a partition of P with m/(wℓ) ≤ K ≤ m and let s ∈ [m]K+1 be the vector denoting the
initial and final indexes of a subsequence, that is Pbi = psi−1 +1 , . . . , psi . Then, s satisfies the
following conditions : (i) s0 = 0 and sK = m, (ii) for 1 ≤ i ≤ K, si − si−1 = rp,1 , which
P
implies that si = ij=1 rp,1 . Once we have partitioned curve P into K subsequences, we
continue as in the w-anchored LSH by applying the basic LSH to each subsequence using
the random shifts given by sequence t. For a query curve Q, the hash process is the same,
S
but a different random sequence rQ is used to partition the curve. We let Hw,δ,ℓ
denote the


t,rQ
t,rP
hash family consisting of all possible pairs of hash functions gw,δ,ℓ, gw,δ,ℓ .
The following Theorem 17 shows that the scheme has a bi-criteria approximation (note
that the alignment approximation in point (ii) differs from the one for the anchored distance).
Its proof depends on the next two lemmas.

A. Driemel and F. Silvestri

15

◮ Lemma 15. Let P, Q ∈ S be two curves with m1 and m2 points, respectively and let
m = min{m1 , m2 }. Let w be the
integer, δ = 4drℓ. If
 traversal width, ℓ ≥1 be an√arbitrary
2m/ℓ
t,rQ
t,rP
dw,sF (P, Q) < r, then P rHSw,δ,ℓ gw,δ,ℓ(P ) = gw,δ,ℓ(Q) > 1/ 2wℓ
.
Proof. Let T be an optimal w-speed traversal of P and Q, and let c1 , . . . cv denote the v
non-overlapping components. As for the anchored version, the two curves collide when the
following two events happen for every 1 ≤ i ≤ ⌈v/ℓ⌉ (note a different definition for event
E1,i ):
Event E1,i : all nodes of P and Q in components ciℓ+1 , . . . , c(i+1)ℓ are contained in the
i-th subsequence of P and Q;
Event
values of the i-th subsequences of P and Q are the same (i.e.,

 hash
 E2,i : the
ti b
ti b
h Pi = h Qi ).
δ

δ

The proof continues as in Lemma 12, where the only difference is in the probability of event
E1,i . Indeed, we have that event E1,1 happens with probability 1/(wℓ)2 , that is when P1
and Q1 contain only the at most wℓ nodes of P and Q in the first ℓ components. The same
probability holds for E1,i , conditioning on E1,i−1 .
◭

◮ Lemma 16. Let P, Q ∈ S be two curves with m1 and m2 points, respectively and let
m = min{m1 , m2 }. Let w be the traversal width, ℓ ≥ 1 be an arbitrary integer, δ = 4drℓ,
3
t,rQ
t,rP
(Q) = 0.
(P ) = gw,δ,ℓ
and c = 4d 2 ℓ. If dwℓ,sF (P, Q) > cr, then P rHSw,δ,ℓ gw,δ,ℓ
Proof. By hypothesis, the two curves P and Q have wℓ-speed discrte Fréchet distance larger
than cr, which implies there cannot be wℓ-speed traversal with cost smaller than or equal
to cr. Assume that P and Q collide under the described hashing scheme; then both curves
have been split into K subsequence and the hash values of Pi √
and Qi , for each 1 ≤ i ≤ K
collide. By Lemma 6, there exists a traversal of cost at most dδ between Pi and Qi , for
each i. Moreover, this traversal is a wℓ-traversal since each subsequence contains at most
wℓ nodes.
√ This however implies that there exist a wℓ-speed traversal of P and Q of cost
at most dδ = cr, which is a contradiction. Therefore, two curves with wℓ-speed Fréchet
◭
distance cannot collide.
◮ Theorem 17. Let P, Q ∈ S two curves with m1 and m2 points, respectively and let
3
m = min{m1 , m2 }. Let ℓ ≥ 1 be an arbitrary integer, δ = 4drℓ, and c = 4d 2 ℓ. Then, it
holds that:


√
2m/ℓ
t,rQ
t,rP
;
(Q) > 1/ 2wℓ
(P ) = gw,δ,ℓ
(i) if dw,sF (P, Q) < r, then P rHSw,δ,ℓ gw,δ,ℓ


t,rQ
t,rP
(ii) if dwℓ,sF (P, Q) > cr, then P rHSw,δ,ℓ gw,δ,ℓ (P ) = gw,δ,ℓ(Q) = 0.
Proof. The proof follows from Lemmas 15 and 16.

7

◭

Extensions to dynamic time warping

All our schemes can be applied to DTW without any algorithmic change, and in this section
we analyze some of them. We first investigate in Section 7.1 the basic scheme in Section 3.1
for this distance. Then, we provide a few insights on DTW with constrained alignments in
Section 7.2. We do not analyze the techniques proposed in Sections 4 and 5 since they have
the same linear approximation of the basic LSH, and—in contrast to our previous results
for the Fréchet distance—do not provide a sublinear approximation for DTW.

16

Locality-sensitive hashing of curves

7.1

Analysis of the basic LSH

◮ Lemma 18. Let P, Q ∈ ∆d be two curves with m1 and m2 points, respectively. For any
δ ≥ 0, it holds that



dDTW (P, Q)
t
t
.
P rHLδ hδ (P ) = hδ (Q) ≥ 1 − d ·
δ
Proof. Let T be an optimal traversal of P and Q with respect to their DTW distance.
Let ℓ = |T | and denote with dk the distance kpik − qjk k for 1 ≤ k ≤ ℓ. We have that
P
dDTW (P, Q) = 1≤k≤ℓ dk .
Now, we bound the probability that pik and qjk for some fixed (ik , jk ) ∈ T are not
snapped to the same grid point. As in the proof of Lemma 5, two points are separated, if
and only if they are separated in at least one of their coordinate dimensions.
Denote with Ek the event that the pair is separated by the random shift t, where t is
uniformly distributed in [0, δ)d . By a union bound over the pairs in T , we have that the
probability of P and Q not being hashed to the same curve is bounded by


X
[
X
X
dDTW (P, Q)
dk
kpik − qjk k
=
=d·
d·
P r
Ek  ≤
P r(Ek ) ≤
d·
δ
δ
δ
1≤k≤ℓ

1≤k≤ℓ

1≤k≤ℓ

1≤k≤ℓ

and the lemma follows.

◭

◮ Lemma 19. Let P, Q ∈ ∆d be two curves with m1 and m2 points, respectively, and let
d
t
t
M = max{m1 , m2 } and δ ≥ 0. If there
√ exists a value of t ∈ [0, δ) such that hδ (P ) = hδ (Q),
then it holds that dDTW (P, Q) ≤ 2M d · δ.
Proof. The DTW distance does not satisfy the triangle inequality, however we can use a
similar argument as in the proof of Lemma 6. Assume that htδ (P ) = htδ (Q) is true from some
b = ht (Q). Let Pb = pb1 , . . . , pbs and Q
b = qb1 , . . . , qbs .
t ∈ [0, δ)d and denote Pb = htδ (P ) and Q
δ
b
b
We have for 0 ≤ r ≤ s that kpbr − qbr k = 0. Recall that P (and respectively, Q) was generated
b t and by contracting each sequence of identical
by snapping each point of P to the grid G
δ
vertices to one copy of the same vertex. We replace each pbr by the original sequence of
(1)
(a)
identical vertices pbr , . . . , pbr (and we do the same for each qbr , denoting its sequence of
(1)
(b)
identical vertices by qbr , . . . , qbr ). Now, consider a traversal T of the resulting sequences
(1)
(1)
(i)
(1)
that pairs each pbr with qbr . Furthermore, if a > 2, then T pairs each pbr with qbr and
(a)
(i)
(a)
(b)
if b > 2, then T pairs pbr with each qbr . Finally, T pairs pbr with qbr , for each r. The
resulting traversal T can also be applied to the original curves
√ P and Q. By the construction
b any two paired vertices have distance at most d · δ, since they snapped to the
of Pb and Q,
same grid point. It follows that
X √
X
X
√
kp
−
q
k
≤
d · δ ≤ 2M dδ,
dDTW (P, Q) = min
kp
−
q
k
≤
i
j
i
j
k
k
k
k
′
T ∈T

(ik ,jk )∈T ′

(ik ,jk )∈T

(ik ,jk )∈T

where the last step can be obtained by observing that |T | ≤ m1 + m2 ≤ 2M .

◭

◮ Theorem 20. Let P, Q ∈ ∆d be two curves with m1 and m2 points, respectively, and let
3
M = max{m1 , m2 }, δ = 2dr and let c = 4d 2 M .
(i) if dDTW (P, Q) < r, then P rHLδ (htδ (P ) = htδ (Q)) > 12 ;
(ii) if dDTW (P, Q) > cr, then P rHLδ (htδ (P ) = htδ (Q)) = 0.
Proof. The proof follows by plugging in the bounds of δ in Lemmas 18 and 19.

◭

A. Driemel and F. Silvestri

7.2

17

Handling constrained alignments

The schemes in Section 6 for w-anchored/speed traversals automatically apply to DTW
distance, with the same collision probabilities stated in Theorems 14 and 17. However, the
approximation factor is 4d3/2 (m1 + m2 ), where m1 and m2 are curve lengths. The claim
follows by mimicking the proofs for the Fréchet distance and use the bounds in Theorem 20.
We provide the analysis only for the w-anchored DTW distance, being the one for w-speed
DTW essentially the same.
◮ Lemma 21. Let P, Q ∈ S be two curves with m1 and m2 points, respectively and let
m = min{m1 , m2 }. Let w be the traversal
width, ℓ ≥ 1 be
integer, δ = 2dr. If
 an arbitrary

√ 2m/ℓ
t,rQ
t,rP
dw,aDTW (P, Q) < r, then P rHAw,δ,ℓ gw,δ,ℓ (P ) = gw,δ,ℓ(Q) > 1/ 2w
.

Proof. The proof mimics the one for the w-anchored Fréchet distance in Lemma 12. The
only difference is in the value of δ required to get P r(E2,i | E1,i ) ≥ 1/2, since, by Lemma 18,
the
  of the i-th subsequences of P and Q collide with probability at least 1 −
 hash values
bi ,Q
bi
dF P
, which is independent of the number of components.
d·
◭
δ
◮ Lemma 22. Let P, Q ∈ S be two curves with m1 and m2 points, respectively. Let w be
3
the traversal width, ℓ ≥ 1 be an arbitrary integer, δ = 2dr, and c = 4d 2 (m1 + m2 ). If
t,r

t,rP
Q
(Q) = 0.
(P ) = gw,δ,ℓ
d(w+2(ℓ−1)),aDTW (P, Q) > cr, then P rHAw,δ,ℓ gw,δ,ℓ

Proof. The proof is almost the same of the one for Lemma 13 and the only difference is in
the approximation
√ provided by the basic LSH. Indeed, by Lemma 6, there exists a traversal
b for each i, where Mi denote the length of the
of cost at most d2Mi δ between Pbi and Q
PK i
longest sequence. However, we have i=1 Mi ≤ m1 + m2 and δ = 2dr. Therefore the final
◭
approximation is c = 4d3/2 (m1 + m2 ).
◮ Theorem 23. Let P, Q ∈ S be two curves with m1 and m2 points, respectively, and let
3
m = min{m1 , m2 }. Let ℓ ≥ 1 be an arbitrary integer, δ = 2dr, and c = 4d 2 (m1 + m2 ).
Then, the above hashing scheme guarantees

 that:
√ 2m/ℓ
t,rQ
t,rP
(Q) > 1/ 2w
(P ) = gw,δ,ℓ
(i) if dw,aDTW (P, Q) < r, then P rHAw,δ,ℓ gw,δ,ℓ
;


t,rQ
t,rP
(ii) d(w+2(ℓ−1)),aDTW (P, Q) > cr, then P rHAw,δ,ℓ gw,δ,ℓ (P ) = gw,δ,ℓ(Q) = 0.
Proof. The theorem follows from Lemmas 21 and 22.

8

◭

Conclusion

To the best of our knowledge, this is the first paper providing LSH schemes for curves. When
applied to the near neighbor problem, our techniques improve the state of the art for the
discrete Fréchet distance [17] under different settings, and provide the first data structure
with theoretical guarantees for DTW. The methods presented are simple enough that they
may be practical. We do not know if our bounds are tight. It would be interesting to know if
lower bounds can be obtained for the studied problem and/or to improve the upper bounds.
All of the presented LSH schemes exhibit the property that no collisions happen between
far points (i.e., α2 = 0). An open question is to understand if it is possible to slightly
increase this collision probability (say α2 = 1/n) to get a better approximation factor.
Another interesting direction would be to reduce space by exploiting the independence in
the approach described in Section 4.1, or by using a multiprobe approach [24]. Finally, we
remark that our results only partially extend to DTW. As such, it is still open to get a

18

Locality-sensitive hashing of curves

sublinear approximation for DTW. We hope that our work inspires further work in one of
these directions.
Acknowledgements The authors would like to thank Rasmus Pagh and the anonymous
reviewers for useful comments. This research was initiated at the Dagstuhl Seminar 16101
"Data Structures and Advanced Models of Computation on Big Data, 2016".
References
1
2

3

4

5
6
7
8
9
10
11

12
13
14
15
16
17
18

S. Arya, D. M. Mount, A. Vigneron, and J. Xia. Space-time tradeoffs for proximity searching
in doubling spaces. In Proc. 16th European Symp. Algorithms (ESA), pages 112–123, 2008.
A. Backurs and A. Sidiropoulos. Constant-distortion embeddings of Hausdorff metrics into
constant-dimensional lp spaces. In Proc. 19th Workshop on Approximation Algorithms for
Combinatorial Optimization Problems (APPROX), volume 60, pages 1:1–1:15, 2016.
Y. Bartal, L.-A. Gottlieb, and O. Neiman. On the impossibility of dimension reduction for
doubling subsets of ℓp . In Proc. 13th Symp. on Computational Geometry (SOCG), pages
60:60–60:66, 2014.
K. Bringmann. Why walking the dog takes time: Fréchet distance has no strongly subquadratic algorithms unless seth fails. In Proc. 55th Symp. on Foundations of Computer
Science (FOCS), pages 661–670, 2014.
J. C. Brown and P. J. O. Miller. Automatic classification of killer whale vocalizations using
dynamic time warping. J. of the Acoustical Society of America, 122(2):1201–1207, 2007.
J. Campbell, J. Tremblay, and C. Verbrugge. Clustering player paths. In Proc. 10th Int.
Conf. on the Foundations of Digital Games (FDG), 2015.
M. de Berg, A. F. Cook, and J. Gudmundsson. Fast Fréchet queries. Comput. Geom.,
46(6):747–755, 2013.
A. Driemel and S. Har-Peled. Jaywalking your dog: Computing the Fréchet distance with
shortcuts. SIAM J. Computing, 42(5):1830–1866, 2013.
A. Driemel, A. Krivošija, and C. Sohler. Clustering time series under the Fréchet distance.
In Proc. 27th Symp. on Discrete Algorithms (SODA), pages 766–785, 2016.
G. Forestier, F. Lalys, L. Riffaud, B. Trelhu, and P. Jannin. Classification of surgical
processes using dynamic time warping. J. Biomedical Informatics, 45(2):255 – 264, 2012.
J. Gudmundsson and N. Valladares. A GPU approach to subtrajectory clustering using the
Fréchet distance. IEEE Transactions on Parallel and Distributed Systems, 26(4):924–937,
2015.
A. Gupta, R. Krauthgamer, and J. R. Lee. Bounded geometries, fractals, and low-distortion
embeddings. In Proc. 44th Symp. Found. Comp. Science (FOCS), pages 534–543, 2003.
S. Har-Peled, P. Indyk, and R. Motwani. Approximate nearest neighbor: Towards removing
the curse of dimensionality. Theory of Computing, 8(1):321–350, 2012.
B. Huang and W. Kinsner. ECG frame classification using dynamic time warping. In Proc.
Canadian Conf. on Electrical and Computer Engineering, volume 2, pages 1105–1110, 2002.
P. Indyk. On approximate nearest neighbors in non-euclidean spaces. In Proc. 39th Symp.
on Foundations of Computer Science, pages 148–155, 1998.
P. Indyk. On approximate nearest neighbors under l∞ norm. J. Computer and System
Sciences, 63(4):627 – 638, 2001.
P. Indyk. Approximate nearest neighbor algorithms for Fréchet distance via product metrics. In Proc. 18th Symp. on Computational Geometry (SOCG), pages 102–106, 2002.
P. Indyk and J. Matoušek. Low-distortion embeddings of finite metric spaces. In Handbook
of Discrete and Computational Geometry, pages 177–196. CRC Press, 2004.

A. Driemel and F. Silvestri

19
20
21
22

23
24

25
26

27
28
29

30
31

A

P. Indyk and R. Motwani. Approximate nearest neighbors: Towards removing the curse of
dimensionality. In Proc. 30th Symp. Theory of Computing (STOC), pages 604–613, 1998.
R. J. Kenefic. Track clustering using Fréchet distance and minimum description length. J.
of Aerospace Information Systems, 11(8):512–524, 2014.
E. Keogh and C. A. Ratanamahatana. Exact indexing of dynamic time warping. Knowledge
and Information Systems, 7(3):358–386, 2005.
Z. Kovacs-Vajna. A fingerprint verification system based on triangular matching and dynamic time warping. IEEE Transactions on Pattern Analysis and Machine Intelligence,
22(11):1266–1276, 2000.
B. Legrand, C. Chang, S. Ong, S.-Y. Neo, and N. Palanisamy. Chromosome classification
using dynamic time warping. Pattern Recognition Letters, 29(3):215 – 222, 2008.
Q. Lv, W. Josephson, Z. Wang, M. Charikar, and K. Li. Multi-probe lsh: Efficient indexing
for high-dimensional similarity search. In Proc. 33rd Int. Conf. on Very Large Data Bases,
VLDB ’07, pages 950–961. VLDB Endowment, 2007.
J. Matoušek. Embedding finite metric spaces into euclidean spaces. In Lectures on Discrete
Geometry, chapter 15. Springer, 2002.
T. Rakthanmanon, B. Campana, A. Mueen, G. Batista, B. Westover, Q. Zhu, J. Zakaria,
and E. Keogh. Searching and mining trillions of time series subsequences under dynamic
time warping. In Proc. 18th Conf. Knowl. Disc. and Data Mining, pages 262–270, 2012.
C. A. Ratanamahatana and E. J. Keogh. Three myths about dynamic time warping data
mining. In Proc. SIAM Conf. on Data Mining (SDM), pages 506–510, 2005.
G. Shakhnarovich, T. Darrell, and P. Indyk, editors. Nearest-Neighbor Methods in Learning
and Vision: Theory and Practice. MIT Press, 2006.
A. Shrivastava and P. Li. Asymmetric LSH (ALSH) for sublinear time maximum inner
product search (MIPS). In Proc. 27th Conf. on Neural Information Processing Systems
(NIPS), pages 2321–2329, 2014.
G. Vries. Kernel methods for vessel trajectories. PhD thesis, Univ. Amsterdam, 2012.
H. Zhu, J. Luo, H. Yin, X. Zhou, J. Huang, and F. B. Zhan. Mining trajectory corridors
using Fréchet distance and meshing grids. In Proc. 14th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD), pages 228–237, 2010.

Conditional lower bound

There is a trivial reduction from the orthogonal vectors problem to the problem of finding
a close pair under the ℓ∞ distance up to approximation c < 3 [16]. Since ℓ∞ embeds
isometrically into the Fréchet distance (while preserving the dimension up to a constant
factor), this implies a conditional time lower bound for the near-neighbor problem under
the Fréchet distance. In detail, the orthogonal vectors problem can be stated as follows.
Given two sets of vectors A, B ⊂ {0, 1}d with |A| = |B| = n, does there exist a pair a ∈ A
and b ∈ B such that a and b are orthogonal? The orthogonal vectors conjecture, which can
be related to the strong exponential time hypothesis, states that for no ε > 0, there
exists an

algorithm for the orthogonal vectors problem that runs in time O n2−ε poly d if d > log2 n.
This conjecture implies that there exists no data structure for exact near-neighbor searching
under the discrete Fréchet distance
that achieves both preprocessing time in O n2−ε poly m

and query time in O n1−ε poly m for any ε > 0. Indeed, if such a data structure would exist,
then we could solve an instance of orthogonal vectors by storing A in this data structure
and performing a query with each of the vectors of B.

19

