近年來，空間資訊分析已經逐漸受到重視，因為它可以廣泛的應用在各個領域，其中最佳位址查詢是空間資訊分析中相當重要的一個議題。舉凡居住地、商家、公共建設的地理位置選擇都屬於最佳位址查詢的範疇。因此本論文提出了一個讓使用者根據自身需求尋找最佳位址的應用。一般來說，使用者在考量最佳位址的時候，會受到周邊環境的影響，希望靠近具有正向屬性的地點並且遠離具有負向屬性的地點。舉個例子來說，在使用者選擇居住地時，會希望靠近擁有學校、公園或是賣場等屬性的地點，另一方面會希望遠離具有垃圾場、KTV、瓦斯行等屬性的地點。然而對於使用者而言不同屬性的重要程度也會不一樣，以上面的例子為例，使用者可能因為家中有小孩因此學校這個屬性對居住地的選擇具有較高的影響力。另外在現代社群網站中，打卡(Check-in)和標籤(Hashtag)都是經常會使用到的功能。透過社群網站上的打卡和標籤功能可以產生地圖上具有關鍵字(Keyword)的地點。在本論文中，我們使用關鍵字來表示使用者的需求與地圖上地點所擁有的屬性，而權重(Weight)則用來表示不同關鍵字的影響力。除此之外，具有相同屬性地點也會因為名氣不同而有不同的影響力。可以透過計算一個地點打卡次數的多寡可以估算某個地點的名氣指數(Popularity)。

In recent years, spatial information analysis has gradually received attention because it can be widely used in various fields. Among them, the optimal location query is a very important topic in spatial information analysis. Finding the geographic location of the place of residence, business, and public construction are all in the category of the optimal location query. Therefore, this project proposes an application that allows users to find the best location according to their user preferences. In general, when considering the best location, the user would like to be close to places with a positive attribute and away from places with a negative attribute. For example, when a user wants to choose a place of residence, they would like to be close to places with attributes such as a school, a park, or a store. On the other hand, they would like to stay away from places with attributes such as landfill, KTV, and gas store. However, the importance of different attributes may be different from users. For example, keywords like school may have a higher influence on the choice of the place of residence because of the child in the family. In addition, in up-to-date social networking sites, check-in and hashtags are features that are often used. Points with keywords on the map can be generated via the check-in and hashtags on the social networking site. In this project, we use keywords to represent the user preferences and the attributes owned by places on the map, and the weight is used to indicate the influence of different keywords. In addition, places with the same attributes will have different influences due to different popularity. We can estimate the popularity of places by calculating the number of check-in at the location of places.

[1] Farhana Murtaza Choudhury, J. Shane Culpepper, Zhifeng Bao, and Timos Sellis, “Finding the optimal location and keywords in obstructed and unobstructed space,” the VLDB Journal, Vol. 27(4), August 2018.
[2] Alvis Logins, “Node Selection in Large Networks,” in Proceedings of 2018 IEEE 34th International Conference on Data Engineering (ICDE), Paris, France, 16-19 April 2018.
[3] Yu-Chi Chung, I-Fang Su, and Chiang Lee, “k-most suitable locations selection,” International Journal on Advances of Computer Science for Geographic Information Systems (GeoInformatica), October 2018, Vol. 22(4), pp 661–692.
[4] Lv Xu, Canglin Mai, Zitong Chen, Yubao Liu, and Genan Dai, “MinSum Based Optimal Location Query in Road Network,” in Proceedings of International Conference on Database Systems for Advanced Applications (Dasfaa 2017), 2017, March.
[5] Ruifeng Liu, Ada Wai-Chee, Zitong Chen, Silu Huang, and Yubao Liu, “Finding multiple new optimal locations in a road network,” in Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Burlingame, California, Oct. 31 – Nov. 03, 2016.
[6] Xiao, Xiaokui, Bin Yao, and Feifei Li. "Optimal location queries in road network databases," in Proceedings of 2011 IEEE 27th International Conference on Data Engineering, Hannover, Germany, 11-16 April 2011.
[7] Dongxiang Zhang, Yuchen Li, Xin Cao, Jie Shao, and Heng Tao Shen, “Augmented keyword search on spatial entity databases,” The VLDB Journal, Vol. 27(2), April 2018.
[8] Dongxiang Zhang, Kian-Lee Tan, and Anthony K. H. Tung, “Scalable top-k spatial keyword search,” in Proceedings of the 16th International Conference on Extending Database Technology (EDBT 2013), Genoa, Italy, Pages 359-370, March 18 - 22, 2013.
[9] Jingwen Zhao, Yunjun Gao, Gang Chen, Christian S. Jensen, Rui Chen, and Deng Cai, “Reverse Top-k Geo-Social Keyword Queries in Road Networks,” in Proceedings of 2017 IEEE 33rd International Conference on Data Engineering (ICDE), San Diego, CA, USA, 19-22 April 2017.
[10] Sen Zhao, Xiang Cheng, Sen Su, and Kai Shuang, “Popularity-aware collective keyword queries in road networks,” GeoInformatica, Vol. 21(3), pp 485–518, July 2017.
[11] Xin, Cong Gao, Jensen Christian, Ooi Beng Chin, “Collective spatial keyword querying,” in Proceedings of the 2011 ACM SIGMOD International Conference on Management of data, Pages 373-384, Athens, Greece, June 12 - 16, 2011.
[12] L Chen, G Cong, CS Jensen, D Wu, “Spatial keyword query processing: an experimental evaluation,” in Proceedings of the 39th international conference on Very Large Data Bases (VLDB), Pages 217-228, January 2013.
[13] JB Rocha-Junior, K Nørvåg, "Top-k spatial keyword queries on road networks," EDBT, 2012.
[14] Siqiang Luo, Yifeng Luo, Shuigeng Zhou, Gao Cong, Jihong Guan, Zheng Yong, “Distributed Spatial Keyword Querying on Road Networks,” EDBT, 2014.
[15] Chen Gang, Zhao Jingwen, Gao Yunjun, Chen Lei, Chen Rui, “Time-Aware Boolean Spatial Keyword Queries,” TKDE, 2017.
[16] A Cary, O Wolfson, N Rishe, “Efficient and Scalable Method for Processing Top-k Spatial Boolean Queries”, SSDBM, 2010
[17] J. B. Rocha-Junior, O. Gkorgkas, S. Jonassen, and K. Nørvag, “Efficient processing of top-k spatial keyword queries,” SSTD, 2011.
[18] G. Tsatsanifos and A. Vlachou, “On processing top-k spatio-textual preference queries,” EDBT, 2015.
[19] Dimitris Sacharidis, and Antonios Deligiannakis, “Spatial Cohesion Queries,” in Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, Seattle, Washington, Nov. 03 - 06, 2015.
[20] Zhisheng Li, Ken C.K. Lee, Baihua Zheng, Wang-Chien Lee, Dik Lee, and Xufa Wang, “IR-Tree: An Efficient Index for Geographic Document Search,” IEEE Transactions on Knowledge and Data Engineering, Vol. 23(4), April 2011.
[21] Yu-Chi Chung, I-Fang Su, Chiang Lee, and Pei-Chi Liu, “Multiple k Nearest Neighbor Search,” in World Wide Web Journal Vol.20, Issue 2, pp. 371-398, March 2017.
[22] Yu-Chi, Chung, I-Fang Su, Chaing Lee, and Ding-Li Chen, “Finding Visible kNN Objects with the View Field Constraint,” in Proceedings of the first international cognitive cities conference (IC3 2018), August 7-9, 2018, Okinawa, Japan.
[23] Yu-Chi Chung, I-Fang Su, Chiang Lee, and Chao-Yue He, “Finding the Personal Fitness Trip Plan in Road Networks,”the 27th Wireless and Optical Communications Conference (WOCC 2018), April 30-May 1, 2018.
[24] Yu-Chi Chung, I-Fang Su, Chiang Lee, and Gary Gu, “An efficient distributed range query processing algorithm on LiDAR data,”2017 10th International Conference on Ubi-Media Computing and Workshops, Pattaya, Thailand, Aug. 1-4, 2017.
[25] Cheng-Wei Lee, Yu-Chi Chung, I-Fang Su, Chiang Lee, “Personalize path recommendation in dynamic networks based on big trajectory data”, DLT, Jun. 2017, Taiwan, Chiayi.
[26] Ding-Li Chen, Yu-Chi Chung, I-Fang Su, Chiang Lee, “Finding Visible kNN Objects with the View Field Constraint”, Itaoi , May 2017, Taiwan, Kinmen.
[27] Chao-Yue He, Yu-Chi Chung, I-Fang Su, Chiang Lee, “On personal tightest trip planning query in road” , Itaoi , May 2017, Taiwan, Kinmen.
[28] Du Y, Zhang D, Xia T, “The optimal-location query”, In: Advances in Spatial and Temporal Databases. Springer, pp 163–180, 2005.
[29] Xia T, Zhang D, Kanoulas E, Du Y, “On computing top-t most influential spatial sites”, In: Proceedings of the 31st international conference on Very large data bases. VLDB Endowment, pp 946–957, 2005.
[30] Wong RC-W, O¨ zsu MT, Yu PS, Fu AW-C, Liu L, “Efficient method for maximizing bichromatic reverse nearest neighbor”, Proc VLDB Endowment 2(1):1126–1137, 2009.
[31] Yan D, Wong RC-W, Ng W, “Efficient methods for finding influential locations with adaptive grids.”, In: Proceedings of the 20th ACM international conference on Information and knowledge management. ACM, pp 1475–1484, 2011.
[32] Wong RC-W, O¨ zsu MT, Fu AW-C, Yu PS, Liu L, Liu Y, “Maximizing bichromatic reverse nearest neighbor for lp-norm in two-and three-dimensional spaces.”, VLDB J Int J Very Large Data Bases 20(6):893–919, 2011.
[33] Ghaemi P, Shahabi K, Wilson JP, Banaei-Kashani F, “Optimal network location queries.”, In: Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM, pp 478–481, 2010.
[34] Zhou Z, Wu W, Li X, Lee ML, Hsu W, “Maxfirst for maxbrknn.”, In: 2011 IEEE 27th International Conference on Data Engineering (ICDE). IEEE, pp 828–839, 2011.
[35] Zheng K, Huang Z, Zhou A, Zhou X, “Discovering the most influential sites over uncertain data: A rank-based approach.”, IEEE Trans Knowl Data Eng 24(12):2156–2169, 2012.
[36] Shang S, Yuan B, Deng K, Xie K, Zhou X, “Finding the most accessible locations: reverse path nearest neighbor query in road networks.”, In: Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM, pp 181–190, 2011.
[37] Huang J, Wen Z, Qi J, Zhang R, Chen J, He Z, “Top-k most influential locations selection,”, In: Proceedings of the 20th ACM international conference on Information and knowledge management. ACM, pp 2377–2380, 2011.
[38] Chen J, Huang J, Wen Z, He Z, Taylor K, Zhang R, “Analysis and evaluation of the top-k most influential location selection query,”, Knowl Inf Syst 43(1):181–217, 2015.
[54] Qi J, Zhang R, Kulik L, Lin D, Xue Y, “The min-dist location selection query,” In: 2012 IEEE 28th International Conference on Data Engineering (ICDE). IEEE, pp 366–377, 2012
[55] Zhang D, Du Y, Xia T, Tao Y, “Progressive computation of the min-dist optimal-location query,”, In: Proceedings of the 32nd international conference on Very large data bases. VLDB Endowment, pp 643–654, 2006.
[56] Guha S, Khuller S, “Greedy strikes back: Improved facility location algorithms,” Journal of Algorithms, Vol. 31(1), pp 228-248, 1999.
[57] Korupolu MR, Plaxton CG, Rajaraman R, “Analysis of a local search heuristic for facility location problems,” Journal of Algorithms, Vol. 37(1), pp 146-188, 2000.
[58] Dongxiang Zhang, Chee-Yong Chan, and Kian-Lee Tan, “Processing spatial keyword query as a top-k aggregation query,” in Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval, Gold Coast, Queensland, Australia, July 06 - 11, 2014.
[59] Jiaheng Lu, Ying Lu, and Gao Cong, “Reverse spatial and textual k nearest neighbor search,” in Proceedings of the 2011 ACM SIGMOD International Conference on Management of data, Athens, Greece, June 12 - 16, 2011.
[60] Antonin Guttman, “R-trees: a dynamic index structure for spatial searching,” in Proceedings of the 1984 ACM SIGMOD international conference on Management of data, Boston, Massachusetts, June 18 - 21, 1984.
[61] Farhana M. Choudhury, J. Shane Culpepper, Timos Sellis, and Xin Cao “Maximizing bichromatic reverse spatial and textual k nearest neighbor queries,” PVLDB vol. 9(6), pp. 456-467, 2016.
[62] Akrivi Vlachou, Christos Doulkeridis, Yannis Kotidis, and Kjetil Nørvåg, “Reverse top-k queries,” in Proceedings of 2010 IEEE 26th International Conference on Data Engineering (ICDE 2010), Long Beach, CA, USA, 1-6 March 2010.
[63] R. Fagin, A. Lotem, M. Naor, “Optimal aggregation algorithms for middleware”, J. Comput. Syst. Sci. 66 (4) 614–656, 2003.
[64] G. Das, D. Gunopulos, N. Koudas, D. Tsirogiannis, “Answering top-k queries using views”, VLDB, pp. 451–462, 2006.
[65] I.F. Ilyas, G. Beskales, M.A. Soliman, “A survey of top-k query processing techniques in relational database systems”, ACM Comput. Surv. 40 (4), 2008.
[66] L. G. A. Marian, N. Bruno. “Evaluating top-k Queries Over Web Accesible Sources”, TODS 29(2), 2004.
[67] A. Vlachou, C, Doulkeridis, K. Nørva˚g, and Y. Kotidis, “Identifying the Most Influential Data Objects with Reverse Top-k Queries” , Very Large Data Base Endowment, 2010.
[68] D. Aruna devi, P. Sujatha, “Reverse top-k queries and the most influential products”, ICAESM, 2012.
[69] O. Gkorgkas, A. Vlachou, C. Doulkeridis and K. Nørvåg, “Maximizing Influence of Spatio-Textual Objects Based on Keyword Selection. In Advances in Spatial and Temporal Databases” Volume 9239 of the series Lecture Notes in Computer Science, 2015.
[70] Tomas Mikolov, Kai Chen, Greg Corrado, Jeffrey Dean, “Efficient Estimation of Word Representations in Vector Space”, arXiv preprint arXiv:1301.3781, 2013.
[71] Tomas Mikolov, Kai Chen, Greg Corrado, Ilya Sutskever, Jeffrey Dean, “Distributed Representations of Words and Phrases and their Compositionality”, NIPS, 2013.