## Abstract

Let S be a set of n polygonal trajectories in the plane and k be a fixed constant. We present a data structure to store S so that, given a k-vertex query trajectory Q, we can answer the following queries approximately: • Nearest neighbor query: given a query trajectory Q, report the trajectory in S with minimum Fréchet distance to Q. • Top-j query: given a query trajectory Q and a positive integer j, report the j trajectories in S with minimum Fréchet distance to Q. • Range reporting query: given a query trajectory Q and a number
_{max} , report all trajectories in S with Fréchet distance at most
_{max} to Q. • Similarity query: given a query trajectory Q and a trajectory ? S, report the Fréchet distance between Q and . Our data structure answers these queries approximately, with an additive error that is at most · reach(Q) for a given fixed constant > 0, where reach(Q) is the maximum distance between the start vertex of Q and any other vertex of Q. Furthermore, our query procedures ignore trajectories whose Fréchet distance to the query Q is very large. That is, if no trajectory is close to the query trajectory then no answer might be returned. The data structure uses O(n/
^{2k} ) space and answers each of the queries above in time O(1 + #answers). Our data structure is the first one that can answer all these queries with provable error guarantees. Moreover, it is fully dynamic: inserting and deleting a trajectory with m vertices takes O(1/
^{2k} (m + log(1/))) and O(1/
^{2k} ) amortized time, respectively. Finally, we empirically evaluate our data structure.

Original language | English |
---|---|

Title of host publication | SIGSPATIAL'17 Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems |

Editors | Siva Ravada, Erik Hoel, Roberto Tamassia, Shawn Newsam, Goce Trajcevski, Goce Trajcevski |

Place of Publication | New York |

Publisher | Association for Computing Machinery, Inc |

Number of pages | 4 |

ISBN (Print) | 978-1-4503-5490-5 |

DOIs | |

Publication status | Published - 7 Nov 2017 |

Event | 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2017) - Redondo Beach, United States Duration: 7 Nov 2017 → 10 Nov 2017 Conference number: 25 http://sigspatial2017.sigspatial.org/ |

### Conference

Conference | 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2017) |
---|---|

Abbreviated title | ACM GIS 2017 |

Country/Territory | United States |

City | Redondo Beach |

Period | 7/11/17 → 10/11/17 |

Internet address |

## Keywords

- And approximate range queries.
- Approximate nearest-neighbor queries
- Data structures
- Fréchet distance
- Trajectory analysis