Title
Algorithms for hotspot computation on trajectory data
Abstract
We study one of the basic tasks in moving object analysis, namely the location of hotspots. A hotspot is a (small) region in which an entity spends a significant amount of time. Finding such regions is useful in many applications, for example in segmentation, clustering, and locating popular places. We may be interested in locating a minimum size hotspot in which the entity spends a fixed amount of time, or locating a fixed size hotspot maximizing the time that the entity spends inside it. Furthermore, we can consider the total time, or the longest contiguous time the entity spends in the hotspot. We solve all four versions of the problem. For a square hotspot, we can solve the contiguous-time versions in O(nlogn) time, where n is the number of trajectory vertices. The algorithms for the total-time versions are roughly quadratic. Finding a hotspot containing relatively the most time, compared to its size, takes O(n3) time. Even though we focus on a single moving entity, our algorithms immediately extend to multiple entities. Finally, we consider hotspots of different shape.
Year
DOI
Venue
2013
10.1145/2525314.2525359
SIGSPATIAL/GIS
Keywords
Field
DocType
hotspot computation,contiguous-time version,square hotspot,fixed amount,significant amount,longest contiguous time,multiple entity,trajectory data,basic task,minimum size hotspot,total time,fixed size hotspot,hotspot,trajectory
Data mining,Vertex (geometry),Hotspot (geology),Computer science,Segmentation,Quadratic equation,Algorithm,Theoretical computer science,Cluster analysis,Hotspot (Wi-Fi),Trajectory,Computation
Conference
Citations 
PageRank 
References 
6
0.51
23
Authors
3
Name
Order
Citations
PageRank
Joachim Gudmundsson11362100.81
Marc J. van Kreveld21702166.91
Frank Staals32911.40