PNN query processing on compressed trajectories

Shang, Shuo, Yuan, Bo, Deng, Ke, Xie, Kexin, Zheng, Kai and Zhou, Xiaofang (2012) PNN query processing on compressed trajectories. Geoinformatica, 16 3: 467-496. doi:10.1007/s10707-011-0144-5

Author Shang, Shuo
Yuan, Bo
Deng, Ke
Xie, Kexin
Zheng, Kai
Zhou, Xiaofang
Title PNN query processing on compressed trajectories
Journal name Geoinformatica   Check publisher's open access policy
ISSN 1384-6175
Publication date 2012-07-01
Year available 2011
Sub-type Article (original research)
DOI 10.1007/s10707-011-0144-5
Open Access Status Not yet assessed
Volume 16
Issue 3
Start page 467
End page 496
Total pages 30
Place of publication New York, United States
Publisher Springer
Language eng
Subject 1710 Information Systems
3305 Geography, Planning and Development
Abstract Trajectory compression is widely used in spatial-temporal databases as it can notably reduce (i) the computation/communication load of clients (GPS-enabled mobile devices) and (ii) the storage cost of servers. Compared with original trajectories, compressed trajectories have clear advantages in data processing, transmitting, storing, etc. In this paper, we investigate a novel problem of searching the Path Nearest Neighbor based on Compressed Trajectories (PNN-CT query). This type of query is conducted on compressed trajectories and the target is to retrieve the PNN with the highest probability (lossy compression leads to the uncertainty), which can bring significant benefits to users in many popular applications such as trip planning. To answer the PNN-CT query effectively and efficiently, a two-phase solution is proposed. First, we use the meta-data and sample points to specify a tight search range. The key of this phase is that the number of data objects/trajectory segments to be processed or decompressed should be kept as small as possible. Our efficiency study reveals that the candidate sets created are tight. Second, we propose a reconstruction algorithm based on probabilistic models to account for the uncertainty when decompressing the trajectory segments in the candidate set. Furthermore, an effective combination strategy is adopted to find the PNN with the highest probability. The complexity analysis shows that our solution has strong advantages over existing methods. The efficiency of the proposed PNN-CT query processing is verified by extensive experiments based on real and synthetic trajectory data in road networks.
Keyword Compressed trajectory
Path nearest neighbor
Road networks
Spatial databases
Q-Index Code C1
Q-Index Status Confirmed Code
Grant ID DP110103423
Institutional Status UQ
Additional Notes Published online: 15 October 2011

Document type: Journal Article
Sub-type: Article (original research)
Collections: Official 2012 Collection
School of Information Technology and Electrical Engineering Publications
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 10 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 16 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Tue, 06 Mar 2012, 18:46:19 EST by System User on behalf of School of Information Technol and Elec Engineering