Personalized trajectory matching in spatial networks

Shang, Shuo, Ding, Ruogu, Zheng, Kai, Jensen, Christian S., Kalnis, Panos and Zhou, Xiaofang (2014) Personalized trajectory matching in spatial networks. VLDB Journal, 23 3: 449-468. doi:10.1007/s00778-013-0331-0


Author Shang, Shuo
Ding, Ruogu
Zheng, Kai
Jensen, Christian S.
Kalnis, Panos
Zhou, Xiaofang
Title Personalized trajectory matching in spatial networks
Journal name VLDB Journal   Check publisher's open access policy
ISSN 1066-8888
0949-877X
Publication date 2014-01-01
Year available 2014
Sub-type Article (original research)
DOI 10.1007/s00778-013-0331-0
Open Access Status
Volume 23
Issue 3
Start page 449
End page 468
Total pages 20
Place of publication New York, NY United States
Publisher Association for Computing Machinery, Inc.
Language eng
Subject 1708 Hardware and Architecture
1710 Information Systems
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.
Keyword Efficiency
Optimization
Personalized trajectory matching
Spatial networks
Spatiotemporal databases
Q-Index Code C1
Q-Index Status Confirmed Code
Institutional Status UQ

Document type: Journal Article
Sub-type: Article (original research)
Collections: Official 2015 Collection
School of Information Technology and Electrical Engineering Publications
 
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 18 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 23 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Tue, 03 Jun 2014, 12:39:16 EST by System User on behalf of School of Information Technol and Elec Engineering