Reporting Flock Patterns

Detecting flocks by range queries in higher-dim. space

A study in Alaska gave the motivation for this work: caribous had been endowed with GPS collars in order to trace their positions over a longer period of time. The aim was to detect and report flocks that the single caribous form and to analyze the social behavior of the animals.

Our idea for the algorithmic realization of the analysis is to map the trace of each entity (defined by the position on t consecutive time steps) to a point in 2t-dimensional space. After this has been done for all entities we perform range (counting/reporting) queries which are able to recognize the existence of a flock and to report all flock members. A flock is defined by three predetermined parameters: the minimum number of animals that have to be involved, the restriction on the size of the area in which all flock animals have to be and the minimum amount have time that they have to be together. An example is depicted in the following figure.

The objects p,q and r form a flock over a period of 3 time steps.

The innovation of our work is based in the simultaneous analysis of t time steps. Earlier algorithms have exclusively been looking at each time step independently. Then, via the current location of the animals and an interpolation of the moving directions, it was tried to make claims on flocks existing for a longer period of time.

Joint work with Joachim Gudmundsson, Florian Hübner and Thomas Wolle.

Publications

  1. Marc Benkert, Joachim Gudmundsson, Florian Hübner, and Thomas Wolle. Reporting flock patterns. In Yossi Azar and Thomas Erlebach, editors, Proc. 14th Annu. Europ. Symp. on Algorithms (ESA'06), volume 4168 of Lecture Notes in Computer Science, pages 660-671. Springer-Verlag, 2006. [ bib | pdf ]
  2. Marc Benkert, Joachim Gudmundsson, Florian Hübner, and Thomas Wolle. Reporting flock patterns. Technical Report 2006-14, Fakultät für Informatik, Universität Karlsruhe, 2006. Available at http://www.ubka.uni-karlsruhe.de/cgi-bin/psview?document=/ira/2006/14. [ bib | html ]