Searching trajectories by locations: An efficiency study

Chen, Zaiben, Shen, Heng Tao, Zhou, Xiaofang, Zheng, Yu and Xie, Xing (2010). Searching trajectories by locations: An efficiency study. In: Proceedings of the 2010 International Conference on Management of Data, SIGMOD '10. 2010 ACM SIGMOD/PODS Conference, Indianapolis, IN, USA, (255-266). 6-11 June 2010. doi:10.1145/1807167.1807197

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads
uq220625_Checklists.pdf HERDC Checklist - Not publicly available application/pdf 264.88KB 0

Author Chen, Zaiben
Shen, Heng Tao
Zhou, Xiaofang
Zheng, Yu
Xie, Xing
Title of paper Searching trajectories by locations: An efficiency study
Conference name 2010 ACM SIGMOD/PODS Conference
Conference location Indianapolis, IN, USA
Conference dates 6-11 June 2010
Proceedings title Proceedings of the 2010 International Conference on Management of Data, SIGMOD '10   Check publisher's open access policy
Journal name Association for Computing Machinery. Special Interest Group on Management of Data. International Conference Proceedings   Check publisher's open access policy
Place of Publication New York, NY, USA
Publisher Association for Computing Machinery
Publication Year 2010
Sub-type Fully published paper
DOI 10.1145/1807167.1807197
Open Access Status Not yet assessed
ISBN 9781450300322
ISSN 0730-8078
Start page 255
End page 266
Total pages 12
Language eng
Formatted Abstract/Summary
Trajectory search has long been an attractive and challenging topic which blooms various interesting applications in spatial-temporal databases. In this work, we study a new problem of searching trajectories by locations, in which context the query is only a small set of locations with or without an order specified, while the target is to find the k Best-Connected Trajectories (k-BCT) from a database such that the k-BCT best connect the designated locations geographically. Different from the conventional trajectory search that looks for similar trajectories w.r.t. shape or other criteria by using a sample query trajectory, we focus on the goodness of connection provided by a trajectory to the specified query locations. This new query can benefit users in many novel applications such as trip planning. In our work, we firstly define a new similarity function for measuring how well a trajectory connects the query locations, with both spatial distance and order constraint being considered. Upon the observation that the number of query locations is normally small (e.g. 10 or less) since it is impractical for a user to input too many locations, we analyze the feasibility of using a general-purpose spatial index to achieve efficient k-BCT search, based on a simple Incremental k-NN based Algorithm (IKNN). The IKNN effectively prunes
and refines trajectories by using the devised lower bound and upper bound of similarity. Our contributions mainly lie in adapting the best-first and depth-first k-NN algorithms to the basic IKNN properly, and more importantly ensuring the efficiency in both search effort and memory usage. An in-depth study on the adaption and its efficiency is provided. Further optimization is also presented to accelerate the IKNN algorithm. Finally, we verify the efficiency of the algorithm by extensive experiments.
Keyword Trajectory Search
Q-Index Code E1
Q-Index Status Confirmed Code
Institutional Status UQ
Additional Notes SIGMOD/PODS '10 International Conference on Management of Data Research session 6

Document type: Conference Paper
Sub-type: Fully published paper
Collections: Official 2011 Collection
ERA 2012 Admin Only
School of Information Technology and Electrical Engineering Publications
Version Filter Type
Citation counts: Scopus Citation Count Cited 104 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Wed, 17 Nov 2010, 00:42:07 EST by Dr Heng Tao Shen on behalf of School of Information Technol and Elec Engineering