Document Open Access Logo

Clustering Moving Entities in Euclidean Space

Authors Stephane Durocher, Md Yeakub Hassan

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2020.22.pdf
  • Filesize: 0.76 MB
  • 14 pages

Document Identifiers

Author Details

Stephane Durocher
  • University of Manitoba, Winnipeg, Canada
Md Yeakub Hassan
  • University of Manitoba, Winnipeg, Canada

Funding

This research was supported in part by the Natural Sciences and Engineering Research Council of Canada.

Cite As Get BibTex

Stephane Durocher and Md Yeakub Hassan. Clustering Moving Entities in Euclidean Space. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.SWAT.2020.22

Abstract

Clustering is a fundamental problem of spatio-temporal data analysis. Given a set 𝒳 of n moving entities, each of which corresponds to a sequence of τ time-stamped points in ℝ^d, a k-clustering of 𝒳 is a partition of 𝒳 into k disjoint subsets that optimizes a given objective function. In this paper, we consider two clustering problems, k-Center and k-MM, where the goal is to minimize the maximum value of the objective function over the duration of motion for the worst-case input 𝒳. We show that both problems are NP-hard when k is an arbitrary input parameter, even when the motion is restricted to ℝ. We provide an exact algorithm for the 2-MM clustering problem in ℝ^d that runs in O(τ d n²) time. The running time can be improved to O(τ n log{n}) when the motion is restricted to ℝ. We show that the 2-Center clustering problem is NP-hard in ℝ². Our 2-MM clustering algorithm provides a 1.15-approximate solution to the 2-Center clustering problem in ℝ². Moreover, finding a (1.15-ε)-approximate solution remains NP-hard for any ε >0. For both the k-MM and k-Center clustering problems in ℝ^d, we provide a 2-approximation algorithm that runs in O(τ d n k) time.

Subject Classification

ACM Subject Classification
  • Theory of computation → Facility location and clustering
Keywords
  • trajectories
  • clustering
  • moving entities
  • k-CENTER
  • algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. P. K. Agarwal and C. M. Procopiuc. Exact and approximation algorithms for clustering. Algorithmica, 33(2):201-226, 2002. Google Scholar
  2. P. K. Agarwal and M. Sharir. Efficient algorithms for geometric optimization. ACM Computing Surveys (CSUR), 30(4):412-458, 1998. Google Scholar
  3. S. Bespamyatnikh, B. Bhattacharya, D. Kirkpatrick, and M. Segal. Lower and upper bounds for tracking mobile users. In Foundations of Information Technology in the Era of Network and Mobile Computing, pages 47-58. Springer, 2002. Google Scholar
  4. K. Buchin, M. Buchin, M. van Kreveld, B. Speckmann, and F. Staals. Trajectory grouping structure. In Proc. Workshop on Algorithms and Data Structures, volume 8037 of Lecture Notes in Computer Science, pages 219-230. Springer, 2013. Google Scholar
  5. K. Buchin, A. Driemel, J. Gudmundsson, M. Horton, I. Kostitsyna, and M. Löffler. Approximating (k,l)-center clustering for curves. In Proc. Symposium on Discrete Algorithms, pages 2922-2938. SIAM, 2019. Google Scholar
  6. A. Driemel, A. Krivošija, and C. Sohler. Clustering time series under the Fréchet distance. In Proc. Symposium on Discrete Algorithms, pages 766-785, 2016. Google Scholar
  7. S. Durocher. Geometric facility location under continuous motion. PhD thesis, University of British Columbia, 2006. Google Scholar
  8. S. Durocher and D. Kirkpatrick. The Steiner centre of a set of points: Stability, eccentricity, and applications to mobile facility location. International Journal of Computational Geometry & Applications, 16(04):345-371, 2006. Google Scholar
  9. S. Durocher and D. Kirkpatrick. Bounded-velocity approximation of mobile Euclidean 2-centres. International Journal of Computational Geometry & Applications, 18(03):161-183, 2008. Google Scholar
  10. D. Eppstein. Faster construction of planar two-centers. In Proc. Symposium on Discrete Algorithms, pages 131-138. ACM/SIAM, 1997. Google Scholar
  11. G. N. Frederickson. Parametric search and locating supply centers in trees. In Proc. Workshop on Algorithms and Data Structures, volume 519 of Lecture Notes in Computer Science, pages 299-319. Springer, 1991. Google Scholar
  12. T. F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38:293-306, 1985. Google Scholar
  13. S. Har-Peled. Clustering motion. Discrete & Computational Geometry, 31(4):545-565, 2004. Google Scholar
  14. C. S. Jensen, D. Lin, and B. C. Ooi. Continuous clustering of moving objects. IEEE Trans. Knowl. Data Eng., 19(9):1161-1174, 2007. Google Scholar
  15. J. Lee, J. Han, and K. Whang. Trajectory clustering: a partition-and-group framework. In Proc. international conference on Management of data, pages 593-604. ACM, 2007. Google Scholar
  16. Y. Li, J. Han, and J. Yang. Clustering moving objects. In Proc. international conference on Knowledge discovery and data mining, pages 617-622. ACM, 2004. Google Scholar
  17. Z. Li, B. Ding, J. Han, and R. Kays. Swarm: Mining relaxed temporal moving object clusters. Proceedings of the VLDB Endowment, 3(1-2):723-734, 2010. Google Scholar
  18. T. W. Liao. Clustering of time series data - a survey. Pattern recognition, 38(11):1857-1874, 2005. Google Scholar
  19. N. Megiddo and K. J. Supowit. On the complexity of some common geometric location problems. SIAM journal on computing, 13(1):182-196, 1984. Google Scholar
  20. T. J. Schaefer. The complexity of satisfiability problems. In Proceedings of the tenth annual ACM symposium on Theory of computing, pages 216-226, 1978. Google Scholar
  21. X. Tan and B. Jiang. Simple O(nlog²n) algorithms for the planar 2-center problem. In Proc. Computing and Combinatorics Conference, volume 10392 of Lecture Notes in Computer Science, pages 481-491. Springer, 2017. Google Scholar
  22. G. Yuan, P. Sun, J. Zhao, D. Li, and C. Wang. A review of moving object trajectory clustering algorithms. Artificial Intelligence Review, 47(1):123-144, 2017. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact