Accurate and Efficient Query Processing at Location Based Services Using online Route APIs
Keywords:
Time Dependent Service Graph, Spatial Data Mining, LBS, Elapsed TimeAbstract
Location-based services (LBS) allow mobile users to query the points-of-interest (e.g., restaurants, cafes) on various features (e.g., price, quality, and variety). Additionally users require accurate query results with up-to-date travel times. Lacking the monitoring infrastructure for road traffic, the LBS may obtain live travel times of routes from online route APIs in order to provide accurate results. Our aim is to reduce the number of requests issued by the LBS significantly while preserving accurate query results. Initially, we suggest exploiting recent routes requested from route APIs to answer queries accurately. Then, we design successful lower/upper bounding techniques and ordering techniques to process queries conveniently. Also, we study parallel route requests to further reduce the query response time. Our experimental evaluation shows that our solution is three times more successful than a competitor, and still achieves high result accuracy (above 98 percent).
References
Yu Li, ML. Yiu, “Route Saver:Leveraging Route APIs for accurate and efficient Query Processing at Location Based Services”, in Spatial data mining, Vol. 27, No. 1, pp.56-68, 2001.
U. Demiryurek, FB. Kashani, C Shahabi, A Ranganathan, “Online computation of fastest path in time-dependent spatialnetworks”, International Symposium on Spatial and Temporal Databases (Springer), Berlin pp.92–111, 2011.
EP. Chan, Y. Yang,“Shortest path tree computation in dynamic graphs”, IEEE Transaction on Computer, Vol.58, No. 4, pp. 541–557, 2009.
H Hu, DL Lee, VCS. Lee, “Distance indexing on road networks,” Proceedings of the 32nd international conference on Very large data bases, Korea, pp.894-905, 2006.
Hai Yang, "Traffic restraint, road pricing and network equilibrium", Transportation Research Part B: Methodological Vol.31, Issue.4, pp.303-314, 1997.
M. Safar, “Group k-nearest neighbors queries in spatial network databases”, Journal of geographical systems, Vol.10, Issue.4, pp.407-416, 2008.
T. Seidl, HP. Kriegel, “Optimal multi-step k-nearest neighbor search”, ACM SIGMOD Record, Vol.27, No.2, pp.154-165, 1998.
HP. Kriegel, P Kr•oger, M Renz, T Schmidt, “Hierarchical Graph Embedding for Efficient Query Processing in Very Large Traffic Networks", Proceedings of the 20th international conference on Scientific and Statistical Database Management, China, pp.150-167, 2008.
J. Rishede,T. Man, L. Yiu, “Effective Caching of Shortest Paths for Location-Based Services”, In SIGMOD, Vol.12, pp.313-324, 2012.
D. Zhang , CY. Chow, Q. Li, X. Zhang, Y. Xu, “Efficient Evaluation of k-NN Queries Using Spatial Mashups”, Advances in Spatial and Temporal Databases (Lecture Notes in Computer Science), Vol. 6849, pp.348-366, 2011
D. Zhang, CY. Chow, Q Li, X Zhang, Y Xu, “SMashQ: Spatial mashup framework for k-NN queries in timedependent road networks”, Distributed. Parallel Databases, Vol. 31, pp. 259–287, 2012.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors contributing to this journal agree to publish their articles under the Creative Commons Attribution 4.0 International License, allowing third parties to share their work (copy, distribute, transmit) and to adapt it, under the condition that the authors are given credit and that in the event of reuse or distribution, the terms of this license are made clear.
