臺灣博碩士論文加值系統

由於經濟的蓬勃發展，如何選擇合適的地點來創業或者擴張企業的版圖已經成為了一個重要的議題。在過去，有一些關於地點選擇的問題被提出，在他們的研究中，他們大都採用Reverse Nearest Neighbor (RNN)來做為衡量的標準並找出適合的地點，而我們發現這將會遭遇到一些問題。因此，在這篇論文中我們採用平均距離做為我們的衡量標準並提出一個新的查詢，此查詢我們稱之為k-most suitable locations (k-MSL)。在二維空間的環境之下，給定一個正整數k和三個不同的資料集，它們分別為顧客資料集、現有設施資料集和候選地點資料集，我們的目的即是幫助業者從候選地點資料集中找出k個地點，使得在這k個地點上建立新的設施能夠讓顧客到該企業設施的平均距離降到最低。k-MSL無庸置疑是一個重要的查詢，它不只可以應用在商業或是基地台建設上，在都市規劃方面也有一定程度的貢獻。我們在論文中正式定義了此查詢，並且證明此查詢為一個NP-hard問題。因此，我們先提出了一個貪婪演算法，它可以花費較少的時間來找到近似最佳的答案。除此之外，我們更進一步提出了能夠找到最佳解的演算法，它利用了多個法則來過濾掉不可能成為答案的候選地點，更藉由估算候選地點的中間組合能夠為顧客縮短距離的上限值來有效率的刪減往後不可能成為答案的組合，藉此減少搜尋空間。最後我們提出了一系列的實驗來評測各個演算法，而實驗結果顯示了我們的演算法有較佳的執行效率。

Choosing suitable locations for starting a business or expanding the territory of an existing enterprise is an important issue, and a number of location selection problems have been discussed in the literature. Such studies usually apply the Reverse Nearest Neighbor (RNN) as the criterion for finding suitable locations, but we find this may encounter some problems. Therefore, in this paper, we apply the average distance as our criterion and propose a novel problem called k-most suitable locations (k-MSL). In a two-dimensional spatial environment, given a positive integer k and three datasets, which are customer set, existing facility set and potential location set, we want to help users to select k locations for establishing new facilities such that the average distance between a customer and his nearest facility is minimized. k-MSL is indeed an important query, and can be applied not only in commerce but also in urban planning. We formally define this problem and show that it is NP-hard. First, we propose a greedy-based algorithm which can quickly find an approximate answer. An exact algorithm is then proposed to find the optimal answer. This applies several pruning rules to prune useless potential locations and, by estimating the upper bound of the distance reduction of each intermediate combination, combinations that will not become the answer can be pruned early in the process of the algorithm. Finally, extensive experiments are proposed to evaluate the efficiency of each algorithm, and the results show that our algorithms have better performance.

Chinese Abstract i
Abstract ii
Acknowledgements iii
List of Contents iv
List of Figures vi
List of Tables vii
I. Introduction 1
II. Related work 6
A. Influential location selection problems 7
B. Minimum distance location selection problems 9
C. k-medoid and k-center problems 12
III. Preliminary 12
A. Formal problem definition 12
B. Complexity of the k-MSL problem 15
IV. Finding the k-most suitable locations 15
A. Nearest location circles with the tree topology 16
B. Greedy-based algorithm 16
C. Baseline algorithm 21
D. k-MSL algorithm 24
V. Performance 34
A. Experiments on synthetic datasets 34
B. Experiments on real datasets 39
VI. Extension 42
VII. Conclusions 43
References 43

[1] F. Korn and S. Muthukrishnan, “Influence sets based on reverse nearest neighbor queries, in ACM SIGMOD Record, vol. 29, no. 2. ACM, 2000, pp. 201–212.
[2] F. Korn, S. Muthukrishnan, and D. Srivastava, “Reverse nearest neighbor aggregates over data streams, in Proceedings of the 28th international conference on Very Large Data Bases. VLDB Endowment, 2002, pp. 814–825.
[3] J. Qi, R. Zhang, L. Kulik, D. Lin, and Y. Xue, “The min-dist location selection query, in Data Engineering (ICDE), 2012 IEEE 28th International Conference on. IEEE, 2012, pp. 366–377.
[4] D. Zhang, Y. Du, T. Xia, and Y. Tao, “Progressive computation of the min-dist optimal-location query, in Proceedings of the 32nd international conference on Very large data bases. VLDB Endowment, 2006, pp. 643–654.
[5] Y. Du, D. Zhang, and T. Xia, “The optimal-location query, in Advances in Spatial and Temporal Databases. Springer, 2005, pp. 163–180.
[6] T. Xia, D. Zhang, E. Kanoulas, and Y. Du, “On computing top-t most influential spatial sites, in Proceedings of the 31st international conference on Very large data bases. VLDB Endowment, 2005, pp. 946–957.
[7] R. C.-W. Wong, M. T. Ozsu, P. S. Yu, A. W.-C. Fu, and L. Liu, “Efficient method for maximizing bichromatic reverse nearest neighbor, Proceedings of the VLDB Endowment, vol. 2, no. 1, pp. 1126–1137, 2009.
[8] D. Yan, R. C.-W. Wong, and W. Ng, “Efficient methods for finding influential locations with adaptive grids, in Proceedings of the 20th ACM international conference on Information and knowledge management. ACM, 2011, pp. 1475–1484.
[9] R. C.-W. Wong, M. T. Ozsu, A. W.-C. Fu, P. S. Yu, L. Liu, and Y. Liu, “Maximizing bichromatic reverse nearest neighbor for lp-norm in two-and three-dimensional spaces, The VLDB JournalaA?TˇThe International Journal on Very Large Data Bases, vol. 20, no. 6, pp. 893–919, 2011.
[10] P. Ghaemi, K. Shahabi, J. P. Wilson, and F. Banaei-Kashani, “Optimal network location queries, in Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM, 2010, pp. 478–481.
[11] Z. Zhou, W. Wu, X. Li, M. L. Lee, and W. Hsu, “Maxfirst for maxbrknn, in Data Engineering (ICDE), 2011 IEEE 27th International Conference on. IEEE, 2011, pp. 828–839.
[12] K. Zheng, Z. Huang, A. Zhou, and X. Zhou, “Discovering the most influential sites over uncertain data: A rank-based approach, Knowledge and Data Engineering, IEEE Transactions on, vol. 24, no. 12, pp. 2156–2169, 2012.
[13] S. Shang, B. Yuan, K. Deng, K. Xie, and X. Zhou, “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, 2011, pp. 181–190.
[14] J. Huang, Z. Wen, J. Qi, R. Zhang, J. Chen, and Z. He, “Top-k most influential locations selection, in Proceedings of the 20th ACM international conference on Information and knowledge management. ACM, 2011, pp. 2377–2380.
[15] J. Chen, J. Huang, Z. Wen, Z. He, K. Taylor, and R. Zhang, “Analysis and evaluation of the top-k most influential location selection query, Knowledge and Information Systems, vol. 43, no. 1, pp. 181–217, 2015.
[16] J. Qi, R. Zhang, Y. Wang, A. Y. Xue, G. Yu, and L. Kulik, “The min-dist location selection and facility replacement queries, World Wide Web, vol. 17, no. 6, pp. 1261–1293, 2014.
[17] X. Xiao, B. Yao, and F. Li, “Optimal location queries in road network databases, in Data Engineering (ICDE), 2011 IEEE 27th International Conference on. IEEE, 2011, pp. 804–815.
[18] K. Mouratidis, D. Papadias, and S. Papadimitriou, “Medoid queries in large spatial databases, in Advances in Spatial and Temporal Databases. Springer, 2005, pp. 55–72.
[19] ——, “Tree-based partition querying: a methodology for computing medoids in large spatial datasets, The VLDB Journal
- The International Journal on Very Large Data Bases, vol. 17, no. 4, pp. 923–945, 2008. [20] H. Sagan, Space-filling curves. Springer Science ＆ Business Media, 2012.
[21] N. Megiddo and K. J. Supowit, “On the complexity of some common geometric location problems, SIAM journal on computing, vol. 13, no. 1, pp. 182–196, 1984.
[22] H. A. Fayed and A. F. Atiya, “A mixed breadth-depth first strategy for the branch and bound tree of euclidean k-center problems, Computational Optimization and Applications, vol. 54, no. 3, pp. 675–703, 2013.
[23] M. R. Garey and D. S. Johnson, “Computers and intractability: a guide to the theory of np-completeness. 1979, San Francisco, LA: Freeman, 1979.
[24] S. Cabello, J. M. Diaz-Banez, S. Langerman, C. Seara, and I. Ventura, Reverse facility location problems. University of Ljubljana, Inst. of Mathematics, Physics and Mechanics, Department of Mathematics, 2006.
[25] A. Guttman, R-trees: a dynamic index structure for spatial searching. ACM, 1984, vol. 14, no. 2.
[26] “Spatial (geographical) datasets in 2d space north america, 2012, http://chorochronos.datastories.org/.