论文标题
$（2+ε）$ - fréchet距离下的时间序列
$(2+ε)$-ANN for time series under the Fréchet distance
论文作者
论文摘要
我们研究了连续的fréchet距离下时间序列的近似邻近数据结构。对于可实现的近似因子$ c> 1 $和查询半径$ r $，可以使用近似near的数据结构来预算在$ \ mathbb {r} $（aka time序列）中以$ \ mathbb {r} $ comploventity $ m $的回答$ k $ k $ k cr cr cr cr cruder，或者在complactity complace clude中回答cruder，或者在complove clude c $ cr cre cre cre cluder clive contrue或距离$ r $内的输入中没有曲线。在这两种情况下，答案都是正确的。我们的第一个数据结构达到了$（5 +ε）$近似因子，在$ n \ cdot \ mathcal {o} \ left（{{ε^{ - 1}}} \ right）^{k} + \ Mathcal {o}（o}（nm）$中，并有$ \ mathcal $ \ k的$ k {我们的第二个数据结构达到了$（2 +ε）$近似因子，在$ n \ cdot \ mathcal {o} \ left（\ frac {m} {m} {kε} \ right）^{k} + \ m natercal {o}（nm）$中，并有$ \ mathcal c. 2^k \ right）$。我们的第三个积极结果是基于局部敏感哈希的概率数据结构，该数据结构在$ \ Mathcal {o}（n \ log n+n+nm）$中获得空间，并在$ \ Mathcal {o}（k \ log log n）中获得查询时间，并以$ \ nathcal calcal calcal calcal calcal calcal calcal calcal calcal {o}（k）$}（k）$}（k）（k）（k）（k）（k）。我们所有的数据结构都利用了签名概念，这些概念最初是针对Fréchet距离下聚类时间序列的问题引入的。此外，我们显示了此问题的下限。考虑任何达到近似因子小于$ 2 $的数据结构，并支持高达$ l $的弧形曲线，并仅使用恒定数量的探针来回答查询。我们表明，在对单词大小的合理假设下，任何此类数据结构都需要$ l^{ω（k）} $中的空间。
We study approximate-near-neighbor data structures for time series under the continuous Fréchet distance. For an attainable approximation factor $c>1$ and a query radius $r$, an approximate-near-neighbor data structure can be used to preprocess $n$ curves in $\mathbb{R}$ (aka time series), each of complexity $m$, to answer queries with a curve of complexity $k$ by either returning a curve that lies within Fréchet distance $cr$, or answering that there exists no curve in the input within distance $r$. In both cases, the answer is correct. Our first data structure achieves a $(5+ε)$ approximation factor, uses space in $n\cdot \mathcal{O}\left({ε^{-1}}\right)^{k} + \mathcal{O}(nm)$ and has query time in $\mathcal{O}\left(k\right)$. Our second data structure achieves a $(2+ε)$ approximation factor, uses space in $n\cdot \mathcal{O}\left(\frac{m}{kε}\right)^{k} + \mathcal{O}(nm)$ and has query time in $\mathcal{O}\left(k\cdot 2^k\right)$. Our third positive result is a probabilistic data structure based on locality-sensitive hashing, which achieves space in $\mathcal{O}(n\log n+nm)$ and query time in $\mathcal{O}(k\log n)$, and which answers queries with an approximation factor in $\mathcal{O}(k)$. 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échet 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^{Ω(k)}$.
