Continuous Maximum Visibility Query for a Moving Target

详细信息    查看全文

• 关键词：Visibility query ; Moving object ; Spatial database
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9877
• 期：1
• 页码：82-94
• 全文大小：1,150 KB
• 参考文献：1.Ali, M.E., Tanin, E., Zhang, R., Kulik, L.: A motion-aware approach for efficient evaluation of continuous queries on 3d object databases. VLDB J. 19(5), 603–632 (2010)CrossRef
  2.Aronov, B., Guibas, L.J., Teichmann, M., Zhang, L.: Visibility queries and maintenance in simple polygons. DCG 27(4), 461–483 (2002)MathSciNet MATH
  3.Asano, T., Guibas, L.J., Hershberger, J., Imai, H.: Visibility of disjoint polygons. Algorithmica 1(1), 49–63 (1986)MathSciNet CrossRef MATH
  4.Ben-Moshe B., Hall-Holt, O., Katz, M.J., Mitchell, J.S.B.: Computing the visibility graph of points within a polygon. In: SCG, pp. 27–35 (2004)
  5.Choudhury, F.M., Ali, M.E., Masud, S., Nath, S., Rabban, I.E.: Scalable visibility color map construction in spatial databases. Inf. Syst. 42, 89–106 (2014)CrossRef
  6.Davis, L.S., Benedikt, M.L.: Computational models of space: Isovists and isovist fields. Comput. Graph. Image Process. 11(1), 49–72 (1979)CrossRef
  7.Gao, Y., Zheng, B.: Continuous obstructed nearest neighbor queries in spatial databases. In: SIGMOD, pp. 577–590 (2009)
  8.Gao, Y., Zheng, B., Lee, W., Chen, G.: Continuous visible nearest neighbor queries. In: EDBT, pp. 144–155 (2009)
  9.Graham, R., Knuth, D., Patashnik, O.: Concrete Mathematics. Addison-Wesley, Boston (1994)MATH
  10.Masud, S., Choudhury, F.M., Ali, M.E., Nutanong, S.: Maximum visibility queries in spatial databases keys. In: ICDE, pp. 637–648 (2013)
  11.Nutanong, S., Tanin, E., Zhang, R.: Visible nearest neighbor queries. In: Kotagiri, R., Radha Krishna, P., Mohania, M., Nantajeewarawat, E. (eds.) DASFAA 2007. LNCS, vol. 4443, pp. 876–883. Springer, Heidelberg (2007)CrossRef
  12.Rabban, I.E., Abdullah, K., Ali, M.E., Cheema, M.A.: Visibility color map for a fixed or moving target in spatial databases. In: Claramunt, C., Schneider, M., Wong, R.C.-W., Xiong, L., Loh, W.-K., Shahabi, C., Li, K.-J. (eds.) SSTD 2015. LNCS, vol. 9239, pp. 197–215. Springer, Heidelberg (2015)CrossRef
  13.Shou, L., Huang, Z., Tan, K.-L.: Hdov-tree: the structure, the storage, the speed. In: ICDE (2003)
  14.Suri, S., ORourke, J.: Worst-case optimal algorithms for constructing visibility polygons with holes. In: SCG, pp. 14–23 (1986)
  15.Zarei, A.R., Ghodsi, M.: Efficient computation of query point visibility in polygons with holes. In: SCG, pp. 6–8 (2005)
  
• 作者单位：Ch. Md. Rakin Haider (16)
  Arif Arman (16)
  Mohammed Eunus Ali (16)
  Farhana Murtaza Choudhury (17)
  
  16. Bangladesh University of Engineering and Technology, Dhaka, Bangladesh
  17. RMIT University, Melbourne, Australia
  
• 丛书名：Databases Theory and Applications
• ISBN：978-3-319-46922-5
• 刊物类别：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
• 卷排序：9877

文摘

Opportunities to answer many real life queries such as “which surveillance camera has the best view of a moving car in the presence of obstacles?” have become a reality due to the development of location based services and recent advances in 3D modeling of urban environments. In this paper, we investigate the problem of continuously finding the best viewpoint from a set of candidate viewpoints that provides the best view of a moving target in presence of visual obstacles in 2D or 3D space. We propose a query type called k Continuous Maximum Visibility (kCMV) query that ranks k query viewpoints (or locations) from a set of candidate viewpoints in the increasing order of the visibility measure of the target from these viewpoints. We propose two approaches that reduce the set of query locations and obstacles to consider during visibility computation and efficiently update the results as target moves. We conduct extensive experiments to demonstrate the effectiveness and efficiency of our solutions for a moving target in presence of obstacles.