A K-main routes approach to spatial network activity summarization

Dev Oliver, Shashi Shekhar, James M. Kang, Renee Laubscher, Veronica Carlan, Abdussalam Bannur

Research output: Contribution to journalArticle

15 Scopus citations

Abstract

Data summarization is an important concept in data mining for finding a compact representation of a dataset. In spatial network activity summarization (SNAS), we are given a spatial network and a collection of activities (e.g., pedestrian fatality reports, crime reports) and the goal is to find \(k\) shortest paths that summarize the activities. SNAS is important for applications where observations occur along linear paths such as roadways, train tracks, etc. SNAS is computationally challenging because of the large number of \(k\) subsets of shortest paths in a spatial network. Previous work has focused on either geometry or subgraph-based approaches (e.g., only one path), and cannot summarize activities using multiple paths. This paper proposes a K-Main Routes (KMR) approach that discovers \(k\) shortest paths to summarize activities. KMR generalizes K-means for network space but uses shortest paths instead of ellipses to summarize activities. To improve performance, KMR uses network Voronoi, divide and conquer, and pruning strategies. We present a case study comparing KMR's network-based output (i.e., shortest paths) to geometry-based outputs (e.g., ellipses) on pedestrian fatality data. Experimental results on synthetic and real data show that KMR with our performance-tuning decisions yields substantial computational savings without reducing summary path coverage.

Original languageEnglish (US)
Article number6574853
Pages (from-to)1464-1478
Number of pages15
JournalIEEE Transactions on Knowledge and Data Engineering
Volume26
Issue number6
DOIs
StatePublished - Jun 2014

Keywords

  • activity summarization
  • hot routes
  • hot spots
  • partitioning
  • spatial network

Fingerprint Dive into the research topics of 'A K-main routes approach to spatial network activity summarization'. Together they form a unique fingerprint.

  • Cite this