臺灣博碩士論文加值系統

給定一個有n個使用者的集合U={u1,u2,…,un}及ň個地緣空間中的查詢點座標P={p1,p2,…pň}，r個關鍵字的集合W={w1,w2,…,wr}。每一個查詢點會結合(涵蓋)部分的關鍵字，使用者如果在某個空間查詢點打卡(他就會坐落在這個座標位置)，就可以計算使用者對此空間中的每個關鍵字的興趣值，我們用I(u,w)來表示使用者v對關鍵字w的興趣值。I(u,W)= ∑w∈W I(u,w)定義為使用者對每個在關鍵字集合W內的關鍵字的興趣值加總。地緣感知興趣群組查詢(SIGQ)定義為找到一個有c個使用者集合Uc，1≤ c≤ n，可以查詢(涵蓋)到所有W內的關鍵字。給定一個SIGQ Uc，一個小數α，0≤α≤1，Rankα(Uc)= α*min{I(u,W)| v∈ Uc}-(1-α)D(Uc)。D(Uc)為使用者集合Uc的直徑(diameter)，即為Uc中任兩個使用者所座落的位置中最遠的(歐式)距離。地緣感知興趣群組查詢問題(SIGQP)是要找到一個SIGQ U*c，使得Rankα(U*c)的值要最大。而地緣感興趣群組查詢問題(SIGQP)已經被證明為是NP-Complete。本研究首先針對此問題設計一個整數規劃 (Integer programming algorithm) 的正確演算法來取得最佳解，另外並設計了線性鬆弛演算法 A、B(Linear Programming relaxation)來加快整體執行的時間。實驗結果顯示當 α=1 時線性鬆弛演算法 A 所得的解與最佳解相除的(所得的解除以最佳解)倍率大約為 0.9905~1，α=0.5的倍率約為 0.3439~0.7927，α=0 的倍率約為 1.3309~ 5.2755。 當 α=1 線性鬆弛演算法 B 的倍率 0.3887~0.5206， α=0.5的倍率約為-0.6150 ~0.0946，α=0的倍率約 為 1.4943~6.8661。線性鬆弛演算法 A 執行時間 平均為 0.0781~0.0792(s)，線性鬆弛演算法 B執行 時間平均為 0.0781~0.0792(s)。而根據此研究的結果，整數規劃演算法可以取得最佳解，但如果考慮時間因素的話，尤其當 α>0.5 時，線性鬆弛演算法 A 具有不錯的倍率，且速度比整數規劃來得更快。

Given a set of n users U={u1,u2,…,un} and ň query point coordinates in geographic space P={p1,p2,…pň}, a set of r keywords W={w1,w2,…,wr}.Each query point will contain(cover) part of the keywords. If the user checks in a certain space query point(he will be located at this coordinate position), Then the user’s interest value for each keyword in this space can be calculated. We represent I(u,w) as the user v’s interest value for the keyword set of W. I(u,W)= ∑w∈W I(u,w) is defined as the sum of the user’s interest in each keyword in the keywords set W. Spatial-Aware Interest Group Query (SIGQ) is defined as finding a set of c users represented as Uc, 1≤ c≤ n , which can query (cover) all keywords in W. Given a SIGQ Uc , and a α , 0≤α≤1 , Rankα(Uc)= α*min{I(u,W)| v∈ Uc}-(1-α)D(Uc). D(Uc) is the diameter of the user set Uc, that is the farthest distance where any two users are seated in Uc. Spatial-Aware Interest Group Query Problem (SIGQP) is to find a SIGQ U*c such that the value of Rankα(U*c) is maximum. Spatial-Aware Interest Group Query Problem (SIGQP) has been proven to be NP-Complete. This research designs a exact integer programming algorithm for this problem to obtain the best solution, and linear programming relaxation technologies to accelerate its execution time. The experimental results show that when α = 1, the magnification of the solution obtained by linear relaxation algorithm A divided by the best solution is about 0.9905~1, and the magnification of α = 0.5 is about 0.3439~0.7927.The magnification of α = 0 is about 1.3309~5.2755. When α = 1, the magnification of linear relaxation algorithm B is 0.3887~0.5206, the magnification of α = 0.5 is about -0.6150~0.0946, and the magnification of α = 0 is about 1.4943~6.8661.

謝誌 I
摘要 III
Abstract V
目錄 VII
表次 IX
圖次 XI
第一章 緒論 1
第一節 研究背景與動機 1
第二節 研究問題 2
第三節 研究目的與應用 4
第四節 論文架構 4
第二章 文獻探討 5
第一節 地緣關鍵字查詢 (Spatial keyword query) 5
第二節 地緣社交群組查詢 (Geo-Social Group Queries，GSGQ) 7
第三節 基於位置的社交網路(Location-Based Social Network) 9
第四節 整數規劃與線性規劃 10
第五節 集合涵蓋問題 (Set cover problem) 13
第三章 研究方法 15
第一節 整數規劃演算法 16
第二節 線性規劃鬆弛演算法 18
第四章 研究結果與討論 21
第五章 結論 29
參考文獻 31

[1] L. Backstrom, D. Huttenlocher, J. Kleinberg, and X. Lan, "Group formation in large social networks: membership, growth, and evolution," in Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, 2006, pp. 44-54.
[2] X. Cao et al., "Spatial keyword querying," in International Conference on Conceptual Modeling, 2012: Springer, pp. 16-29.
[3] A. Cary, O. Wolfson, and N. Rishe, "Efficient and scalable method for processing top-k spatial boolean queries," in International Conference on Scientific and Statistical Database Management, 2010: Springer, pp. 87-95.
[4] S.-J. Chen and L. Lin, "Modeling team member characteristics for the formation of a multifunctional team in concurrent engineering," IEEE Transactions on Engineering Management, vol. 51, no. 2, pp. 111-124, 2004.
[5] E. Cho, S. A. Myers, and J. Leskovec, "Friendship and mobility: user movement in location-based social networks," in Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, 2011, pp. 1082-1090.
[6] G. Cong, C. S. Jensen, and D. Wu, "Efficient retrieval of the top-k most relevant spatial web objects," Proceedings of the VLDB Endowment, vol. 2, no. 1, pp. 337-348, 2009.
[7] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to algorithms. MIT press, 2009.
[8] G. DANTZIG, "Linear programming and extensions.[Sl]: Princeton," New Jersey, 1963.
[9] I. De Felipe, V. Hristidis, and N. Rishe, "Keyword search on spatial databases," in 2008 IEEE 24th International Conference on Data Engineering, 2008: IEEE, pp. 656-665.
[10] Y. Doytsher, B. Galon, and Y. Kanza, "Querying geo-social data by bridging spatial networks and social networks," in Proceedings of the 2nd ACM SIGSPATIAL International Workshop on Location Based Social Networks, 2010, pp. 39-46.
[11] N. Garg, G. Konjevod, and R. Ravi, "A polylogarithmic approximation algorithm for the group Steiner tree problem," Journal of Algorithms, vol. 37, no. 1, pp. 66-84, 2000.
[12] R. E. Gomory, "Outline of an algorithm for integer solutions to linear programs and an algorithm for the mixed integer problem," in 50 Years of Integer Programming 1958-2008: Springer, 2010, pp. 77-103.
[13] R. Hariharan, B. Hore, C. Li, and S. Mehrotra, "Processing spatial-keyword (SK) queries in geographic information retrieval (GIR) systems," in 19th International Conference on Scientific and Statistical Database Management (SSDBM 2007), 2007: IEEE, pp. 16-16.
[14] C.-Y. Huang, P.-C. Chien, and Y. H. Chen, "Exact and Heuristic Algorithms for Some Spatial-aware Interest Group Query Problems," Journal of Internet Technology, vol. 21, no. 4, pp. 1199-1205, 2020.
[15] W. Huang, G. Li, K.-L. Tan, and J. Feng, "Efficient safe-region construction for moving top-k spatial keyword queries," in Proceedings of the 21st ACM international conference on Information and knowledge management, 2012, pp. 932-941.
[16] N. Karmarkar, "A new polynomial-time algorithm for linear programming," in Proceedings of the sixteenth annual ACM symposium on Theory of computing, 1984, pp. 302-311.
[17] R. M. Karp, "Reducibility among combinatorial problems," in Complexity of computer computations: Springer, 1972, pp. 85-103.
[18] T. Lappas, K. Liu, and E. Terzi, "Finding a team of experts in social networks," in Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, 2009, pp. 467-476.
[19] C.-T. Li and M.-K. Shan, "Team formation for generalized tasks in expertise social networks," in 2010 IEEE second international conference on social computing, 2010: IEEE, pp. 9-16.
[20] G. Li, J. Feng, and J. Xu, "Desks: Direction-aware spatial keyword search," in 2012 IEEE 28th International Conference on Data Engineering, 2012: IEEE, pp. 474-485.
[21] N. Li and G. Chen, "Analysis of a location-based social network," in 2009 international conference on computational science and engineering, 2009, vol. 4: Ieee, pp. 263-270.
[22] Y. Li, R. Chen, J. Xu, Q. Huang, H. Hu, and B. Choi, "Geo-social k-cover group queries for collaborative spatial computing," IEEE Transactions on Knowledge and Data Engineering, vol. 27, no. 10, pp. 2729-2742, 2015.
[23] Y. Li, D. Wu, J. Xu, B. Choi, and W. Su, "Spatial-aware interest group queries in location-based social networks," Data & Knowledge Engineering, vol. 92, pp. 20-38, 2014.
[24] Z. Li, K. C. Lee, B. Zheng, W.-C. Lee, D. Lee, and X. Wang, "Ir-tree: An efficient index for geographic document search," IEEE transactions on knowledge and data engineering, vol. 23, no. 4, pp. 585-599, 2010.
[25] W. Liu, W. Sun, C. Chen, Y. Huang, Y. Jing, and K. Chen, "Circle of friend query in geo-social networks," in International Conference on Database Systems for Advanced Applications, 2012: Springer, pp. 126-137.
[26] J. Lu, Y. Lu, and G. Cong, "Reverse spatial and textual k nearest neighbor search," in Proceedings of the 2011 ACM SIGMOD International Conference on Management of data, 2011, pp. 349-360.
[27] D. G. Luenberger and Y. Ye, Linear and nonlinear programming. Springer, 1984.
[28] J. B. Rocha-Junior, O. Gkorgkas, S. Jonassen, and K. Nørvåg, "Efficient processing of top-k spatial keyword queries," in International Symposium on Spatial and Temporal Databases, 2011: Springer, pp. 205-222.
[29] O. Roick and S. Heuser, "Location Based Social Networks – Definition, Current State of the Art and Research Agenda," Transactions in GIS, vol. 17, no. 5, pp. 763-784, 2013.
[30] C.-Y. Shen, D.-N. Yang, L.-H. Huang, W.-C. Lee, and M.-S. Chen, "Socio-spatial group queries for impromptu activity planning," IEEE Transactions on Knowledge and Data Engineering, vol. 28, no. 1, pp. 196-210, 2015.
[31] D. Wu, G. Cong, and C. S. Jensen, "A framework for efficient spatial web object retrieval," The VLDB Journal, vol. 21, no. 6, pp. 797-822, 2012.
[32] D. Wu, M. L. Yiu, C. S. Jensen, and G. Cong, "Efficient continuously moving top-k spatial keyword query processing," in 2011 IEEE 27th International Conference on Data Engineering, 2011: IEEE, pp. 541-552.
[33] D.-N. Yang, Y.-L. Chen, W.-C. Lee, and M.-S. Chen, "On social-temporal group query with acquaintance constraint," arXiv preprint arXiv:1104.3219, 2011.
[34] D.-N. Yang, C.-Y. Shen, W.-C. Lee, and M.-S. Chen, "On socio-spatial group query for location-based social networks," in Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, 2012, pp. 949-957.
[35] D. Zhang, Y. M. Chee, A. Mondal, A. K. Tung, and M. Kitsuregawa, "Keyword search in spatial databases: Towards searching by document," in 2009 IEEE 25th International Conference on Data Engineering, 2009: IEEE, pp. 688-699.
[36] D. Zhang, B. C. Ooi, and A. K. Tung, "Locating mapped resources in web 2.0," in 2010 IEEE 26th International Conference on Data Engineering (ICDE 2010), 2010: IEEE, pp. 521-532.
[37] Y. Zheng, "Location-based social networks: Users," in Computing with spatial trajectories: Springer, 2011, pp. 243-276.
[38] Y. Zhou, X. Xie, C. Wang, Y. Gong, and W.-Y. Ma, "Hybrid index structures for location-based web search," in Proceedings of the 14th ACM international conference on Information and knowledge management, 2005, pp. 155-162.
[39] Q. Zhu, H. Hu, C. Xu, J. Xu, and W.-C. Lee, "Geo-social group queries with minimum acquaintance constraints," The VLDB Journal, vol. 26, no. 5, pp. 709-727, 2017.
[40] A. Zzkarian and A. Kusiak, "Forming teams: an analytical approach," IIE transactions, vol. 31, no. 1, pp. 85-97, 1999.