Efficient Computation of Continuous Range Skyline Queries in Road Networks

详细信息    查看全文

• 关键词：Continuous range skyline queries ; Road networks ; Network voronoi diagram ; Dynamic split points setting
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9773
• 期：1
• 页码：520-532
• 全文大小：1,034 KB
• 参考文献：1.Aljubayrin, S., He, Z., Zhang, R.: Skyline trips of multiple POIs categories. In: Renz, M., Shahabi, C., Zhou, X., Chemma, M.Aamir (eds.) DASFAA 2015. LNCS, vol. 9050, pp. 189–206. Springer, Heidelberg (2015)
  2.Borzsony, S., Kossmann, D., Stocker, K.: The skyline operator. In: Proceedings of the 17th International Conference on Data Engineering (ICDE), Heidelberg, Germany (2001)
  3.Chomicki, J., Godfrey, P., Gryz, J.: Skyline with presorting. In: Proceedings of the 19th International Conference on Data Engineering (ICDE), Bangalore, India (2003)
  4.Deng, K., Zhou, X., Shen, H.T.: Multi-source skyline query processing in road networks. In: Proceedings of the 19th International Conference on Data Engineering (ICDE), Istanbul, Turkey (2007)
  5.Godfrey, P., Shipley, R., Gryz, J.: Maximal vector computation in large data sets. In: Proceedings of the 31st International Conference on Very Large Data Bases (VLDB), Trondheim, Norway (2005)
  6.Huang, Y.H., Chang, C.H., Lee, C.: Continuous distance-based skyline queries in road networks. Inf. Syst. 37(7), 611–633 (2012)CrossRef
  7.Jang, S., Yoo, J.: Processing continuous skyline queries in road networks. In: International Symposium on Computer Science and its Applications (CSA) (2008)
  8.Kolahdouzan, M., Shahabi, C.: Voronoi-based K nearest neighbor search for spatial network databases. In: Proceedings of the 30th International Conference on Very Large Data Bases (VLDB), Toronto, Ontario, Canada (2004)
  9.Kolahdouzan, M.R., Shahabi, C.: Alternative solutions for continuous K nearest neighbor queries in spatial network databases. Geoinformatica 9(4), 321–341 (2005)CrossRef
  10.Kriegel, H.P., Renz, M., Schubert, M.: Route skyline queries: a multi-preference path planning approach. In: Proceedings of the 26th International Conference on Data Engineering (ICDE), Long Beach, California, USA (2010)
  11.Mouratidis, K., Lin, Y., Yiu, M.L.: Preference queries in large multi-cost transportation networks. In: Proceedings of the 26th International Conference on Data Engineering (ICDE), Long Beach, California, USA (2010)
  12.Papadias, D., Tao, Y., Fu, G.: Progressive skyline computation in database systems. TODS 30(1), 41–82 (2005)CrossRef
  13.Safar, M.: K nearest neighbor search in navigation systems. Mob. Inf. Syst. 1(3), 207–224 (2005)
  14.Safar, M., El-Amin, D., Taniar, D.: Optimized skyline queries on road networks using nearest neighbors. Pers. Ubiquit. Comput. 15(8), 845–856 (2011)CrossRef
  15.Son, W., Hwang, S.W., Ahn, H.K.: MSSQ: manhattan spatial skyline queries. Inf. Syst. 40, 67–83 (2014)CrossRef
  16.Tian, Y., Lee, K.C.K., Lee, W.-C.: Finding skyline paths in road networks. In: Proceedings of the 17th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems (GIS), Seattle, Washington, USA (2009)
  
• 作者单位：Shunqing Jiang (16)
  Jiping Zheng (16) (17)
  Jialiang Chen (16)
  Wei Yu (16)
  
  16. College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing, China
  17. School of Computer Science and Engineering, University of New South Wales, Sydney, Australia
  
• 丛书名：Intelligent Computing Methodologies
• ISBN：978-3-319-42297-8
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9773

文摘

Skyline query processing in road networks has been investigated extensively in recent years. Skyline points for road network applications may be large while the query point may only interest the ones within a certain range. In this paper, we address the issue of efficient evaluation of Continuous Range Skyline Queries (CRSQ) in road networks. Due to the computation of network distance between objects in road networks is expensive and suffers the limitation of memory resources, we propose a novel method named Dynamic Split Points Setting (DSPS) dividing a given path in road networks into several segments. For each segment, we use Network Voronoi Diagrams (NVDs) based technique to calculate the candidate skyline interest points at the starting point of the segment. After that, when the query point moves, we dynamically set the spilt points by DSPS strategy to ensure that when the query point moves within a segment, skyline points remain unchanged and only need to be updated while moving across the split points. Extensive experiments show that our DSPS strategy is efficient compared with previous approaches.