Journal article
Sampling Big Trajectory Data for Traversal Trajectory Aggregate Query
IEEE transactions on big data, Vol.5(4), pp.550-563
12/01/2019
DOI: 10.1109/TBDATA.2018.2830780
Abstract
This paper defines and investigates a novel trajectory query, namely, Traversal Trajectory Aggregate (TTA) Query: Given a trajectory database and a pair of upstream and downstream spatio-temporal (ST) regions (i.e., spatial area coupled with a time interval), a TTA query aims to retrieve the total number of unique trajectories that traverse through these two ST regions. Such TTA queries play an important role in various urban applications, such as route planning, taxi dispatching, and location-based advertising. Two baselines can answer such TTA queries: (a) exact search (over the entire ST query regions) can obtain the exact answer, but it leads to extremely long running time when the ST query regions are huge; (b) uniform-sampling-based approaches estimate the query answer with sampled trajectories. However, the uniform sampling distribution may lead to significant estimation variance for TTA query, because traversal trajectories are relatively few and unevenly distributed in the query regions. To tackle these challenges, this paper proposes a novel Targeted Index Sampling (TIS) framework to answer TTA queries with high estimation accuracy. TIS employs a two-stage framework, with a Pilot Sampling Estimation (PSE) stage to estimate the distribution of trajectories in ST query region, and an Integrated Importance Sampling (IIS) stage, which collects trajectories with the importance sampling distribution obtained in PSE, and estimates the query result with an asymptotically unbiased estimator. Extensive experiments and case studies using a large-scale real taxi trajectory dataset from Shenzhen, China demonstrate that our TIS framework achieves <; 10 percent estimation error with > 90 percent computational time reduction over exact search, and 50 percent reduction on estimation error (with similar running time) over uniform-distribution-based sampling approaches.
Details
- Title: Subtitle
- Sampling Big Trajectory Data for Traversal Trajectory Aggregate Query
- Creators
- Yichen Ding - Department of Management Sciences, University of Iowa, Iowa City, IAYanhua Li - Department of Computer Science, Worcester Polytechnic Institute, Worcester, MAXun Zhou - Department of Management Sciences, University of Iowa, Iowa City, IAZhuojie Huang - Pitney Bowes Inc., Stamford, CTSimin You - Pitney Bowes Inc., Stamford, CTJun Luo - Machine Intelligence Lab, Lenovo Group Limited, Hong Kong
- Resource Type
- Journal article
- Publication Details
- IEEE transactions on big data, Vol.5(4), pp.550-563
- DOI
- 10.1109/TBDATA.2018.2830780
- ISSN
- 2332-7790
- eISSN
- 2332-7790
- Grant note
- CNS-1657350 / NSF CRII Pitney Bowes Inc. IIS-1566386 / NSF
- Language
- English
- Date published
- 12/01/2019
- Academic Unit
- Business Analytics
- Record Identifier
- 9984083998802771
Metrics
20 Record Views