Clustering Moving Entities in Euclidean Space
AuthorsStephane Durocher,Md Yeakub Hassan
- Part of: Volume:17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)
Part of: Series:Leibniz International Proceedings in Informatics (LIPIcs)
Part of: Conference:Scandinavian Symposium and Workshops on Algorithm Theory (SWAT) - License:
Creative Commons Attribution 3.0 Unported license - Publication Date: 2020-06-12
File
LIPIcs.SWAT.2020.22.pdf
- Filesize: 0.76 MB
- 14 pages
Document Identifiers
Author Details
Funding
This research was supported in part by the Natural Sciences and Engineering Research Council of Canada.
Cite AsGet 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)0PDF Downloads0Metadata Views
References
- P. K. Agarwal and C. M. Procopiuc. Exact and approximation algorithms for clustering. Algorithmica, 33(2):201-226, 2002.
- P. K. Agarwal and M. Sharir. Efficient algorithms for geometric optimization. ACM Computing Surveys (CSUR), 30(4):412-458, 1998.
- 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.
- 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.
- 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.
- 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.
- S. Durocher. Geometric facility location under continuous motion. PhD thesis, University of British Columbia, 2006.
- 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.
- S. Durocher and D. Kirkpatrick. Bounded-velocity approximation of mobile Euclidean 2-centres. International Journal of Computational Geometry & Applications, 18(03):161-183, 2008.
- D. Eppstein. Faster construction of planar two-centers. In Proc. Symposium on Discrete Algorithms, pages 131-138. ACM/SIAM, 1997.
- 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.
- T. F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38:293-306, 1985.
- S. Har-Peled. Clustering motion. Discrete & Computational Geometry, 31(4):545-565, 2004.
- C. S. Jensen, D. Lin, and B. C. Ooi. Continuous clustering of moving objects. IEEE Trans. Knowl. Data Eng., 19(9):1161-1174, 2007.
- 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.
- 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.
- 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.
- T. W. Liao. Clustering of time series data - a survey. Pattern recognition, 38(11):1857-1874, 2005.
- N. Megiddo and K. J. Supowit. On the complexity of some common geometric location problems. SIAM journal on computing, 13(1):182-196, 1984.
- T. J. Schaefer. The complexity of satisfiability problems. In Proceedings of the tenth annual ACM symposium on Theory of computing, pages 216-226, 1978.
- 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.
- 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.