DROPS

Document

DOI: 10.4230/LIPIcs.SEA.2020.24

Finding Structurally and Temporally Similar Trajectories in Graphs

Authors: Roberto Grossi, Andrea Marino, and Shima Moghtasedi

Published in: LIPIcs, Volume 160, 18th International Symposium on Experimental Algorithms (SEA 2020)

Abstract

The analysis of similar motions in a network provides useful information for different applications like route recommendation. We are interested in algorithms to efficiently retrieve trajectories that are similar to a given query trajectory. For this task many studies have focused on extracting the geometrical information of trajectories. In this paper we investigate the properties of trajectories moving along the paths of a network. We provide a similarity function by making use of both the temporal aspect of trajectories and the structure of the underlying network. We propose an approximation technique that offers the top-k similar trajectories with respect to a query trajectory in an efficient way with acceptable precision. We investigate our method over real-world networks, and our experimental results show the effectiveness of the proposed method.

Cite as

Roberto Grossi, Andrea Marino, and Shima Moghtasedi. Finding Structurally and Temporally Similar Trajectories in Graphs. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 24:1-24:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{grossi_et_al:LIPIcs.SEA.2020.24,
  author =	{Grossi, Roberto and Marino, Andrea and Moghtasedi, Shima},
  title =	{{Finding Structurally and Temporally Similar Trajectories in Graphs}},
  booktitle =	{18th International Symposium on Experimental Algorithms (SEA 2020)},
  pages =	{24:1--24:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-148-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{160},
  editor =	{Faro, Simone and Cantone, Domenico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2020.24},
  URN =		{urn:nbn:de:0030-drops-120989},
  doi =		{10.4230/LIPIcs.SEA.2020.24},
  annote =	{Keywords: Graph trajectory, approximated similarity, top-k similarity query}
}

Search Results

Documents authored by Moghtasedi, Shima

Finding Structurally and Temporally Similar Trajectories in Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message