近年來由於行動裝置與無線網路蓬勃發展，使得適地性服務（Location-Based Services, LBS）也受到熱烈歡迎，尤其是其中依使用者與物件間的空間相對距離，提供使用者附近熱門的景點與美食等查詢服務的k個最鄰近點查詢（k Nearest Neighbor Queries, kNN）。而隨著虛擬實境、擴增實境的崛起，kNN在應用上出現了不同以往的查詢需求。舉其中虛擬實境的應用來看，在使用者與物件皆處於動態移動的環境中，使用者往往希望能得到鄰近「可視」物件的相關資訊。這些鄰近物件不僅要滿足「相對距離」較近的需求，還需要落於使用者的「視角範圍」內，且不被「障礙物」所遮蔽。此外，在這樣的應用中，隨著物體動態移動造成的高頻率更新需求，也是必須被納入解決這類應用問題的考量之中。但現存並沒有研究同時針對上述動態環境下的查詢條件作完整的考量與提出解決方案。因此針對這個議題本研究提出了「動態環境下針對特定可視範圍限制的k個最鄰近可視物件查詢」，並提出了四個演算法。首先Baseline algorithm透過逐一檢查的方式來找出答案，而在後續的三個演算法，我們分別提出Direction Index 、Obstructed Table與相關的pruning機制，透過考量相對角度關係來大幅提升可視性檢查的效率與執行速度。針對演算法我們也提出一系列的證明來證實各個演算法與其pruning機制的正確性，此外我們也提出update機制來減少動態環境下重運算需求改善整體效能。最後我們利用實驗來評測演算法的效能，透過實驗結果驗證了我們的演算法能有效提昇可視性運算與執行的效率。

With the high development of wireless network and mobile devices, Location-Based Services(LBS) is even more popular. Especially the k Nearest Neighbor Queries(kNN) providing the services such as searching for nearby hot spots or high rated restaurants etc. Furthermore, various searching conditions of kNN query are emerging with the rise of the Virtual Reality, Augmented Reality and related technologies. Take applications of Virtual Reality for example, wearing a virtual glass in a virtual environment where objects may move constantly. The user will be more interested in the information of nearby objects, which are not only close to the user, but also located in the view field of the user, and further visible to the user meaning that these objects are not obstructed by obstacles. There are still no existing studies simultaneously taking all the above searching conditions into consideration. Therefore, in this paper, we propose Continuous Visible k Nearest Neighbor Queries on Moving Objects with View Field constraint and four corresponding algorithms. First, Baseline algorithm finds the solutions by sequential examinations. In the following three more efficient algorithms, we propose Direction Index, Obstructed Table and corresponding pruning techniques, to improve the efficiency of visibility checking and execution time with directional perspective. We also give complete proof to prove the correctness of each algorithm and its pruning techniques. And further propose update techniques to improve the re-computational requests and execution efficiency. Finally, extensive experiments are conducted to evaluate the efficiency of each algorithm, and the results show that our algorithms effectively improve the efficiency of visibility checking and overall execution.

[1] "http://chorochronos.Datastories.Org/."
[2] "http://www.Techawarness.Com/."
[3] "https://www.Unrealengine.Com/what-is-unreal-engine-4."
[4] Rimantas Benetis, Christian S. Jensen, Gytis Karciauskas, and Simonas Saltenis, "Nearest and reverse nearest neighbor queries for moving objects," The VLDB Journal, vol. 15, no. 3, pp. 229-249, 2006.
[5] Stefan Berchtold, Bernhard Ertl, Daniel A. Keim, Hans-Peter Kriegel, and Thomas Seidl, "Fast nearest neighbor search in high-dimensional space," in Proceedings 14th International Conference on Data Engineering, pp. 209-218, 1998.
[6] Muhammad Aamir Cheema, Ljiljana Brankovic, Xuemin Lin, Wenjie Zhang, and Wei Wang, "Continuous monitoring of distance-based range queries," IEEE Transactions on Knowledge and Data Engineering, vol. 23, no. 8, pp. 1182-1199, 2011.
[7] Muhammad Aamir Cheema, Xuemin Lin, Ying Zhang, Wei Wang, and Wenjie Zhang, "Lazy updates: An efficient technique to continuously monitoring reverse knn," Proc. VLDB Endow., vol. 2, no. 1, pp. 1138-1149, 2009.
[8] Dong Wan Choi and Chin Wan Chung, "Nearest neighborhood search in spatial databases," in 2015 IEEE 31st International Conference on Data Engineering, pp. 699-710, 2015.
[9] Ian De Felipe, Vagelis Hristidis, and Naphtali Rishe, "Keyword search on spatial databases," in 2008 IEEE 24th International Conference on Data Engineering, pp. 656-665, 2008.
[10] Yunjun Gao, Baihua Zheng, Gencai Chen, Wang Chien Lee, Ken C. K. Lee, and Qing Li, "Visible reverse k-nearest neighbor queries," in 2009 IEEE 25th International Conference on Data Engineering, pp. 1203-1206, 2009.
[11] Yunjun Gao, Baihua Zheng, Gencai Chen, Qing Li, and Xiaofa Guo, "Continuous visible nearest neighbor query processing in spatial databases," The VLDB Journal, vol. 20, no. 3, pp. 371-396, 2011.
[12] Buğra Gedik and Ling Liu, "Mobieyes: Distributed processing of continuously moving queries on moving objects in a mobile system," in Advances in database technology - edbt 2004: 9th international conference on extending database technology, heraklion, crete, greece, march 14-18, 2004, pp. 67-87, 2004.
[13] Antonin Guttman, "R-trees: A dynamic index structure for spatial searching," SIGMOD Rec., vol. 14, no. 2, pp. 47-57, 1984.
[14] Gísli R. Hjaltason and Hanan Samet, "Distance browsing in spatial databases," ACM Trans. Database Syst., vol. 24, no. 2, pp. 265-318, 1999.
[15] Haibo Hu, Dik Lun Lee, and Jianliang Xu, "Fast nearest neighbor search on road networks," in Proceedings of the 10th international conference on Advances in Database Technology, pp. 186-203, 2006.
[16] Haibo Hu, Jianliang Xu, and Dik Lun Lee, "A generic framework for monitoring continuous spatial queries over moving objects," in Proceedings of the 2005 ACM SIGMOD international conference on Management of data, pp. 479-490, 2005.
[17] Yuan Ko Huang, Shi Jei Liao, and Chiang Lee, "Efficient continuous k-nearest neighbor query processing over moving objects with uncertain speed and direction," in Proceedings of the 20th international conference on Scientific and Statistical Database Management, pp. 549-557, 2008.
[18] Christian S. Jensen, Jan Kolarvr, Torben Bach Pedersen, and Igor Timko, "Nearest neighbor queries in road networks," in Proceedings of the 11th ACM international symposium on Advances in geographic information systems, pp. 1-8, 2003.
[19] K. C. K. Lee, Wang Chien Lee, and Hong Va Leong, "Nearest surrounder queries," in 22nd International Conference on Data Engineering (ICDE'06), pp. 85-85, 2006.
[20] Kyoung Won Lee, Dong Wan Choi, and Chin Wan Chung, "Dart: An efficient method for direction-aware bichromatic reverse k nearest neighbor queries," in Proceedings of the 13th international conference on Advances in Spatial and Temporal Databases, pp. 295-311, 2013.
[21] Guoliang Li, Jianhua Feng, and Jing Xu, "Desks: Direction-aware spatial keyword search," in 2012 IEEE 28th International Conference on Data Engineering, pp. 474-485, 2012.
[22] Mohamed F. Mokbel, Xiaopeing Xiong, and Walid G. Aref, "Sina: Scalable incremental processing of continuous queries in spatio-temporal databases," in Proceedings of the 2004 ACM SIGMOD international conference on Management of data, pp. 623-634, 2004.
[23] Kyriakos Mouratidis, Dimitris Papadias, Spiridon Bakiras, and Yufei Tao, "A threshold-based algorithm for continuous monitoring of k nearest neighbors," IEEE Transactions on Knowledge and Data Engineering, vol. 17, no. 11, pp. 1451-1464, 2005.
[24] Kyriakos Mouratidis, Dimitris Papadias, and Marios Hadjieleftheriou, "Conceptual partitioning: An efficient method for continuous nearest neighbor monitoring," in Proceedings of the 2005 ACM SIGMOD international conference on Management of data, pp. 634-645, 2005.
[25] Kyriakos Mouratidis, Man Lung Yiu, Dimitris Papadias, and Nikos Mamoulis, "Continuous nearest neighbor monitoring in road networks," in Proceedings of the 32nd international conference on Very large data bases, pp. 43-54, 2006.
[26] Sarana Nutanong, Egemen Tanin, and Rui Zhang, "Visible nearest neighbor queries," in Advances in databases: Concepts, systems and applications: 12th international conference on database systems for advanced applications, dasfaa 2007, bangkok, thailand, april 9-12, 2007. Proceedings, pp. 876-883, 2007.
[27] Nick Roussopoulos, Stephen Kelley, and Frederic Vincent, "Nearest neighbor queries," in Proceedings of the 1995 ACM SIGMOD international conference on Management of data, pp. 71-79, 1995.
[28] Zhexuan Song and Nick Roussopoulos, "K-nearest neighbor search for moving query point," in Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, pp. 79-96, 2001.
[29] Nusrat Sultana, Tanzima Hashem, and Lars Kulik, "Group meetup in the presence of obstacles," Inf. Syst., vol. 61, no. C, pp. 24-39, 2016.
[30] Yufei Tao, Dimitris Papadias, and Xiang Lian, "Reverse knn search in arbitrary dimensionality," in Proceedings of the Thirtieth international conference on Very large data bases - Volume 30, pp. 744-755, 2004.
[31] Yufei Tao, Dimitris Papadias, and Qiongmao Shen, "Continuous nearest neighbor search," in Proceedings of the 28th international conference on Very Large Data Bases, pp. 287-298, 2002.
[32] Xia Tian and Zhang Donghui, "Continuous reverse nearest neighbor monitoring," in 22nd International Conference on Data Engineering (ICDE'06), pp. 77-77, 2006.
[33] Yafei Wang, Yunjun Gao, Lu Chen, Gang Chen, and Qing Li, "All-visible-k-nearest-neighbor queries," in Database and expert systems applications: 23rd international conference, dexa 2012, vienna, austria, september 3-6, 2012. Proceedings, part ii, pp. 392-407, 2012.
[34] Yanqiu Wang, Rui Zhang, Chuanfei Xu, Jianzhong Qi, Yu Gu, and Ge Yu, "Continuous visible k nearest neighbor query on moving objects," Information Systems, vol. 44, pp. 1-21, 2014.
[35] Kun Lung Wu, Shyh Kwei Chen, and Philip S. Yu, "Processing continual range queries over moving objects using vcr-based query indexes," in The First Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services, 2004. MOBIQUITOUS 2004., pp. 226-235, 2004.
[36] Kun Lung Wu, Shyh Kwei Chen, and Philip S. Yu, "Incremental processing of continual range queries over moving objects," IEEE Transactions on Knowledge and Data Engineering, vol. 18, no. 11, pp. 1560-1575, 2006.
[37] Hu Xu, Zhicheng Li, Yansheng Lu, Ke Deng, and Xiaofang Zhou, "Group visible nearest neighbor queries in spatial databases," in Web-age information management: 11th international conference, waim 2010, jiuzhaigou, china, july 15-17, 2010. Proceedings, pp. 333-344, 2010.
[38] Sungmin Yi, HaRim Jung, Jun Pyo Park, and Yon Dohn Chung, "On processing view field nearest neighbor queries on the r*-tree," in 2011 International Conference on Electrical and Control Engineering, pp. 4838-4841, 2011.
[39] Sungmin Yi, Hyoseok Ryu, Jihoon Son, and Yon Dohn Chung, "View field nearest neighbor: A novel type of spatial queries," Information Sciences, vol. 275, pp. 68-82, 2014.
[40] Sungmin Yi, Changbeom Shim, and Yon Dohn Chung, "Reverse view field nearest neighbor queries," Information Sciences, vol. 402, pp. 35-49, 2017.
[41] Xiaohui Yu, Ken Q. Pu, and Nick Koudas, "Monitoring k-nearest neighbor queries over moving objects," in 21st International Conference on Data Engineering (ICDE'05), pp. 631-642, 2005.
[42] Dongxiang Zhang, Chee Yong Chan, and Kian Lee Tan, "Nearest group queries," in Proceedings of the 25th International Conference on Scientific and Statistical Database Management, p. 7, 2013.