##
**Reporting flock patterns.**
*(English)*
Zbl 1163.65011

The authors discuss algorithms to detect flocks in moving objects. They start with a set of \(n\) identities in the plane and the position of the entities at time steps \(t_1,\dots, t_\tau\). It is supposed that these time steps are taken synchronously for all the identities and that the movement between the steps is linear at constant speed.

Given integers \(m, k\) and \(r>0\), a flock is a set of \(m\) entities such that during a \(k\)-length time, all of the entities belong to a (moving) ball of radious \(r\). The main problem is then how to detect all possible flocks from the data.

The main idea of the article is, for each entity \(p\) and a \(k\)-length interval \([t_i,t_j]\), \(j-i+1\geq k\), let \((x_l,y_l)\) the possition of \(p\) at discrete time \(t_l\). Then consider the vector \((x_i,y_i,x_{i+1},y_{i+1},\dots,x_j,y_j)\) in a higher dimensional space. A flock is then a set of \(m\) entities whose corresponding vectors that are close in this higher space.

In order to work with these objects, one has to be careful on how to describe the spatial objects, since the complexity increases exponentially in \(k\). The authors use a specific data structure called skip-quadtree. Some queries over these trees and operations can be done in constant time \(n\) for the model of computation assumed in the article. A set of different algorithms to compute flocks within this specific model is provided. These algorithms are approximate, they will correctly report all the flocks but there may be some detected fake-flocks, that are flocks for a radius \(\Delta r\), where \(\Delta\) may be \(\sqrt{8}+\varepsilon\) (the box method), \(2+\varepsilon\) (the pipe method) and \((1+\varepsilon)\) (ample-points method). After describing the algorithms and giving theoretical complexity, a brief discussion on related problems follows. Finally, there is a section of experiments where it is shown how the algorithms behave in practice under a number of different situations and some explanations and hypothesis of why the algorithms behave as they do.

Given integers \(m, k\) and \(r>0\), a flock is a set of \(m\) entities such that during a \(k\)-length time, all of the entities belong to a (moving) ball of radious \(r\). The main problem is then how to detect all possible flocks from the data.

The main idea of the article is, for each entity \(p\) and a \(k\)-length interval \([t_i,t_j]\), \(j-i+1\geq k\), let \((x_l,y_l)\) the possition of \(p\) at discrete time \(t_l\). Then consider the vector \((x_i,y_i,x_{i+1},y_{i+1},\dots,x_j,y_j)\) in a higher dimensional space. A flock is then a set of \(m\) entities whose corresponding vectors that are close in this higher space.

In order to work with these objects, one has to be careful on how to describe the spatial objects, since the complexity increases exponentially in \(k\). The authors use a specific data structure called skip-quadtree. Some queries over these trees and operations can be done in constant time \(n\) for the model of computation assumed in the article. A set of different algorithms to compute flocks within this specific model is provided. These algorithms are approximate, they will correctly report all the flocks but there may be some detected fake-flocks, that are flocks for a radius \(\Delta r\), where \(\Delta\) may be \(\sqrt{8}+\varepsilon\) (the box method), \(2+\varepsilon\) (the pipe method) and \((1+\varepsilon)\) (ample-points method). After describing the algorithms and giving theoretical complexity, a brief discussion on related problems follows. Finally, there is a section of experiments where it is shown how the algorithms behave in practice under a number of different situations and some explanations and hypothesis of why the algorithms behave as they do.

Reviewer: Luis Felipe Tabera Alonso (Madrid)

### MSC:

65D18 | Numerical aspects of computer graphics, image analysis, and computational geometry |

51-04 | Software, source code, etc. for problems pertaining to geometry |

68T10 | Pattern recognition, speech recognition |

65Y20 | Complexity and performance of numerical algorithms |

### Keywords:

moving point objects; Trajectories; Spatio-temporal data; computational goemetry; numerical examples; complexity; algorithms; box method; pipe method; ample-points method
PDFBibTeX
XMLCite

\textit{M. Benkert} et al., Comput. Geom. 41, No. 3, 111--125 (2008; Zbl 1163.65011)

### References:

[1] | Al-Naymat, G.; Chawla, S.; Gudmundsson, J., Dimensionality reduction for long duration and complex spatio-temporal queries, (Proceedings of the 22nd ACM Symposium on Applied Computing (2007), ACM), 393-397 |

[2] | Arya, S.; Mount, D. M., Approximate range searching, Computational Geometry—Theory and Applications, 17, 3-4, 135-152 (2000) · Zbl 0968.68167 |

[3] | Balme, G.; Hunter, L., Mortality in a protected leopard population, phinda private game reserve, South Africa: A population in decline?, Ecological Journal, 6 (2004) |

[4] | Bern, M.; Eppstein, D.; Teng, S.-H., Parallel construction of quadtrees and quality triangulations, International Journal of Computational Geometry and Applications, 9, 6, 517-532 (1999) · Zbl 1074.68630 |

[5] | Dettki, H.; Ericsson, G.; Edenius, L., Real-time moose tracking: An internet based mapping application using GPS/GSM-collars in Sweden, Alces, 40, 13-21 (2004) |

[7] | (Frank, A. U.; Raper, J. F.; Cheylan, J.-P., Life and Motion of Spatial Socio-economic Units (2001), Taylor & Francis: Taylor & Francis London) |

[9] | Gudmundsson, J.; van Kreveld, M.; Speckmann, B., Efficient detection of motion patterns in spatio-temporal sets, GeoInformatica, 11, 2, 195-215 (2007) |

[10] | Heurich, M.; Löttker, P.; Stache, A.; Baierl, F.; Kiener, H., Der Luchs im Bergwaldökosystem, AFZ—Der Wald, 10, 530-531 (2007) |

[13] | Laube, P.; Imfeld, S., Analyzing relative motion within groups of trackable moving point objects, (Egenhofer, M. J.; Mark, D. M., Geographic Information Science 2002. Geographic Information Science 2002, Lecture Notes in Computer Science, vol. 2478 (2002), Springer: Springer Berlin), 132-144 · Zbl 1015.68615 |

[14] | Laube, P.; van Kreveld, M.; Imfeld, S., Finding REMO—detecting relative motion patterns in geospatial lifelines, (Fisher, P. F., Developments in Spatial Data Handling: Proceedings of the 11th International Symposium on Spatial Data Handling (2004), Springer: Springer Berlin), 201-214 |

[15] | (Metha, D. P.; Sahni, S., Handbook of Data Structures and Applications. Handbook of Data Structures and Applications, Chapman & Hall/CRC Computer and Information Science Series (2005), Chapman & Hall/CRC) · Zbl 1077.68023 |

[16] | (Miller, H. J.; Han, J., Geographic Data Mining and Knowledge Discovery (2001), Taylor & Francis: Taylor & Francis London) |

[17] | Roddick, J. F.; Hornsby, K.; Spiliopoulou, M., An updated bibliography of temporal, spatial, and spatio-temporal data mining research, (Roddick, J. F.; Hornsby, K., Temporal, Spatial and Spatio-temporal Data Mining, TSDM 2000. Temporal, Spatial and Spatio-temporal Data Mining, TSDM 2000, Lecture Notes in Artificial Intelligence, vol. 2007 (2001), Springer: Springer Berlin), 147-163 · Zbl 0981.68657 |

[18] | Shim, C.-B.; Chang, J.-W., A new similar trajectory retrieval scheme using \(k\)-warping distance algorithm for moving objects, (Proceedings of the 4th International Conference on Advances in Web-Age Information Management, (WAIM 2003). Proceedings of the 4th International Conference on Advances in Web-Age Information Management, (WAIM 2003), Lecture Notes in Computer Science, vol. 2762 (2003), Springer: Springer Berlin), 433-444 |

[19] | Sumpter, N.; Bulpitt, A. J., Learning spatio-temporal patterns for predicting object behaviour, Image Vision and Computing, 18, 9, 697-704 (2000) |

[20] | Verhein, F.; Chawla, S., Mining spatio-temporal association rules, sources, sinks, stationary regions and thoroughfares in object mobility databases, (Proceedings of the 11th International Conference on Database Systems for Advanced Applications (DASFAA). Proceedings of the 11th International Conference on Database Systems for Advanced Applications (DASFAA), Lecture Notes in Computer Science, vol. 3882 (2006), Springer: Springer Berlin), 187-201 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.