Document Open Access Logo

Probing a Set of Trajectories to Maximize Captured Information

Authors Sándor P. Fekete , Alexander Hill , Dominik Krupke , Tyler Mayer, Joseph S. B. Mitchell , Ojas Parekh, Cynthia A. Phillips

PDF
Thumbnail PDF

File

LIPIcs.SEA.2020.5.pdf
  • Filesize: 3.34 MB
  • 14 pages

Document Identifiers

Author Details

Sándor P. Fekete
  • Department of Computer Science, TU Braunschweig, Germany
Alexander Hill
  • Department of Computer Science, TU Braunschweig, Germany
Dominik Krupke
  • Department of Computer Science, TU Braunschweig, Germany
Tyler Mayer
  • Decision Management Systems, Charles River Analytics Inc., Boston, MA, USA
Joseph S. B. Mitchell
  • Department of Applied Mathematics and Statistics, Stony Brook University, NY, USA
Ojas Parekh
  • Sandia National Laboratories, Albuquerque, NM, USA
Cynthia A. Phillips
  • Sandia National Laboratories, Albuquerque, NM, USA

Acknowledgements

Work by Tyler Mayer was mostly carried out while at Stony Brook University. Joe Mitchell and Tyler Mayer were partially supported by the National Science Foundation (CCF-1526406) and a grant from the US-Israel Binational Science Foundation (BSF project 2016116). Joe Mitchell was also partially supported by the DARPA Lagrange program. Sandia National Laboratories is a multimission laboratory managed and operated by National Technology and Engineering Solutions of Sandia, LLC, a wholly owned subsidiary of Honeywell International, Inc., for the U.S. Department of Energy’s National Nuclear Security Administration under contract DE-NA-0003525.

Cite AsGet BibTex

Sándor P. Fekete, Alexander Hill, Dominik Krupke, Tyler Mayer, Joseph S. B. Mitchell, Ojas Parekh, and Cynthia A. Phillips. Probing a Set of Trajectories to Maximize Captured Information. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SEA.2020.5

Abstract

We study a trajectory analysis problem we call the Trajectory Capture Problem (TCP), in which, for a given input set T of trajectories in the plane, and an integer k≥ 2, we seek to compute a set of k points ("portals") to maximize the total weight of all subtrajectories of T between pairs of portals. This problem naturally arises in trajectory analysis and summarization. We show that the TCP is NP-hard (even in very special cases) and give some first approximation results. Our main focus is on attacking the TCP with practical algorithm-engineering approaches, including integer linear programming (to solve instances to provable optimality) and local search methods. We study the integrality gap arising from such approaches. We analyze our methods on different classes of data, including benchmark instances that we generate. Our goal is to understand the best performing heuristics, based on both solution time and solution quality. We demonstrate that we are able to compute provably optimal solutions for real-world instances.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Algorithm engineering
  • optimization
  • complexity
  • approximation
  • trajectories

Metrics

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

Related Versions

Supplementary Materials

References

  1. Mattias Andersson, Joachim Gudmundsson, Patrick Laube, and Thomas Wolle. Reporting leaders and followers among trajectories of moving point objects. GeoInformatica, 12(4):497-528, 2008. Google Scholar
  2. Marc Benkert, Joachim Gudmundsson, Florian Hübner, and Thomas Wolle. Reporting flock patterns. Computational Geometry, 41(3):111-125, 2008. Google Scholar
  3. Kevin Buchin, Maike Buchin, Marc van Kreveld, Bettina Speckmann, and Frank Staals. Trajectory grouping structure. In Algorithms and data structures, pages 219-230. Springer, 2013. Google Scholar
  4. Sándor P. Fekete, Andreas Haas, Michael Hemmer, Michael Hoffmann, Irina Kostitsyna, Dominik Krupke, Florian Maurer, Joseph S. B. Mitchell, Arne Schmidt, Christiane Schmidt, and Julian Troegel. Computing nonsimple polygons of minimum perimeter. Journal of Computational Geometry, 8:340-365, 2017. Google Scholar
  5. Sándor P Fekete, Kan Huang, Joseph SB Mitchell, Ojas Parekh, and Cynthia A Phillips. Geometric hitting set for segments of few orientations. Theory of Computing Systems, 62(2):268-303, 2018. Google Scholar
  6. Sándor P. Fekete, Alexander Hill, Dominik Krupke, Tyler Mayer, Joseph S. B. Mitchell, Ojas Parekh, and Cynthia A. Phillips. Probing a set of trajectories to maximize captured information, 2020. Google Scholar
  7. Joachim Gudmundsson and Marc van Kreveld. Computing longest duration flocks in trajectory data. In Proc. of the 14th Annual ACM International Symposium on Advances in Geographic Information Systems, pages 35-42. ACM, 2006. Google Scholar
  8. Joachim Gudmundsson, Marc van Kreveld, and Bettina Speckmann. Efficient detection of patterns in 2D trajectories of moving points. Geoinformatica, 11(2):195-215, 2007. Google Scholar
  9. Marios Hadjieleftheriou, George Kollios, Dimitrios Gunopulos, and Vassilis J Tsotras. On-line discovery of dense areas in spatio-temporal databases. In Advances in Spatial and Temporal Databases, pages 306-324. Springer, 2003. Google Scholar
  10. Haje Korth, Michelle F. Thomsen, Karl-Heinz Glassmeier, and W. Scott Phillips. Particle tomography of the inner magnetosphere. Journal of Geophysical Research: Space Physics, 107(A9):SMP-5, 2002. Google Scholar
  11. Patrick Laube, Matt Duckham, and Thomas Wolle. Decentralized movement pattern detection amongst mobile geosensor nodes. In Geographic Information Science, pages 199-216. Springer, 2008. Google Scholar
  12. Jae-Gil Lee, Jiawei Han, Xiaolei Li, and Hector Gonzalez. TraClass: trajectory classification using hierarchical region-based and trajectory-based clustering. Proceedings of the VLDB Endowment, 1(1):1081-1094, 2008. Google Scholar
  13. Jae-Gil Lee, Jiawei Han, and Kyu-Young Whang. Trajectory clustering: a partition-and-group framework. In Proc. of the 2007 ACM SIGMOD International Conference on Management of Data, pages 593-604. ACM, 2007. Google Scholar
  14. Yifan Li, Jiawei Han, and Jiong Yang. Clustering moving objects. In Proc. Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 617-622. ACM, 2004. Google Scholar
  15. Zhenhui Li, Bolin Ding, Jiawei Han, and Roland Kays. Swarm: Mining relaxed temporal moving object clusters. Proceedings of the VLDB Endowment, 3(1-2):723-734, 2010. Google Scholar
  16. Pasin Manurangsi. Almost-polynomial ratio eth-hardness of approximating densest k-subgraph. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 954-961, 2017. Google Scholar
  17. Mirco Nanni and Dino Pedreschi. Time-focused clustering of trajectories of moving objects. Journal of Intelligent Information Systems, 27(3):267-289, 2006. Google Scholar
  18. Michal Piorkowski, Natasa Sarafijanovic-Djukic, and Matthias Grossglauser. CRAWDAD dataset epfl/mobility (v. 2009-02-24), doi:10.15783/c7j010, February 2009. Google Scholar
  19. Gerhard Reinelt. TSPLIB-a traveling salesman problem library. ORSA Journal on Computing, 3(4):376-384, 1991. Google Scholar
  20. Md Reaz Uddin, Chinya Ravishankar, and Vassilis J Tsotras. Finding regions of interest from trajectory data. In Mobile Data Management (MDM), 2011 12th IEEE International Conference on, volume 1, pages 39-48. IEEE, 2011. Google Scholar
  21. Marcos R Vieira, Petko Bakalov, and Vassilis J Tsotras. On-line discovery of flock patterns in spatio-temporal data. In Proc. of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 286-295. ACM, 2009. Google Scholar
  22. Yu Zheng. Trajectory data mining: an overview. ACM Transactions on Intelligent Systems and Technology (TIST), 6(3):29, 2015. Google Scholar
  23. Yu Zheng and Xiaofang Zhou. Computing with spatial trajectories. Springer Science & Business Media, 2011. 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 Imprint Privacy Contact