Property Testing of Curve Similarity

We initiate the study of property testing for measures of curve similarity, motivated by the need for fast solutions for curve classification and clustering. Thus, our research lies at the intersection of property testing and computational geometry. While property testing is a very broad area, we believe this intersection has received far less attention than it deserves. We also believe that property testing for well-studied measures such as the Fréchet distance is especially well-motivated due to its connections to other problems studied on the curves, such as clustering [3, 8], similarity search [1, 7, 14] and map reconstruction [4, 5].

Typically in property testing, we are given access to a (large) data set and the goal is to very quickly assess whether the data has a certain property. The classical notation of correctness is typically not suitable for property testing since these algorithms are intended to be randomized algorithms that access (very small) parts of data via queries. Instead, a property testing algorithm is considered correct if it can satisfy the following two conditions, with a probability close to 1 (e.g., at least $1-\gamma$ probability for some small value of $\gamma$): first, if the input has the desired property, the algorithm must return accept and second, if the input is “far” from having the property (under some suitable definition of “far”), the algorithm should reject the input. Our algorithms have one-sided error, meaning, they will not produce false negatives and thus rejection means that the input does not have the desired property.

For further reading on property testing, see [24, 2]. Here, we quickly review the main motivation for property testing in general and then we focus on computational geometry.

Property testing algorithms can be useful in many different scenarios. In particular, if the input is extremely large, it makes sense to obtain a quick approximate answer before deciding to run more expensive algorithms. This is especially useful if the testing algorithm has one-sided error; in that case, if the test returns reject, there is no need to do any extra work. For the Fréchet distance, there are applications [1, 7, 14] where negative filters are used to minimize expensive Fréchet distance computations; testing may be useful in such cases. Property testing is also useful if most inputs are expected to not have the desired property, or the input distribution is such that each input either has the property or it is “far” from having that property. In addition, the definition of property testing has a strong connection to topics in learning theory such as probably approximately correct (PAC) learners and this was in fact one of the important motivations behind its conception [23].

Another motivation for property testing is when small errors can be tolerated or objects that are close to having the desired property are acceptable outcomes; in this view, property testing is in spirit similar to approximation algorithms where an approximate answer is considered to be an acceptable output. In the context of similarity testing we can also compare it to a partial similarity measure. In fact, our chosen error model will be very close to a partial Fréchet distance [6]. For more details on motivations to study property testing see [17, 24]. See also the aforementioned references for more detailed results on property testing as surveying the known results on property testing is beyond the scope of this paper.

Computational geometry has a long tradition of using randomization and sampling to speed up algorithmic approaches [22, 19, 20, 18]. Property testing has received some attention within computational geometry, but is much less explored compared to other areas. There are fast and efficient testers for many basic geometric properties, such as convexity of a point set [13], disjointness of objects [13], the weight of Euclidean minimum spanning tree [10, 11, 12], clustering [21], the Voronoi property of a triangulation [13], ray shooting [9, 13], as well as LP-type problems [15].

Unlike in graph property testing, where it is assumed that we can sample a vertex uniformly at random, and query for its neighbors, it seems that, for geometric data, there is no commonly agreed upon query model. Different types of queries are used to access the data in the above cited works, such as range queries, cone nearest neighbor queries, queries for the bounding box of the data inside a query hyper-rectangle. In our paper, we use queries to the free space matrix of the two input curves, see Section 3 for the precise definition.

We mention that there is also work on matrix testing [16]. Compared to our setting, the input size is defined as $n^2$ – the number of entries needed to specify the matrix. In our case, we assume the input size to be $n$, the maximum of column and row dimension of the matrix.

Let $(M,d)$ be a metric space. We say a (discrete) curve $P$ in $(M,d)$ is an ordered point sequence $⟨p_1,\mathrm{\dots },p_n⟩$ with $p_i\in M$ for all $i=1,\mathrm{\dots },n$. We call the points of the curve vertices. We denote by $\left|P\right|$ the number of vertices in $P$ and by $\mathrm{\ell }(P)$ its length, which is defined as $\mathrm{\ell }(P)={\sum }_{i=1}^{n-1}d(p_i,p_{i+1})$. The subcurve of $P$ between $p_i$ and $p_j$ is denoted by $P[i,j]$. A curve $P$ is called $t$-straight if for any two vertices $p_i$ and $p_j$ in $P$, we have $\mathrm{\ell }(P[i,j])\le t\cdot d(p_i,p_j)$. Denote by $[n]$ the set of integers from $1$ to $n$ and by $[n]\times [n]\subset \mathbb{N}\times \mathbb{N}$ the integer lattice of $n$ times $n$ integers. Given two curves $P=⟨p_1,\mathrm{\dots },p_n⟩$ and $Q=⟨q_1,\mathrm{\dots },q_n⟩$, we say that an ordered sequence $𝒞$ of elements in $[n]\times [n]$ is a coupling of $P$ and $Q$, if it starts in $(1,1)$, ends in $(n,n)$ and for any consecutive tuples $(i,j),(i^{\prime },j^{\prime })$ in $𝒞$ it holds that $(i^{\prime },j^{\prime })\in \{(i+1,j),(i,j+1),(i+1,j+1)\}$. We define the discrete Fréchet distance between $P$ and $Q$ as follows

For brevity, we simply call this the Fréchet distance between $P$ and $Q$. The free space matrix of $P$ and $Q$ with distance value $\delta$ is an $n\times n$ matrix $M_{\delta }$, where the $i$-th column corresponds to the vertex $p_i$ of $P$ and the $j$-th row corresponds to the vertex $q_j$ of $Q$.

The entry $M_{\delta }[i,j]$ has the value $0$ if $d(p_i,q_j)\le \delta$ and $1$ otherwise.¹¹1Note we use $0$ and $1$ in switched roles compared to the conventions in the literature on the free space matrix. Our notation makes the cost-function of the path more intuitive. A coupling path $𝒞$ is the path through the $[n]\times [n]$ integer lattice defined by the coupling $𝒞$. We define the cost of such a path as $c(𝒞)={\sum }_{(i,j)\in 𝒞}{M}_{\delta }[i,j]$. Note that the Fréchet distance between $P$ and $Q$ is at most $\delta$ if and only if there exists a coupling path with cost $0$ from $(1,1)$ to $(n,n)$.

Our analysis is based on a property of the free space matrix. We first define this property and then link the property to a certain class of well-behaved input curves.

See Figure 1 for a visualization. A consequence of this property is that zero-entries within one row or within one column cannot be too far away from each other.

In the following, we argue why we think the $t$-locality assumption is reasonable. Note that $t$ will not exceed $n$ on any input. There are classes of well-behaved curves that satisfy the locality assumption for some $t\ll n$. Lemma 3 below shows that the free space matrix of approximate shortest paths is $t$-local. For simplicity, we impose the assumption that the lengths of the edges are bounded by a fixed multiple of $\delta$, the query radius of the Fréchet distance. In the full version, we show that our approach can be adapted to work as well if the lengths of the edges are bounded by a constant multiple of any fixed value.

The problem we study in this paper is the following. Assume we want to determine for two curves $P$ and $Q$, each consisting of $n$ vertices,²²2For ease of notation, our analysis assumes the input curves have the same number of vertices. if their Fréchet distance is at most a given value of $\delta$. We do not have direct access to the input curves. Instead, we have access to an oracle that returns the information in a given row or column of the $\delta$-free space matrix in the form of a sorted list of indices of zero-entries. We call this a query and we want to determine $D_{ℱ}(P,Q)\le \delta$ using as few (sublinear in $n$) queries as possible. Note that from the point of view of a data structure setting, our query corresponds to a classical ball range query with a vertex $p$ of one curve and returns the list of vertex indices of the other curve that are contained in the ball of radius $\delta$ centered at $p$.

Our bounds on the number of queries will be probabilistic and will hold under a certain error model that allows for the coupling path to pass through a bounded number of one-entries. These are entries where the corresponding points are far from each other. In the full version, we discuss alternative error models and how they relate to our chosen error model.

In this section, we describe and analyze a Fréchet tester under the assumption that the free space matrix is $t$-local for a given value of $t$.

Our main goal in this section is to obtain a Fréchet-tester that does not require an additional input (the value of $t$). Our approach for this is to first run a “tester” to find an estimate for $t$ and then run Algorithm 1 with that parameter. Unfortunately, this combination is more complicated than just running two testers, for a number of different reasons: First, Algorithm 1 assumes that the matrix is $t$-local whereas the best we can do is to show that with some probability close to 1, it is “close” to being $t$-local. This change breaks the proof of correctness of Algorithm 1. The second complication is that we cannot plug in any tester for locality, we need a specific one for our analysis that also guarantees some additional properties. Guaranteeing these properties requires more queries than just testing for locality.

This section describes how the Fréchet-testers for the discrete Fréchet distance can be used to serve as $(1+{\epsilon }^{\prime })$-approximate Fréchet-testers for the continuous Fréchet distance. First, we define $(\epsilon ,\delta )$-far for the continuous Fréchet-distance. Then, we explain how to use our Fréchet-testers on instances of the continuous Fréchet distance with this error model.

We first define the continuous Fréchet distance. We set $F_n$ to be the set of all continuous non-decreasing functions $f:[0,1]\to [1,n]$ with $f(0)=1$ and $f(1)=n$. Let $P$ and $Q$ be polygonal curves with $n$ and $m$ vertices. The continuous Fréchet distance is defined to be

Now we want to introduce a possible error model for the continuous Fréchet distance. Given a value $\delta >0$ and $f\in F_n$, $g\in F_m$, we define

as the partial difference, namely the total length of the portions of the two curves $P$ and $Q$ that are not matched with distance at most $\delta$ by $f$ and $g$. Building on this, we define the partial Fréchet difference to be

This is essentially the same as the partial Fréchet distance as defined in [6].³³3Note that, in line with their definition, we assume the reparameterizations to be (piecewise) differentiable.

In order to use the first Fréchet-tester introduced in this paper, we transform the polygonal curves into discrete curves by subsampling vertices along the edges of the curves. Denote by $P_a$ the discrete curve that arises from $P$ if we subsample vertices along the edges of $P$ such that $P$ visits a curve segment of length $a$ in between any two vertices for some $a\in (0,\mathrm{\ell }(P)]$. The last edge might be longer than $a$ but shorter than $2a$. Hence, $P_a$ has $\lfloor \frac{\mathrm{\ell }(P)}{a}\rfloor$ edges. This yields that . If $P$ is $t$-straight, so is $P_a$ for any $a\in (0,\mathrm{\ell }(P)]$. The next lemma shows that the notions of $(\epsilon ,\delta )$-far are also related.

For a proof see the full version. We adjust our query oracle such that it can access the free space matrix of $P_a$ and $Q_a$. So we can apply the Fréchet-testers to $P_a$ and $Q_a$ for an adequate choice of $a$. We show that for given ${\epsilon }^{\prime }>0$ and , we can choose $a$ such that this yields a $(1+{\epsilon }^{\prime })$-approximate Fréchet-tester for the continuous Fréchet distance of $P$ and $Q$. Let ${\epsilon }^{\prime \prime }>0$. For $a={\epsilon }^{\prime \prime }\delta$, we test $P_{{\epsilon }^{\prime \prime }\delta }$ and $Q_{{\epsilon }^{\prime \prime }\delta }$ for the distance ${\delta }^{\prime }≔(1+2{\epsilon }^{\prime \prime })\delta$. We observe that $M_{{\delta }^{\prime }}$ is $𝒪(\frac{t}{{\epsilon }^{\prime \prime }})$-local if $P$ and $Q$ are $t$-straight. If ${\delta }_{ℱ}(P,Q)\le \delta$, we have $D_{ℱ}(P_{{\epsilon }^{\prime \prime }\delta },Q_{{\epsilon }^{\prime \prime }\delta })\le {\delta }^{\prime }$ and if $P$ and $Q$ are $(\epsilon ,\mu \delta )$-far, we have that $P_{{\epsilon }^{\prime \prime }\delta }$ and $Q_{{\epsilon }^{\prime \prime }\delta }$ are $(\frac{\epsilon }{12},{\delta }^{\prime })$-far for $\mu =1+4{\epsilon }^{\prime \prime }=1+{\epsilon }^{\prime }$ for ${\epsilon }^{\prime \prime }={\epsilon }^{\prime }/4$. So, if we know $t$, we can apply the first Fréchet-tester for $\frac{\epsilon }{12}$ and ${\delta }^{\prime }$. If $t$ is unknown, we apply the second Fréchet-tester for the same values.

A natural consequence of the above theorem is that for $t$-straight curves, the number of queries is bounded in terms of $n$ and the aspect ratio of the input.