Straight-path queries in trajectory data

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

1 Citaat (Scopus)
3 Downloads (Pure)


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, and present efficient construction algorithms for our data structures, and analyze their performance. We also present an O(n^{1.5¿+¿e}) algorithm that, given a trajectory P and a threshold t, finds a simplification of P with a minimum number of vertices such that each edge in the simplification replaces a sub-trajectory of length at most t times the length of the edge. This significantly improves the fastest known algorithm for the problem.
Originele taal-2Engels
TitelWALCOM: Algorithms and Computation (9th International Workshop, WALCOM 2015, Dhaka, Bangladesh, February 26-28, 2015. Proceedings)
RedacteurenM.S. Rahman, E. Tomita
Plaats van productieCham
ISBN van geprinte versie978-3-319-15611-8
StatusGepubliceerd - 2015
Evenement9th International Workshop on Algorithms and Computation (WALCOM 2015) - Dhaka, Bangladesh
Duur: 26 feb 201528 feb 2015
Congresnummer: 9

Publicatie series

NaamLecture Notes in Computer Science
ISSN van geprinte versie0302-9743


Workshop9th International Workshop on Algorithms and Computation (WALCOM 2015)
Verkorte titelWALCOM 2015
Ander9th International Workshop on Algorithms and Computation

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

Citeer dit