No Access

FINDING POPULAR PLACES

Department of Computer Science, Faculty of Informatics, University Karlsruhe, ITI Wagner, Box 6980, 76128 Karlsruhe, Germany

Search for more papers by this author

BOJAN DJORDJEVIC

NICTA, Sydney, Locked Bag 9013, Alexandria NSW 1435, Australia

School of Information Technologies, University of Sydney, NSW 2006, Australia

Search for more papers by this author

JOACHIM GUDMUNDSSON

NICTA, Sydney, Locked Bag 9013, Alexandria NSW 1435, Australia

Search for more papers by this author

, and

THOMAS WOLLE

NICTA, Sydney, Locked Bag 9013, Alexandria NSW 1435, Australia

Search for more papers by this author

https://doi.org/10.1142/S0218195910003189Cited by:16 (Source: Crossref)

Abstract

Widespread availability of location aware devices (such as GPS receivers) promotes capture of detailed movement trajectories of people, animals, vehicles and other moving objects. We investigate spatio-temporal movement patterns in large tracking data sets, i.e. in large sets of polygonal paths. Specifically, we study so-called 'popular places', that is, regions that are visited by many entities.

Given a set of polygonal paths with a total of vertices, we look at the problem of computing such popular places in two different settings. For the discrete model, where only the vertices of the polygonal paths are considered, we propose an algorithm; and for the continuous model, where also the straight line segments between the vertices of a polygonal path are considered, we develop an algorithm. We also present lower bounds and hardness results.

Keywords:

Remember to check out the Most Cited Articles!
Check out these titles in image analysis!

References

Wildlife tracking projects with GPS GSM collars. 2006 , http://www.environmental-studies.de/projects/projects.html . Google Scholar
A. U. Frank, Life and Motion of Socio-economic Units, Socio-economic units: their life and motion 8, eds. A. U. Frank, J. Raper and J. P. Cheylan (Taylor & Francis, London, 2001) pp. 21–34. Crossref, Google Scholar
R. H. Güting and M. Schneider , Moving Objects Databases ( Morgan Kaufmann Publishers , 2005 ) . Google Scholar
J. Gudmundsson, P. Laube and T. Wolle, Encyclopedia of GIS, Movement Patterns in Spatio-temporal Data (Springer, 2008) pp. 726–732. Crossref, Google Scholar
P. Laube, S. Imfeld and R. Weibel, Int. J. Geograph. Inform. Sci. 19(6), 639 (2005), DOI: 10.1080/13658810500105572. Crossref, Web of Science, Google Scholar
P. Laube, M. van Kreveld and S. Imfeld, Finding REMO – detecting relative motion patterns in geospatial lifelines, Developments in Spatial Data Handling: Proceedings of the 11th Int. Symp. Spatial Data Handling, ed. P. F. Fisher (Springer, Berlin, 2004) pp. 201–214. Google Scholar
H. Cao, O. Wolfson and G. Trajcevski, The VLDB J. 15(3), 211 (2006), DOI: 10.1007/s00778-005-0163-7. Crossref, Web of Science, Google Scholar
J. Gudmundssonet al., Compressing spatio-temporal trajectories, Proc. 18th Ann. Int. Symp. Algorithms and Computation (ISAAC)4835, Lecture Notes in Computer Science (Springer-Verlag, Berlin Heidelberg, 2007) pp. 763–775. Google Scholar
S. Sǎlteniset al., Indexing the positions of continuously moving objects, Proc. ACM SIGMOD Int. Conf. Management of Data pp. 331–342. Google Scholar
M. Hadjieleftheriouet al., The VLDB J. 15(2), 143 (2006), DOI: 10.1007/s00778-004-0151-3. Crossref, Web of Science, Google Scholar
F. Verhein and S. Chawla, Mining spatio-temporal association rules, sources, sinks, stationary regions and thoroughfares in object mobility databases, Proc. 11th Int. Conf. Database Systems for Advanced Applications (DASFAA)3882, Lecture Notes in Computer Science (Springer, 2006) pp. 187–201. Google Scholar
N. Mamouliset al., Mining, indexing, and querying historical spatiotemporal data, Proc. 10th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining (ACM, 2004) pp. 236–245. Google Scholar
G. Al-Naymat, S. Chawla and J. Gudmundsson, Dimensionality reduction for long duration and complex spatio-temporal queries, Proc. 22nd ACM Symp. Applied Computing (ACM, 2007) pp. 393–397. Google Scholar
M. Anderssonet al., GeoInformatica (2007). Google Scholar
M. Benkertet al., Computational Geometry — Theory and Applications (2007). Google Scholar
J. Gudmundsson and M. van Kreveld, Computing longest duration flocks in trajectory data, Proc. 14th ACM Symp. Advances in GIS pp. 35–42. Google Scholar
J. Gudmundsson, M. van Kreveld and B. Speckmann, GeoInformatica 11(2), 195 (2007), DOI: 10.1007/s10707-006-0002-z. Crossref, Web of Science, Google Scholar
P. Gupta, R. Janardan and M. Smid, Handbook of Data Structures and Applications, Computational geometry: generalized intersection searching (Chapman & Hall/CRC, 2005) pp. 64-1–64-17. Google Scholar
M. Ben-Or, Lower bounds for algebraic computation trees, STOC '83: Proc. Fifteenth Ann. ACM Symp. Theory of Computing (ACM Press, New York, NY, USA, 1983) pp. 80–86. Google Scholar
J. Gudmundsson, T. Husfeldt and C. Levcopoulos, Inform. Process. Lett. 81(3), 137 (2002), DOI: 10.1016/S0020-0190(01)00203-4. Crossref, Web of Science, Google Scholar
H. Edelsbrunner and L. J. Guibas, J. Comput. Syst. Sci. 38, 165 (1989), DOI: 10.1016/0022-0000(89)90038-X. Crossref, Web of Science, Google Scholar
E. Rafalin, D. Souvaine and I. Streinu, Topological sweep in degenerate cases, Proc. 4th Int. Workshop on Algorithm Engineering and Experiments, ALENEX 022409, Lecture Notes in Computer Science (Springer, Berlin, 2002) pp. 155–156. Google Scholar
A. Gajentaan and M. H. Overmars , n2-hard problems in computational geometry ( Department of Coumputer Science, Utrecht University , The Netherlands , 1993 ) . Google Scholar
J. Erickson and R. Seidel, Discr. Comput. Geom. 13, 41 (1995), DOI: 10.1007/BF02574027. Crossref, Web of Science, Google Scholar
M. de Berg et al. , Computational Geometry: Algorithms and Applications , 2nd edn. ( Springer-Verlag , Berlin, Germany , 2000 ) . Crossref, Google Scholar