1. Home
  2. Issues
  3. Volume 28, Issue 1 (2017)
  4. Safe-Region Generation Methods for Conti ...

Informatica


Safe-Region Generation Methods for Continuous Trip Route Planning Queries
Volume 28, Issue 1 (2017), pp. 131–154
Pub. online: 1 January 2017      Type: Research Article      Open accessOpen Access
Received
1 October 2016
Accepted
1 February 2017
Published
1 January 2017

Abstract

Continuous query is a monitoring query issued by a moving object to keep the query condition satisfied. In the continuous query, the safe-region method is preferable to reduce the load for several requests on the server. A safe-region is a region in which the query result is unchanged, and it is created and sent to the moving object with the query result. The moving object always checks the current position in the region. When it leaves the region, it requests a new result to the server. Safe-region generation methods have been eagerly discussed for simple query types, including kNN, distance range, and RkNN queries. This paper challenges to generate the safe-region for trip route planning queries (TRPQ). This type of query is very time consuming even for snap-shot queries, and therefore, there are many restrictions on the safe-region generation methods in existing studies. This paper first investigates the property of the safe-region on TRPQ, and then proposes two types of efficient algorithms, the preceding rival addition (PRA) and the tardy rival addition (TRA) algorithms. The former algorithm runs fast, however, it still requires long processing time when the density of the data object is high. The latter algorithm is very fast independent of the density of data objects, however, the safe-region generated by TRA becomes about 5% larger in the size of generated safe-region. We evaluate the performance through intensive experiments.

References

 
Bentis, R., Jensen, C.S., Karčlauskas, G., Šaltenis, S. (2006). Nearest and reverse nearest neighbor queries for moving objects. The VLDB Journal, 15(3), 229–250.
 
Cheema, M.A., Brankovic, L., Lin, X., Zhang, W., Wang, W. (2011). Continuous monitoring of distance based range queries. IEEE Transactions on Knowledge and Data Engineering, 23, 1182–1199.
 
Chen, H., Ku, W.S., Sun, M.T., Zimmermann, R. (2008). The multi-rule partial sequenced route query. In: Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 65–74.
 
Chen, Z., Shen, H.T., Zhou, X., Yu, J.X. (2009). Monitoring path nearest neighbor in road networks. In: Proceedings SIGMOD’09 Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data, pp. 591–602.
 
Costa, C.F., Nascimento, M.A., Mecodo, J.A.F., Theodoridis, Y., Pelekis, N., Machado, J. (2015). Optimal time-dependent sequenced route queries in road networks. In: Proceedings SIGSPATIAL ’15 Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems. ISBN: 978-1-4503-3967-4. Article No. 56.
 
Gedik, B., Liu, L. (2004). Mobieyes: distributed processing of continuously moving queries on moving objects in a mobile system. In:Proceedings EDBT 2004 Proceedings of the 9th International Conference on Extending Database Technology, LNCS, Vol. 2992. pp. 67–87.
 
Htoo, H., Ohsawa, Y., Sonehara, N., Sakauchi, M. (2012). Optimal sequenced route query algorithm using visited poi graph. In: Proceedings WAIM2012 Proceedings of the 13th International Conference on Web-Age Information Management, LNCS, Vol. 7418, pp. 198–209.
 
Htoo, H., Ohsawa, Y., Sonehara, N., Sakauchi, M. (2013). Incremental single-source multi target A* algorithm for LBS based on road network distance. Journal IEICE Transactions on Information and Systems E, 96–D(5), 1043–1052.
 
Huang, Y.K., Chang, C.H., Lee, C. (2012). Continuous distance-based skyline queries in road networks. Journal Information Systems, 37(7), 611–633.
 
Iwerks, G.S., Samet, H., Smith, K.P. (2004). Maintenance of spatial semijoin queries on moving points. In: Proceedings 2004 VLDB Conference Proceedings 2004 VLDB Conference, pp. 828–839.
 
Li, F., Cheng, D., Hadjieleftheriou, M., Kollios, G., Teng, S.H. (2005). On trip planning queries in spatial databases. In: Proceeding SSTD’05 Proceedings of the 9th International Conference on Advances in Spatial and Temporal Databases, pp. 273–290.
 
Mouratidis, K., Yiu, M.L., Papadias, D., Mamoulis, N. (2006). Continuous nearest neighbor monitoring in road networks. In: Proceeding VLDB ’06 Proceedings of the 32nd International Conference on Very Large Data Bases, pp. 43–54.
 
Nutanong, S., Tanin, E., Shao, J., Zahang, R., Ramamohanarao, K. (2012). Continuous detour queries in spatial networks. Journal IEEE Transactions on Knowledge and Data Engineering, 24(7), 1201–1215.
 
Ohsawa, Y., Htoo, H., Sonehara, N., Sakauchi, M. (2012). Sequenced route query in road network distance based on incremental Euclidean restriction. In: Proceeding DEXA 2012 Proceedings of the 23rd International Conference on Database and Expert Systems Applications, LNCS, Vol. 7446, pp. 484–491.
 
Ohsawa, Y., Htoo, H., Win, T.N. (2016). Continuous trip route planning queries. In: Proceedings ADBIS 2016 Proceedings of the 20th East European Conference on Advances in Databases and Information Systems, LNCS, Vol. 9809. Springer, ISBN: 978-1-4503-3967-4, pp. 198–211.
 
Papadias, D., Zhang, J., Mamoulis, N., Tao, Y. (2003). Query processing in spatial network databases. In: Proceeding VLDB ’03 Proceedings of the 29th International Conference on Very Large Data Bases, pp. 802–813.
 
Prabhakar, S., Xia, Y., Kalashnikov, D., Aref, W., Hambrush, S. (2002). Query indexing and velocity constrained indexing: Scalable techniques for continuous queries on moving objects. Journal IEEE Transactions on Computers, 51(10), 1124–1140.
 
Sharifzadeh, M., Kalahdouzan, M., Shahabi, C. (2005). The optimal sequenced route query. Journal the VLDB, 765–787.
 
Sharifzadeh, M., Shahabi, C. (2008). Processing optimal sequenced route queries using Voronoi diagram. Geoinformatica an International Journal on Advances of Computer Science for Geographic Information Systems, 12(8), 411–433.
 
Xia, T., Zhang, D. (2006). Continuous reverse nearest neighbor monitoring. In: Proceeding of the 22nd International Conference on Data Engineering, pp. 68–77.

Biographies

Ohsawa Yutaka
ohsawa@mail.saitama-u.ac.jp

Y. Ohsawa received his BE and ME degrees from Shinshu University in 1976 and 1978, respectively, and his PhD degree from the University of Tokyo in 1985. From 1979 to 1989, he worked for the Institute of Industrial Science at the University of Tokyo as a research associate and an assistant professor. Since 1989, he has worked for Saitama University. He is currently a professor at the Graduate School of Science and Engineering at Saitama University. His research interests include geographic information systems, spatio-temporal databases, and location based services.

Htoo Htoo
htoohtoo@mail.saitama-u.ac.jp

H. Htoo received her BCSc and MCSc degrees from University of Computer Studies (UCSY),Yangon, Myanmar in 2002 and 2004, respectively. She worked as a teaching staff at UCSY from 2004 to 2008. She received her PhD degree from Saitama University, Japan in 2013. Currently, she is an assistant professor at Saitama University with the specialization in location based services and spatio-temporal databases.

Win Tin Nilar

T.N. Win received her Bachelor of Engineering (B.E.IT) from the Mandalay Technological University (MTU), Myanmar, in 2006. She is currently a student at the Graduate School of Science and Engineering, Saitama University, Japan. Her research interests include geographic information systems and location based services.


Full article Cited by PDF XML
Full article Cited by PDF XML

Copyright
© 2017 Vilnius University
Open access article under the CC BY license.

Keywords
safe-region trip route planning queries continuous trip route planning queries road network distance

Metrics
since January 2020
967

Article info
views

470

Full article
views

432

PDF
downloads

245

XML
downloads


Share


RSS