Publikation:

On the generalized fréchet distance and its applications

Lade...
Vorschaubild

Dateien

Zu diesem Dokument gibt es keine Dateien.

Datum

2022

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

URI (zitierfähiger Link)
ArXiv-ID

Internationale Patentnummer

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published

Erschienen in

RENZ, Matthias, ed., Mohamed SARWAT, ed.. SIGSPATIAL '22 : Proceedings of the 30th International Conference on Advances in Geographic Information Systems. New York, NY: ACM, 2022, 35. ISBN 978-1-4503-9529-8. Available under: doi: 10.1145/3557915.3560970

Zusammenfassung

Measuring the similarity of spatio-temporal trajectories in a sensible fashion is an important building block for applications such as trajectory clustering or movement pattern analysis. However, typically employed similarity measures only take the spatial components of the trajectory into account, or are complicated combinations of different measures. In this paper we introduce the so called Generalized Fréchet distance, which extends the well-known Fréchet distance. For two polygonal curves of length n and m in d-dimensional space, the Generalized Fréchet distance enables an individual weighting of each dimension on the similarity value by using a convex function. This allows to integrate arbitrary data dimensions as e.g. temporal information in an elegant, flexible and application-aware manner. We study the Generalized Fréchet Distance for both the discrete and the continuous version of the problem, prove useful properties, and present efficient algorithms to compute the decision and optimization problem. In particular, we prove that for d ∈ O(1) the asymptotic running times of the optimization problem for the continuous version are O(nm log(nm)) under realistic assumptions, and O(nm) for the discrete version for arbitrary weight functions. Therefore the theoretical running times match those of the classical Fréchet distance. In our experimental evaluation, we demonstrate the usefulness of the Generalized Fréchet distance and study the practical behaviour of our algorithms. On sets of real-world trajectories, we confirm that the weighting of the spatial and temporal dimensions heavily impacts the relative similarity, and hence the ability to tailor the measure to the application is a useful tool.

Zusammenfassung in einer weiteren Sprache

Fachgebiet (DDC)
004 Informatik

Schlagwörter

Trajectory similarity, Fréchet distance, Algorithm analysis

Konferenz

SIGSPATIAL '22 : The 30th International Conference on Advances in Geographic Information Systems, 1. Nov. 2022 - 4. Nov. 2022, Seattle, Washington
Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690GUTSCHLAG, Theodor, Sabine STORANDT, 2022. On the generalized fréchet distance and its applications. SIGSPATIAL '22 : The 30th International Conference on Advances in Geographic Information Systems. Seattle, Washington, 1. Nov. 2022 - 4. Nov. 2022. In: RENZ, Matthias, ed., Mohamed SARWAT, ed.. SIGSPATIAL '22 : Proceedings of the 30th International Conference on Advances in Geographic Information Systems. New York, NY: ACM, 2022, 35. ISBN 978-1-4503-9529-8. Available under: doi: 10.1145/3557915.3560970
BibTex
@inproceedings{Gutschlag2022gener-66286,
  year={2022},
  doi={10.1145/3557915.3560970},
  title={On the generalized fréchet distance and its applications},
  isbn={978-1-4503-9529-8},
  publisher={ACM},
  address={New York, NY},
  booktitle={SIGSPATIAL '22 : Proceedings of the 30th International Conference on Advances in Geographic Information Systems},
  editor={Renz, Matthias and Sarwat, Mohamed},
  author={Gutschlag, Theodor and Storandt, Sabine},
  note={Funded by the Deutsche Forschungsgemeinschaft (DFG, German
Research Foundation) - Project-ID 251654672 - TRR 161. Article Number: 35}
}
RDF
<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/66286">
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2023-03-03T12:30:21Z</dc:date>
    <dc:creator>Gutschlag, Theodor</dc:creator>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dc:contributor>Storandt, Sabine</dc:contributor>
    <dc:contributor>Gutschlag, Theodor</dc:contributor>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/66286"/>
    <dcterms:title>On the generalized fréchet distance and its applications</dcterms:title>
    <dc:language>eng</dc:language>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:issued>2022</dcterms:issued>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2023-03-03T12:30:21Z</dcterms:available>
    <dc:creator>Storandt, Sabine</dc:creator>
    <dcterms:abstract xml:lang="eng">Measuring the similarity of spatio-temporal trajectories in a sensible fashion is an important building block for applications such as trajectory clustering or movement pattern analysis. However, typically employed similarity measures only take the spatial components of the trajectory into account, or are complicated combinations of different measures. In this paper we introduce the so called Generalized Fréchet distance, which extends the well-known Fréchet distance. For two polygonal curves of length n and m in d-dimensional space, the Generalized Fréchet distance enables an individual weighting of each dimension on the similarity value by using a convex function. This allows to integrate arbitrary data dimensions as e.g. temporal information in an elegant, flexible and application-aware manner. We study the Generalized Fréchet Distance for both the discrete and the continuous version of the problem, prove useful properties, and present efficient algorithms to compute the decision and optimization problem. In particular, we prove that for d ∈ O(1) the asymptotic running times of the optimization problem for the continuous version are O(nm log(nm)) under realistic assumptions, and O(nm) for the discrete version for arbitrary weight functions. Therefore the theoretical running times match those of the classical Fréchet distance. In our experimental evaluation, we demonstrate the usefulness of the Generalized Fréchet distance and study the practical behaviour of our algorithms. On sets of real-world trajectories, we confirm that the weighting of the spatial and temporal dimensions heavily impacts the relative similarity, and hence the ability to tailor the measure to the application is a useful tool.</dcterms:abstract>
    <dc:rights>terms-of-use</dc:rights>
  </rdf:Description>
</rdf:RDF>

Interner Vermerk

xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter

Kontakt
URL der Originalveröffentl.

Prüfdatum der URL

Prüfungsdatum der Dissertation

Finanzierungsart

Kommentar zur Publikation

Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - Project-ID 251654672 - TRR 161.
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Diese Publikation teilen