Reporting flock patterns
Computational GeometryPublished 4 December 2007
Marc Benkert, Joachim Gudmundsson, Florian Hübner, Thomas Wolle
Citations190
SJR quartileQ3
SJR score0.40
SNIP0.77
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A new definition of a flock is given that is argued to be more realistic than the previous ones, and fast approximation algorithms to report flocks are presented.
Abstract
Data representing moving objects is rapidly getting more available, especially in the area of wildlife GPS tracking. It is a central belief that information is hidden in large data sets in the form of interesting patterns, where a pattern can be any configuration of some moving objects in a certain area and/or during a certain time period. One of the most common spatio-temporal patterns sought after is flocks. A flock is a large enough subset of objects moving along paths close to each other for a certain pre-defined time. We give a new definition that we argue is more realistic than the previous ones, and by the use of techniques from computational geometry we present fast algorithms to detect and report flocks. The algorithms are analysed both theoretically and experimentally.
Keywords
Computer Science
Lecture notes in computer scienceOn Discovering Moving Clusters in Spatio-temporal Data
421 Citations2005Panos Kalnis, Nikos Mamoulis +1 more
This work provides a formal definition for moving clusters and describes three algorithms for their automatic discovery, a straight-forward method based on the definition, a more efficient method which avoids redundant checks and an approximate algorithm which trades accuracy for speed by borrowing ideas from the MPEG-2 video encoding.
Computing longest duration flocks in trajectory data
276 Citations2006Joachim Gudmundsson, Marc van Kreveld
This work considers the computational efficiency of computing two of the most basic spatio-temporal patterns in trajectories, namely flocks and meetings, and gives several exact and approximation algorithms.
Finding REMO — Detecting Relative Motion Patterns in Geospatial Lifelines
191 Citations2005Patrick Laube, Marc van Kreveld +1 more
A geographic data mining approach to detect generic aggregation patterns such as flocking behaviour and convergence in geospatial lifeline data and discusses the geometric properties of the formalised patterns with respect to their efficient computation.
Lecture notes in computer scienceAnalyzing Relative Motion within Groups ofTrackable Moving Point Objects
148 Citations2002Patrick Laube, Stephan Imfeld
The overall goal of the ongoing project is to develop methods for spatio-temporal analysis of relative motion within groups of moving point objects, such as GPS-tracked animals, using the analysis concept called REMO (RElative MOtion).
Efficient detection of motion patterns in spatio-temporal data sets
141 Citations2004Joachim Gudmundsson, Marc van Kreveld +1 more
By the use of techniques from computational geometry, including approximation algorithms, this work improves the running time bounds of existing algorithms to detect spatio-temporal patterns of moving point objects, namely flock, leadership, convergence, and encounter.
Computational GeometryApproximate range searching☆☆A preliminary version of this paper appeared in the Proc. of the 11th Annual ACM Symp. on Computational Geometry, 1995, pp. 172–181.
131 Citations2000Sunil Arya, David M. Mount
GeoInformaticaEfficient Detection of Patterns in 2D Trajectories of Moving Points
120 Citations2007Joachim Gudmundsson, Marc van Kreveld +1 more
This work improves the running time bounds of existing algorithms to detect spatio-temporal patterns, namely flock, leadership, convergence, and encounter, that exhibit similar movement in the sense of direction, heading for the same location, and/or proximity.
Lecture notes in computer scienceMining Spatio-temporal Association Rules, Sources, Sinks, Stationary Regions and Thoroughfares in Object Mobility Databases
98 Citations2006Florian Verhein, Sanjay Chawla
This work provides a comprehensive definition of spatio-temporal association rules (STARs) that describe how objects move between regions over time and introduces other patterns that are useful for mobility data; stationary regions and high traffic regions.
Life and Motion of Socio-Economic Units
93 Citations2000Andrew U. Frank, Jonathan Raper +1 more
This chapter discusses the development ofabases for Temporal GIS: Applications in the context ofSocio-economic Units and its applications in the 21st Century.
Image and Vision ComputingLearning spatio-temporal patterns for predicting object behaviour
93 Citations2000Neil Sumpter, Andrew J. Bulpitt
A novel approach to learning long-term spatio-temporal patterns of objects in image sequences, using a neural network paradigm to predict future behaviour in response to a predator is presented.
The skip quadtree
90 Citations2005David Eppstein, Michael T. Goodrich +1 more
This work presents a new multi-dimensional data structure, which it is called the skip quadtree or the skip octree, which has the well-defined "box"-shaped regions of region quadtrees and the logarithmic-height search and update hierarchical structure of skip lists.
International Journal of Computational Geometry & ApplicationsPARALLEL CONSTRUCTION OF QUADTREES AND QUALITY TRIANGULATIONS
76 Citations1999Marshall Bern, David Eppstein +1 more
Computational GeometryOn fat partitioning, fat covering and the union size of polygons
69 Citations1998Marc van Kreveld
A necessary and sufficient condition is given for simple polygons which guarantees smaller union complexity, based on a new method to partition a simple polygon P with n vertices into O(n) convex quadrilaterals, without introducing angles smaller than π/12 radians or narrow corridors.
Computational GeometryComputing depth orders for fat objects and related problems
51 Citations1995Pankaj K. Agarwal, Matthew J. Katz +1 more
A new technique for computing depth orders is presented, and it is shown that if K is a set of n triangles whose xy-projections are all ‘fat’, then a depth order for K can be computed in time O(n log5n).
Symposium on Discrete AlgorithmsOn approximating the depth and related problems
46 Citations2005Boris Aronov, Sariel Har-Peled
Motion planning amidst fat obstacles (extended abstract)
45 Citations1994A. Frank van der Stappen, Mark H. Overmars
The paradigm fits in the cell decomposition approach to motion planning and exploits workspace properties that follow from the fatness of the obstacles and leads to nearly optimal algorithms for motion planning in 2D and 3D amidst obstacles of comparable size.
Lecture notes in computer scienceReporting Flock Patterns
42 Citations2006Marc Benkert, Joachim Gudmundsson +2 more
Dimensionality reduction for long duration and complex spatio-temporal queries
42 Citations2007Ghazi Al‐Naymat, Sanjay Chawla +1 more
This paper proposes a preprocessing strategy which consists of using a random projection to reduce the dimensionality of the transformed space and shows the possibility of breaking the curse of dimensionality in a spatio-temporal setting.
AlcesREAL-TIME MOOSE TRACKING: AN INTERNET BASED MAPPING APPLICATION USING GPS/GSM-COLLARS IN SWEDEN
31 Citations2004Holger Dettki, Göran Ericsson +1 more
A technique that automatically tracks and reports moose in almost real time, and presents moose positions and movement paths with an interactive web-based map service is presented.
Tracking Soccer Player Using Multiple Views
25 Citations2002Sachiko Iwase, Hideo Saitô
Experimental results show that robust player tracking is available by taking advantage of using multiple cameras.
Lecture notes in computer scienceMotion Mining
11 Citations2001Stan Sclaroff, George Kollios +2 more
A preliminary system for estimating human motion in video, as well as indexing and data mining of the resulting motion databases, and algorithms that automatically extract motion trajectories and time series data from video are described.
Lecture notes in computer scienceA New Similar Trajectory Retrieval Scheme Using k-Warping Distance Algorithm for Moving Objects
9 Citations2003Choon-Bo Shim, Jae‐Woo Chang
A k-warping distance algorithm is proposed which enhances the existing time warping distance algorithm by permitting up to k replications for an arbitrary motion of a query trajectory so that the authors measure the similarity between two trajectories accurately.