近年來，空間資訊分析的議題已經逐漸受到研究者們的重視，因為它可以廣泛的應用到防災、人類行為模式探討，甚至是提昇商業價值的分析上。因此本篇論文提出了一個基於空間資訊分析的商家尋找開設分店地點的新應用。一般來說，一個商家在考量開設分店的地點時，會希望靠近與自己有相似顧客群的其他商店，因為這些商店可以替查詢的店家帶來潛在顧客。另一方面，這個查詢店家也會希望遠離一些特定的業者，避免顧客被這些特定業者搶走。此外，我們也發現到依照查詢店家的開店風格不同，地圖上的每個商店對查詢店家的影響程度並不相同。為了解決上述問題，本篇論文利用了適地性社群網路(location-based social network, LBSN)中的打卡資料與使用者資料計算地圖上的每個商店對查詢店家的影響程度，並依照這些影響程度找出查詢店家的最佳開店位置。此外，由於要計算地圖上每個商店對查詢店家的影響程度可能會花費很多時間，因此本論文總共提出了三個演算法來解決此一問題，包含了一個基礎演算法，以及兩個加速的演算法。最終，實驗結果則驗證了我們所提出方法的有效性。

In recent years, spatial information analysis has become a popular topic among researchers due its wide range of applications in disaster prevention, human behavior pattern exploration, and even analyses to increase commercial value. This study therefore proposed a new application based on spatial information analysis to help businesses look for new branch locations. Generally, when business owners are considering a location for a new branch, they generally want the location to be near other stores with customers that are similar to their own customers, as these stores will help them bring in potential customers. Furthermore, they want the location to be far from other stores that may take away their customers. We also found that the influence of each store on the map on the business owner making the query varies with the style of said business owner. To resolve this issue, we utilized the check-in data and user profiles in a location-based social network (LBSN) to calculate the influence of each store on the map on the business owner making the query and then searched for an optimal new store location based on these influence values. The calculation of these influence values can be time-consuming, so we proposed three algorithms to solve this problem, including a basic algorithm and two acceleration algorithms. Finally, we conducted a series of experiments that demonstrated the validity of the proposed approach.

[1] A. Arvanitis, A. Deligiannakis, and Y. Vassiliou, “Efficient influence-based processing of market research queries,” in Proceedings of the 21st ACM international conference on Information and knowledge management, pp. 1193-1202, 2012.
[2] J. Bao, Y. Zheng, and M. F. Mokbel, “Location-based and preference-aware recommendation using sparse geo-social networking data,” in Proceedings of the 20th International Conference on Advances in Geographic Information Systems, pp. 199-208, 2012.
[3] Z. Chen, Y. Liu, R. C. Wong, J. Xiong, G. Mai, and C. Long, “Efficient algorithms for optimal location queries in road networks,” in Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, pp. 123-134, 2014.
[4] D. M. Endres and J. E. Schindelin, “A new metric for probability distributions,” IEEE Transactions on Information Theory, vol. 49, no. 7, pp. 1858-1860, 2003.
[5] H. Hsieh, C. Li, and S. Lin, “Triprec: Recommending trip routes from large scale check-in data,” in Proceedings of the 21st International Conference on World Wide Web, pp. 529-530, 2012.
[6] H. Huang, “Who can be my joint promotion partners?,” Master thesis of National Cheng-Kung University, 2015.
[7] P. Jaccard, “Etude comparative de la distribution florale dans une portion des alpes et des jura,” Bull Soc Vaudoise Sci Nat, vol. 37, pp. 547-579, 1901.
[8] X. Jin and J. Han, “Expectation maximization clustering,” in Encyclopedia of machine learning and data mining, pp. 480-482, 2017.
[9] S. Kullback and R. A. Leibler, “On information and sufficiency,” The Annals of Mathematical Statistics, vol. 22, no. 1, pp. 79-86, 1951.
[10] C. Lee, “Finding the k-most suitable locations under minimum average distance,” Master thesis of National Cheng-Kung University, 2015.
[11] H. Li, R. Hong, S. Zhu, and Y. Ge, “Point-of-interest recommender systems: A separate-space perspective,” in Proceedings of the 2015 IEEE International Conference on Data Mining, pp. 231-240, 2015.
[12] Y. Lin, E. T. Wang, C. Chiang, and A. L. P. Chen, “Finding targets with the nearest favor neighbor and farthest disfavor neighbor by a skyline query,” in Proceedings of the 29th Annual ACM Symposium on Applied Computing, pp. 821-826, 2014.
[13] E. H. Lu, C. Chen, and V. S. Tseng, “Personalized trip recommendation with multiple constraints by mining user check-in behaviors,” in Proceedings of the 20th International Conference on Advances in Geographic Information Systems, pp. 209-218, 2012.
[14] J. Qi, R. Zhang, L. Kulik, D. Lin, and Y. Xue, “The min-dist location selection query,” in 2012 IEEE 28th International Conference on Data Engineering, pp. 366-377, 2012.
[15] D. Sacharidis and A. Deligiannakis, “Spatial cohesion queries,” in Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 1-10, 2015.
[16] I. Su, Y. Huang, Y. Chung, and I. Shen, “Finding both aggregate nearest positive and farthest negative neighbors,” in Proceedings of the International Conference on Information and Knowledge Engineering (IKE), p. 1, 2012.
[17] X. Wang, Y. Zhang, W. Zhang, and X. Lin, “Distance-aware influence maximization in geo-social network,” in 2016 IEEE 32nd International Conference on Data Engineering (ICDE), pp. 1-12, 2016.
[18] Y. T. Wen, K. J. Cho, W. C. Peng, J. Yeo, and S. W. Hwang, “Kstr: Keyword-aware skyline travel route recommendation,” in 2015 IEEE International Conference on Data Mining, pp. 449-458, 2015.
[19] X. Xiao, B. Yao, and F. Li, “Optimal location queries in road network databases,” in 2011 IEEE 27th International Conference on Data Engineering, pp. 804-815, 2011.
[20] L. Xu, G. Mai, Z. Chen, Y. Liu, and G. Dai, “Minsum based optimal location query in road networks,” in International Conference on Database Systems for Advanced Applications, pp. 441-457, 2017.
[21] J. Zhang, W.-S. Ku, M. Sun, X. Qin, and H. Lu, “Multi-criteria optimal location query with overlapping voronoi diagrams,” in 17th International Conference on Extending Database Technology (EDBT), pp. 391-402, 2014.
[22] R. Zhong, G. Li, K. L. Tan, L. Zhou, and Z. Gong, “G-tree: An efficient and scalable index for spatial search on road networks,” IEEE Transactions on Knowledge and Data Engineering, vol. 27, no. 8, pp. 2175-2189, 2015.
[23] “Facebook,” https://www.facebook.com/.
[24] “Foursquare,” https://foursquare.com/.
[25] “Openstreetmap,” http://www.openstreetmap.org/.
[26] “Real datasets for spatial databases: Road networks and points of interest,” https://www.cs.utah.edu/~lifeifei/SpatialDataset.htm.