论文标题
在Fréchet距离下实际输入图上的地图匹配查询
Map matching queries on realistic input graphs under the Fréchet distance
论文作者
论文摘要
地图匹配是分析车辆轨迹的常见预处理步骤。在理论社区中，最流行的地图匹配方法是计算道路网络上的路径，该路径在空间上与轨迹最相似，在空间上，使用Fréchet距离测量了空间相似性。在Fréchet距离下，现有地图匹配算法的缺点是，每次匹配轨迹时，整个道路网络都需要从头开始重新处理。一个开放的问题是，是否可以将道路网络预处理到数据结构中，以便可以在跨线性时间内回答地图匹配查询。 在本文中，我们调查了在Fréchet距离下的地图匹配查询。我们为几何平面图提供了负面结果。我们表明，除非塞思失败，否则在多项式时间内没有可以构造的数据结构，可以在$ o（（PQ）^{1-δ}）中匹配查询的地图匹配查询（（pq）^{1-δ}）$查询时间的任何$δ> 0 $，其中$ p $和$ q $是$ p $和$ q $，是几何图形图和查询图形的复杂性，以及查询图形的复杂性。我们为现实的输入图提供了积极的结果，我们认为这是本文的主要结果。 We show that for $c$-packed graphs, one can construct a data structure of $\tilde O(cp)$ size that can answer $(1+\varepsilon)$-approximate map matching queries in $\tilde O(c^4 q \log^4 p)$ time, where $\tilde O(\cdot)$ hides lower-order factors and dependence on $\varepsilon$.
Map matching is a common preprocessing step for analysing vehicle trajectories. In the theory community, the most popular approach for map matching is to compute a path on the road network that is the most spatially similar to the trajectory, where spatial similarity is measured using the Fréchet distance. A shortcoming of existing map matching algorithms under the Fréchet distance is that every time a trajectory is matched, the entire road network needs to be reprocessed from scratch. An open problem is whether one can preprocess the road network into a data structure, so that map matching queries can be answered in sublinear time. In this paper, we investigate map matching queries under the Fréchet distance. We provide a negative result for geometric planar graphs. We show that, unless SETH fails, there is no data structure that can be constructed in polynomial time that answers map matching queries in $O((pq)^{1-δ})$ query time for any $δ> 0$, where $p$ and $q$ are the complexities of the geometric planar graph and the query trajectory, respectively. We provide a positive result for realistic input graphs, which we regard as the main result of this paper. We show that for $c$-packed graphs, one can construct a data structure of $\tilde O(cp)$ size that can answer $(1+\varepsilon)$-approximate map matching queries in $\tilde O(c^4 q \log^4 p)$ time, where $\tilde O(\cdot)$ hides lower-order factors and dependence on $\varepsilon$.
