Significant lagrangian linear hotspot discovery

Yan Li, Yiqun Xie, Pengyue Wang, Shashi Shekhar, William Northrop

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Given a collection of multi-attribute trajectories, an event definition, and a spatial network, the Significant Lagrangian Linear Hotspot Discovery (SLLHD) problem finds the paths where records in the trajectories tend to be events in the Lagrangian perspective. The SLLHD problem is of significant societal importance because of its applications in transportation planning, vehicle design, and environmental protection. Its main challenges include the potentially large number of candidate hotspots caused by the tremendous volume of trajectories as well as the non-monotonicity of the statistic measuring event concentration. The related work on the linear hotspot discovery problem is designed in the Eulerian perspective and focuses on point datasets, which ignores the dependence of event occurrence on trajectories and the paths where trajectories are. To solve this problem, we introduce an algorithm in the Lagrangian perspective, as well as five refinements that improve its computational scalability. Two case studies on real-world datasets and experiments on synthetic data show that the proposed approach finds hotspots which are not detectable by existing techniques. Cost analysis and experimental results on synthetic data show that the proposed approach yields substantial computational savings.

Original languageEnglish (US)
Title of host publicationProceedings of the 13th ACM SIGSPATIAL International Workshop on Computational Transportation Science, IWCTS 2020
EditorsAnne Berres, Kuldeep Kurte
PublisherAssociation for Computing Machinery, Inc
ISBN (Electronic)9781450381666
DOIs
StatePublished - Nov 3 2020
Event13th ACM SIGSPATIAL International Workshop on Computational Transportation Science, IWCTS 2020 - Seattle, Virtual, United States
Duration: Nov 3 2020 → …

Publication series

NameProceedings of the 13th ACM SIGSPATIAL International Workshop on Computational Transportation Science, IWCTS 2020

Conference

Conference13th ACM SIGSPATIAL International Workshop on Computational Transportation Science, IWCTS 2020
Country/TerritoryUnited States
CitySeattle, Virtual
Period11/3/20 → …

Bibliographical note

Funding Information:
This material is based upon work supported by the National Science Foundation under Grants No. 1737633, 1901099, 1916518, and IIS-1218168, the USDOD under Grants No. HM1582-08-1-0017 and HM0210-13-1-0005, the Advanced Research Projects Agency-Energy, U.S. Department of Energy under Award No. DE-AR0000795, the NIH under Grant No. UL1 TR002494, KL2 TR002492, and TL1 TR002493, the USDA under Grant No. 2017-51181-27222. The authors would like to thank Kim Koffolt and the University of Minnesota Spatial Computing Research Group for their comments.

Publisher Copyright:
© 2020 ACM.

Keywords

  • hotspot detection
  • lagrangian
  • linear hotspot
  • multi-attribute trajectories
  • statistical significance

Fingerprint

Dive into the research topics of 'Significant lagrangian linear hotspot discovery'. Together they form a unique fingerprint.

Cite this