Accurate and Efficient Query Processing at Location Based Services Using online Route APIs

RK. Savarapu¹ , Lavanya ²

Section:Review Paper, Product Type: Isroset-Journal
Vol.4 , Issue.3 , pp.16-19, Jun-2016

Online published on Jul 02, 2016

Copyright © RK. Savarapu, Lavanya . This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
 

View this paper at   Google Scholar | DPI Digital Library

XML View     PDF Download

How to Cite this Paper

Abstract :
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).

Key-Words / Index Term :
Time Dependent Service Graph; Spatial Data Mining; LBS, Elapsed Time

References :
[1]. 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.
[2]. 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.
[3]. EP. Chan, Y. Yang,“Shortest path tree computation in dynamic graphs”, IEEE Transaction on Computer, Vol.58, No. 4, pp. 541–557, 2009.
[4]. 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.
[5]. Hai Yang, "Traffic restraint, road pricing and network equilibrium", Transportation Research Part B: Methodological Vol.31, Issue.4, pp.303-314, 1997.
[6]. M. Safar, “Group k-nearest neighbors queries in spatial network databases”, Journal of geographical systems, Vol.10, Issue.4, pp.407-416, 2008.
[7]. T. Seidl, HP. Kriegel, “Optimal multi-step k-nearest neighbor search”, ACM SIGMOD Record, Vol.27, No.2, pp.154-165, 1998.
[8]. 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.
[9]. J. Rishede,T. Man, L. Yiu, “Effective Caching of Shortest Paths for Location-Based Services”, In SIGMOD, Vol.12, pp.313-324, 2012.
[10]. 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
[11]. 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.