請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/61930
標題: | 於社群與空間資料庫之群體規劃 Group Management in Social and Spatial Databases |
作者: | Chih-Ya Shen 沈之涯 |
指導教授: | 陳銘憲(Ming-Syan Chen) |
關鍵字: | 演算法設計與分析,詢問處理,社群網路,近似演算法,索引結構, Algorithm Design and Analysis,Query Processing,Social Networks,Approximation Algorithm,Index Structure, |
出版年 : | 2013 |
學位: | 博士 |
摘要: | 群體是人類為了滿足需求而自然形成的社會單位,於許多層面,群體能裨益其成員,如增進工作效率、心靈支持與提供安全感。另一方面,隨著具備定位功能的行動裝置與社群網路蓬勃發展,社群與空間資料庫中之群體管理帶來了許多新的應用與挑戰。第一,不同於處理個體的狀況,在群體規劃中,群體中的個體皆須滿足某些需求,並共同滿足規劃上的目標。這個特性使得群體規劃十分複雜。事實上,在本論文中所探討的問題皆為NP-Hard問題;第二,因本論文探討之群體規劃是在社群與空間資料庫中,是故我們需要謹慎處理社群與空間這兩個維度;第三,群體規劃之計算複雜度十分龐大,故需要謹慎設計的演算法與資料結構來妥善處理。
在本論文中,我們首先探討如何在空間資料庫中為群體進行最佳化路徑規劃,以減少其共同涵蓋某個區域的時間。這個問題可適用於搜救與巡邏工作。我們提出一個近似演算法(approximation algorithm)與一個分散式的演算法(distributed algorithm)來處理這個問題。我們透過實地測試(field-trial)與模擬分析來驗證其效能。接著,我們探討如何在社群與空間資料庫中進行群體人員的選擇,以利臨時性社交活動的規劃。我們提出了兩個詢問處理演算法,並提出演算法來迅速地找到最適合的群體。最後,我們探討在社群與空間資料庫中選擇適當的群體成員以利特定工作的進行。我們提出了有效率的處理演算法與資料結構。實驗結果指出,我們提出的演算法大幅勝過其他的演算法。 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. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/61930 |
全文授權: | 有償授權 |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-102-1.pdf 目前未授權公開取用 | 2.2 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。