Personalized trajectory matching in spatial networks

Shuo Shang, Ruogu Ding, Kai Zheng, Christian Søndergaard Jensen, Panos Kalnis, Xiaofang Zhou

Research output: Contribution to journalArticlepeer-review

103 Scopus citations

Abstract

With the increasing availability of moving-object tracking data, trajectory search and matching is increasingly important. We propose and investigate a novel problem called personalized trajectory matching (PTM). In contrast to conventional trajectory similarity search by spatial distance only, PTM takes into account the significance of each sample point in a query trajectory. A PTM query takes a trajectory with user-specified weights for each sample point in the trajectory as its argument. It returns the trajectory in an argument data set with the highest similarity to the query trajectory. We believe that this type of query may bring significant benefits to users in many popular applications such as route planning, carpooling, friend recommendation, traffic analysis, urban computing, and location-based services in general. PTM query processing faces two challenges: how to prune the search space during the query processing and how to schedule multiple so-called expansion centers effectively. To address these challenges, a novel two-phase search algorithm is proposed that carefully selects a set of expansion centers from the query trajectory and exploits upper and lower bounds to prune the search space in the spatial and temporal domains. An efficiency study reveals that the algorithm explores the minimum search space in both domains. Second, a heuristic search strategy based on priority ranking is developed to schedule the multiple expansion centers, which can further prune the search space and enhance the query efficiency. The performance of the PTM query is studied in extensive experiments based on real and synthetic trajectory data sets. © 2013 Springer-Verlag Berlin Heidelberg.
Original languageEnglish (US)
Pages (from-to)449-468
Number of pages20
JournalThe VLDB Journal
Volume23
Issue number3
DOIs
StatePublished - Jul 31 2013

ASJC Scopus subject areas

  • Hardware and Architecture
  • Information Systems

Fingerprint Dive into the research topics of 'Personalized trajectory matching in spatial networks'. Together they form a unique fingerprint.

Cite this