請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/61930
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 陳銘憲(Ming-Syan Chen) | |
dc.contributor.author | Chih-Ya Shen | en |
dc.contributor.author | 沈之涯 | zh_TW |
dc.date.accessioned | 2021-06-16T13:19:14Z | - |
dc.date.available | 2016-07-30 | |
dc.date.copyright | 2013-07-30 | |
dc.date.issued | 2013 | |
dc.date.submitted | 2013-07-26 | |
dc.identifier.citation | [1] S. Jex and T. Britt. Organizational Psychology: A Scientist-Practitioner Approach. John
Wiley & Sons, Inc., 2008. [2] A. LaMarca, Y. Chawathe, S. Consolvo, J. Hightower, I. Smith, J. Scott, T. Sohn, J. Howard, J. Hughes, F. Potter, J. Tabert, P. Powledge, G. Borriello, and B. Schilit. Place Lab: Device Positioning Using Radio Beacons in the Wild. Proc. Pervasive, 2005. [3] E. Rukzio, M. Muller, and R. Hardy. Design, Implementation and Evaluation of a Novel Public Display for Pedestrian Navigation: The Rotating Compass. Proc. 27th Int’l Conf. Human Factors in Computing Systems (CHI’09), pp. 113-122, 2009. [4] J. Chung and C. Schmandt. GoingMyWay: A User-Aware Route Planner. Proc. 27th Int’l Conf. Human Factors in Computing Systems (CHI’09), pp. 1899-1902, 2009. [5] A. J. Nicholson and B. D. Noble. BreadCrumbs: Forecasting Mobile Connectivity. Proc. 14th ACMInt’l Conf.Mobile Computing and Networking (MobiCom’08), pp. 46-57, 2008. [6] R. K. Balan, N. Ramasubbu, K. Prakobphol, N. Christin, and J. Hong. mFerio: The Design and Evaluation of a Peer-to-Peer Mobile Payment System. Proc. 7th Int’l Conf. Mobile Systems, Applications, and Services (MobiSys’09), pp. 291-304, 2009. [7] J. Eriksson, L. Girod, B. Hull, R. Newton, S. Madden, and H. Balakrishnan. The Pothole Patrol: Using aMobile Sensor Network for Road SurfaceMonitoring. Proc. 6th Int’l Conf. Mobile Systems, Applications, and Services (MobiSys’08), pp. 29-39, 2008. [8] H. Lu, W. Pan, N. D. Lane, T. Choudhury, and A. T. Campbell, “SoundSense: Scalable Sound Sensing for People-Centric Applications on Mobile Phones. Proc. 7th Int’l Conf. Mobile Systems, Applications, and Services (MobiSys’09), pp. 165-178, 2009. [9] C. Hartung, R. Han, C. Seielstad, and S. Holbrook. FireWxNet: A Multi-Tiered Portable Wireless System forMonitoringWeather Conditions inWildland Fire Environments. Proc. 4th Int’l Conf. Mobile Systems, Applications, and Services (MobiSys’06), pp. 28-41, 2006. [10] P. Volgyesi, G. Balogh, A. Nadas, C. B. Nash, and A. Ledeczi. Shooter Localization and Weapon Classification with Soldier-Wearable Networked Sensors. Proc. 5th Int’l Conf. Mobile Systems, Applications, and Services (MobiSys’07), pp. 113-126, 2007. [11] The Participatory Urban Sensing Projects at UCLA website. http://urban.cens.ucla.edu/projects/. [12] C. Buragohain, D. Agrawal, and S. Suri. Distributed Navigation Algorithms for Sensor Networks. Proc. 25th IEEE Int’l Conf. Computer Communications (INFOCOM’06), pp. 1-10, 2006. [13] Q. Li, M. D. Rosa, and D. Rus. Distributed Algorithm for Guiding Navigation across a Sensor Network. Proc. 9th ACM Int’l Conf. Mobile Computing and Networking (Mobi- Com’03), pp. 313–325, 2003. [14] Y. -C. Tseng, M. -S. Pan, and Y. -Y. Tsai. Wireless Sensor Networks for Emergency Navigation. Computer, vol. 39, pp. 55–62, 2006. [15] M. Li, Y. Liu, J.Wang, and Z. Yang. Sensor Network Navigation without Locations. Proc. 28th IEEE Int’l Conf. Computer Communications (INFOCOM’09), pp. 2419-2427, 2009. [16] I. A.Wagner,M. Lindenbaum, and A.M. Bruckstein. Distributed Covering by Ant-Robots Using Evaporating Traces. IEEE Trans. Robotics Automation, vol. 15, pp. 918-933, 1999. [17] I. A. Wagner, M. Lindenbaum, and A. M. Bruckstein. MAC vs. PC – Determinism and Randomness as Complementary Approaches to Robotic Exploration of Continuous Unknown Domains. Int’l J. Robotics Research, vol. 19, pp. 12-31, 2000. [18] E. Osherovich, V. Yanovki, I. A.Wagner, and A.M. Bruckstein. Robust and Efficient Covering of Unknown Continuous Domains with Simple, Ant-Like Agents. Int’l J. Robotics Research, vol. 27, pp. 815-831, 2008. [19] Y. Elmaliach, N. Agmon, and G. A. Kaminka. Multi-Robot Area Patrol under Frequency Constraints. Proc. IEEE Int’l Conf. Robotics and Automation (ICRA’07), 2007. [20] N. Hazon and G. A. Kaminka. Redundancy, Efficiency and Robustness in Multi-Robot Coverage. Proc. IEEE Int’l Conf. Robotics and Automation (ICRA’05), 2005. [21] J. Melvin, P. Keskinocak, S. Koenig, C. Tovey, and B. Y. Ozkaya. Multi-Robot Routing with Rewards and Disjoint Time Windows. Proc. IEEE Int’l Conf. Intelligent Robots and Systems (IROS’07), 2007. [22] IBM CPLEX Optimizer website. http://www-01.ibm.com/software/integration /optimization/cplex-optimizer/. [23] L. Euler. Solutii Problematis ad Geometriam Situs Pertinentis. Commentarii Academiae Scientiarum Petropolitanae, vol. 8, pp. 128-140, 1736. [24] S. Sahni and T. Gonzalez. P-Complete Approximation Problems. J. ACM, vol. 23, pp. 555-565, 1976. [25] N. Christofides. The Optimum Traversal of a Graph. Int’l J. Management Science, vol. 1, pp. 719-732, 1973. [26] W. Heinzelman, A. Chandrakasan, and H. Balakrishnan. Energy-Efficient Communication Protocol for Wireless Microsensor Networks. Proc. Hawaii Int’l Conf. System Sciences, 2000. [27] A. Manjeshwar and D. P. Agrawal. TEEN: a Routing Protocol for Enhanced Efficiency in Wireless Sensor Networks. Proc. 15th Int’l Parallel and Distributed Processing Symp. Workshops, 2001. [28] S. Lindsey and C. S. Raghavendra. PEGASIS: Power Efficient Gathering in Sensor Information Systems. Proc. IEEE Aerospace Conf., 2002. [29] M. Barthelemy and A. Flammini. Modeling Urban Street Patterns. Physical Review Letters, 100, 138702, 2008. [30] H. N. Gabow. An Efficient Implementation of Edmonds’ Algorithm for MaximumMatching on Graphs. J. ACM, vol. 23, pp. 221-234, 1976. [31] HTC website. http://www.htc.com/. [32] N. Roussopoulos, S. Kelley and F. Vincent. Nearest Neighbor Queries. SIGMOD, 1995. [33] T. Lappas, K. Liu, and E. Terzi. Finding a Team of Experts in Social Networks. KDD, 2009. [34] C.-T. Li and M.-K. Shan. Team Formation for Generalized Tasks in Expertise Social Networks. SocialCom, 2010. [35] M. Sozio and A. Gionis. The Community-Search Problem and How to Plan a Successful Cocktail Party. KDD, 2010. [36] D. Papadias, Q. Shen, Y. Tao and K. Mouratidis. Group Nearest Neighbor Queries. ICDE, 2004. [37] Y. Tao, D. Papadias and Q. Shen. Continuous Nearest Neighbor Search. VLDB, 2002. [38] D.-N. Yang, Y.-L. Chen, W.-C. Lee and M.-S. Chen. On Social-Temporal Group Query with Acquaintance Constraint. VLDB, 2011. [39] Y. Gao, B. Zheng, W.-C. Lee, G. Chen. Continuous Visible Nearest Neighbor Queries. EDBT, 2009. [40] Y. Gao and B. Zheng. Continuous Obstructed Nearest Neighbor Queries in Spatial Databases. SIGMOD, 2009. [41] G. Hjaltason and H. Samet. Distance Browsing in Spatial Databases. TODS, 1999. [42] S. Omohundro. Five balltree construction algorithms. Technical Report, 1989. [43] M. Ye, P. Yin, W.-C. Lee and D.-L. Lee. Exploiting Geographical Influence for Collaborative Point-of-Interest Recommendation. SIGIR, 2011. [44] T. Lappas, K. Liu, and E. Terzi. Finding a Team of Experts in Social Networks. Proc. of KDD, 2009. [45] M. Kargar and A. An. Discovering Top-k Teams of Experts with/without a Leader in Social Networks. Proc. of CIKM, 2011. [46] U. Feige, “A Threshold of ln n for Approximating Set Cover”, J. ACM, 1998. [47] R. Raz, and S. Safra. A Sub-constant Error-probability Low-degree Test, and Sub-constant Error-probability PCP Characterization of NP. Proc. of STOC, 1997. [48] A. Gajewar, and A. Sarma. Multi-skill Collaborative Teams based on Densest Subgraphs. Proc. of SDM, 2012. [49] A. Anagnostopoulos, L. Becchetti, C. Castillo, A. Gionis, and S. Leonardi. Power in Unity: Forming Teams in Large-scale Community Systems. Proc. of CIKM, 2010. [50] L. Qin, J. Yu, L. Chang, and Y. Tao. Querying Communities in Relational Databases. Proc. of ICDE, 2009. [51] Kargar and A. An. Keyword Search in Graphs: Finding r-cliques. Proc. of VLDB, 2011. [52] D. Papadias, Q. Shen, Y. Tao, and K. Mouratidis. Group Nearest Neighbor Queries. Proc. of ICDE, 2004. [53] Y. Gao, B. Zheng,W.-C. Lee, and G. Chen. Continuous Visible Nearest Neighbor Queries. Proc. of EDBT, 2009. [54] G. Hjaltason and H. Samet. Distance Browsing in Spatial Databases. ACM Trans. Database Syst., 1999. [55] E. Dijkstra. A Note on Two Problems in Connexion with Graphs. NumerischeMathematik, 1959. [56] Y. Manolopoulos, A. Nanopoulos, and Y. Theodoridis. R-Trees: Theory and Applications. Springer, 2006. [57] D. Watts and S. Strogatz. Collective Dynamics of ’Small-World’ Networks. Nature 393, 1998. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/61930 | - |
dc.description.abstract | 群體是人類為了滿足需求而自然形成的社會單位,於許多層面,群體能裨益其成員,如增進工作效率、心靈支持與提供安全感。另一方面,隨著具備定位功能的行動裝置與社群網路蓬勃發展,社群與空間資料庫中之群體管理帶來了許多新的應用與挑戰。第一,不同於處理個體的狀況,在群體規劃中,群體中的個體皆須滿足某些需求,並共同滿足規劃上的目標。這個特性使得群體規劃十分複雜。事實上,在本論文中所探討的問題皆為NP-Hard問題;第二,因本論文探討之群體規劃是在社群與空間資料庫中,是故我們需要謹慎處理社群與空間這兩個維度;第三,群體規劃之計算複雜度十分龐大,故需要謹慎設計的演算法與資料結構來妥善處理。
在本論文中,我們首先探討如何在空間資料庫中為群體進行最佳化路徑規劃,以減少其共同涵蓋某個區域的時間。這個問題可適用於搜救與巡邏工作。我們提出一個近似演算法(approximation algorithm)與一個分散式的演算法(distributed algorithm)來處理這個問題。我們透過實地測試(field-trial)與模擬分析來驗證其效能。接著,我們探討如何在社群與空間資料庫中進行群體人員的選擇,以利臨時性社交活動的規劃。我們提出了兩個詢問處理演算法,並提出演算法來迅速地找到最適合的群體。最後,我們探討在社群與空間資料庫中選擇適當的群體成員以利特定工作的進行。我們提出了有效率的處理演算法與資料結構。實驗結果指出,我們提出的演算法大幅勝過其他的演算法。 | zh_TW |
dc.description.abstract | Group is the natural form for gathering individuals for need satisfaction and can benefit its
members from many aspects. On the other hand, with the emergence of GPS-enabled mobile devices and social networks, group management in social and spatial databases brings new challenges and applications. Therefore, in this dissertation, we study different group management problems in social and spatial databases. The challenges faced for group management in social and spatial databases are threefold. First, unlike dealing with single individual, in group management, each selected individual needs to fulfill the requirements and the objective function considers all members in the group. This makes group management problems much more complicated. In fact, the three group management problems studied in this dissertation are all NP-Hard problems. Second, our study considers the group management in social and spatial databases, in which we need to carefully address the interplay between social and spatial domains. Third, the computation needed is much greater than the single individual case, which demands carefully designed data structures and algorithms. In this study, we first look into the route planning for a group of individuals in spatial databases for search and rescue operations. We devise an approximation algorithm for route planning before the search starts, and an algorithm for dynamic adjustments of search routes during the search operation. Field-trial and simulation results demonstrate the superior performance, as compared to other approaches. Then we examine the attendee selection for groups in social and spatial databases, for planning impromptu social activities. We formulate two useful queries for planning activities with social and spatial factors. We propose a framework and several processing strategies for efficiently obtaining the optimal group. Implementations on Facebook and simulations results indicate that our results outperform both human planning and other algorithms. In addition, we also explore the group formations for task accomplishment with social and spatial databases for rescue response teams. We devise efficient processing strategies and perform extensive experiments. The results indicate that our approach outperforms the others on both solution quality and computation time. | en |
dc.description.provenance | Made available in DSpace on 2021-06-16T13:19:14Z (GMT). No. of bitstreams: 1 ntu-102-D96921017-1.pdf: 2247959 bytes, checksum: eaa27473e5399fc663b691802e7f3efb (MD5) Previous issue date: 2013 | en |
dc.description.tableofcontents | 1 Introduction 6
1.1 Motivation and Overview of the Dissertation . . . . . . . . . . . . . . . . . . . 6 1.1.1 Spatial Perspective: Collaborative and Distributed Search System . . . 7 1.1.2 Social and Spatial Perspective: Socio-Spatial Group Query . . . . . . . 7 1.1.3 Social and Spatial with Node Label: Spatio-Social Team Query . . . . 8 1.2 Organization of the Dissertation . . . . . . . . . . . . . . . . . . . . . . . . . 9 2 Spatial Perspective: Collaborative and Distributed Search System 10 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3 Problem Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.4 Algorithm Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.4.1 Split 1-man tour . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.4.2 Assign dangling walks . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.4.3 Performance analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.5 Distributed algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.6 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3 Social and Spatial Perspective: Socio-Spatial Group Query 38 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.3 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.4 Algorithm Design for SSGQ . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.4.1 Distance Ordering . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.4.2 Socio-Spatial Ordering . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.4.3 Distance Pruning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.4.4 Familiarity Pruning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.5 Enhanced Strategy for SSGQ . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.5.1 Social R-Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.5.2 Joint Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.6 Heuristic Algorithms for SSGQ . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.6.1 Heuristic Algorithm Design . . . . . . . . . . . . . . . . . . . . . . . 56 3.7 SSGQ with Multiple Rally Points . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.7.1 Algorithms Design for SSNGQ . . . . . . . . . . . . . . . . . . . . . 61 3.8 Enhanced Strategy for SSNGQ . . . . . . . . . . . . . . . . . . . . . . . . . . 75 3.8.1 Arranging Social Clusters with SC-Tree . . . . . . . . . . . . . . . . . 76 3.8.2 Mega Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 3.9 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 3.9.1 Experiment Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 3.9.2 User Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 3.9.3 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . 81 3.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 4 Social and Spatial with Node Label: Spatio-Social Team Query 88 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 4.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 4.2.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 4.2.2 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 4.2.3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 4.3 Algorithm SkillFirst . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 4.3.1 Feasible Candidate Extraction . . . . . . . . . . . . . . . . . . . . . . 97 4.3.2 Expert Assignment Phase . . . . . . . . . . . . . . . . . . . . . . . . 98 4.3.3 Complete Team Formation Phase . . . . . . . . . . . . . . . . . . . . 101 4.4 Algorithm SpatialFirst . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 4.4.1 Seed Extraction Phase . . . . . . . . . . . . . . . . . . . . . . . . . . 106 4.4.2 Team Construction Phase . . . . . . . . . . . . . . . . . . . . . . . . . 107 4.5 Advanced Strategies for SSTQ . . . . . . . . . . . . . . . . . . . . . . . . . . 110 4.5.1 SK R-Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 4.5.2 Massive Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 4.6 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 4.6.1 Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 4.6.2 Experimental Results on Dataset RescueTeams . . . . . . . . . . . . . 115 4.6.3 Experimental Results on Dataset Foursquare . . . . . . . . . . . . . . 117 4.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 5 Conclusions 122 Appendices 124 A NP-Hardness of k-PSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 B Algorithm design for k-LPSP . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 C Pseudo codes and time complexity analysis for k-PSP . . . . . . . . . . . . . . 131 C.1 Pseudo codes for k-PSP . . . . . . . . . . . . . . . . . . . . . . . . . 131 C.2 Time complexity of algorithm Balanced k Search Walks . . . . . . . . 134 D Pseudo codes and analysis of the proposed algorithm. . . . . . . . . . . . . . . 135 D.1 Pseudo codes for PRP . . . . . . . . . . . . . . . . . . . . . . . . . . 135 D.2 Time complexity of algorithm Moving Edges . . . . . . . . . . . . . . 137 D.3 An example of algorithm Moving Edges . . . . . . . . . . . . . . . . . 138 E Distributed operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 F Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 G Simulation results for different numbers of searchers . . . . . . . . . . . . . . 142 H Comparisons of different frequencies of the distributed operation . . . . . . . 143 I Computation time for the centralized algorithm on mobile devices . . . . . . . 144 J Field-trial results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 | |
dc.language.iso | en | |
dc.title | 於社群與空間資料庫之群體規劃 | zh_TW |
dc.title | Group Management in Social and Spatial Databases | en |
dc.type | Thesis | |
dc.date.schoolyear | 101-2 | |
dc.description.degree | 博士 | |
dc.contributor.oralexamcommittee | 陳良弼(Arbee L.P. Chen),曾新穆(Vincent S. Tseng),李旺謙(Wang-Chien Lee),楊得年(De-Nian Yang),葉彌妍(Mi-Yen Yeh) | |
dc.subject.keyword | 演算法設計與分析,詢問處理,社群網路,近似演算法,索引結構, | zh_TW |
dc.subject.keyword | Algorithm Design and Analysis,Query Processing,Social Networks,Approximation Algorithm,Index Structure, | en |
dc.relation.page | 150 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2013-07-26 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-102-1.pdf 目前未授權公開取用 | 2.2 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。