Straight-path queries in trajectory data

M.T. Berg, de, A.D. Mehrabi

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

2 Citaten (Scopus)
1 Downloads (Pure)

Samenvatting

Inspired by sports analysis, we study data structures for storing a trajectory representing the movement of a player during a game, such that the following queries can be answered: Given two positions s and t, report all sub-trajectories in which the player moved in a more or less straight line from s to t. We consider two measures of straightness, namely dilation and direction deviation , we present efficient construction algorithms for our data structures, and we analyze their performance. We also present an O(n^{1.5¿+¿e}) algorithm for the following simplification problem: given a trajectory P and a threshold t, find a simplification of P with a minimum number of vertices such that each edge in the simplification replaces a sub-trajectory whose length is at most t times the length of the edge. This significantly improves the fastest known algorithm for the problem. Keywords: Trajectory data; Data structures; Path simplification problem
Originele taal-2Engels
Pagina's (van-tot)27-38
TijdschriftJournal of Discrete Algorithms
Volume36
Nummer van het tijdschriftWalcom 2015
DOI's
StatusGepubliceerd - 2016
Evenement9th International Workshop on Algorithms and Computation (WALCOM 2015) - Dhaka, Bangladesh
Duur: 26 feb 201528 feb 2015
Congresnummer: 9

Vingerafdruk

Duik in de onderzoeksthema's van 'Straight-path queries in trajectory data'. Samen vormen ze een unieke vingerafdruk.

Citeer dit