English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

Map matching is a common preprocessing step for analysing vehicletrajectories. In the theory community, the most popular approach for mapmatching is to compute a path on the road network that is the most spatiallysimilar to the trajectory, where spatial similarity is measured using theFr\'echet distance. A shortcoming of existing map matching algorithms under theFr\'echet distance is that every time a trajectory is matched, the entire roadnetwork needs to be reprocessed from scratch. An open problem is whether onecan preprocess the road network into a data structure, so that map matchingqueries can be answered in sublinear time.  In this paper, we investigate map matching queries under the Fr\'echetdistance. We provide a negative result for geometric planar graphs. We showthat, unless SETH fails, there is no data structure that can be constructed inpolynomial time that answers map matching queries in $O((pq)^{1-\delta})$ querytime for any $\delta > 0$, where $p$ and $q$ are the complexities of thegeometric planar graph and the query trajectory, respectively. We provide apositive result for realistic input graphs, which we regard as the main resultof this paper. We show that for $c$-packed graphs, one can construct a datastructure of $\tilde O(cp)$ size that can answer $(1+\varepsilon)$-approximatemap matching queries in $\tilde O(c^4 q \log^4 p)$ time, where $\tildeO(\cdot)$ hides lower-order factors and dependence on $\varepsilon$.

Map matching queries on realistic input graphs under the Fr\'echet distance