本文關(guān)鍵詞：在線社交網(wǎng)絡(luò)分布式存儲的數(shù)據(jù)分配算法研究

  更多相關(guān)文章： 社交網(wǎng)絡(luò) 分布式存儲 圖劃分 動態(tài)劃分復(fù)制 存儲受限

【摘要】：自誕生之日起，在線社交網(wǎng)絡(luò)一直保持著快速成長的勢頭，吸引了大量用戶和開發(fā)者、研究學(xué)者。過去十年中，社交網(wǎng)絡(luò)的規(guī)模呈幾何式爆炸增長。隨著用戶數(shù)的進一步增加，單一服務(wù)器已經(jīng)不能滿足當(dāng)代社交網(wǎng)絡(luò)的整體需求，大部分社交網(wǎng)絡(luò)的數(shù)據(jù)信息開始分布式存儲在服務(wù)器集群上。 這些集群節(jié)點相互之間的通信通過網(wǎng)絡(luò)實現(xiàn)，往往需要較高的通信成本和較長的訪問時間。大量的遠程訪問會導(dǎo)致通信網(wǎng)絡(luò)的擁塞，成為整個系統(tǒng)的瓶頸，并且大大延遲訪問時間，降低用戶體驗。如何在有限的、分布的存儲空間內(nèi)高性能存儲和訪問用戶數(shù)據(jù)具有現(xiàn)實意義。 現(xiàn)有研究表明，社交網(wǎng)絡(luò)中大部分交互行為發(fā)生在少部分用戶之間，同時，大部分用戶只與少數(shù)好友交流，具有明顯的社團結(jié)構(gòu)。通過對社交網(wǎng)絡(luò)圖合理劃分，減少不同劃分間的割邊能夠有效減少網(wǎng)絡(luò)通信。然而圖劃分問題是NP完全問題，不存在線性時間內(nèi)的最優(yōu)解。 基于以上觀察，，一些研究學(xué)者根據(jù)社交網(wǎng)絡(luò)的結(jié)構(gòu)特性對現(xiàn)有的圖劃分算法作出改進，具有一定成效。在研究現(xiàn)有社交網(wǎng)絡(luò)圖劃分算法后，本文提出一種基于用戶交互行為的動態(tài)劃分復(fù)制算法，利用用戶之間的朋友關(guān)系和評論行為描述社交網(wǎng)絡(luò)的結(jié)構(gòu)，周期性劃分復(fù)制用戶數(shù)據(jù)，從而提高本地訪問率，降低網(wǎng)絡(luò)負(fù)載。通過真實數(shù)據(jù)集驗證，該算法相比隨機劃分和復(fù)制算法能夠提升本地訪問率，降低訪問延遲。
【關(guān)鍵詞】：社交網(wǎng)絡(luò) 分布式存儲 圖劃分 動態(tài)劃分復(fù)制 存儲受限
【學(xué)位授予單位】：上海交通大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2014
【分類號】：TP333;O157.5
【目錄】：

• 摘要3-5
• ABSTRACT5-7
• 目錄7-10
• 圖錄10-11
• 表錄11-12
• 第一章 緒論12-18
• 1.1 研究背景和意義12-13
• 1.2 國內(nèi)外研究現(xiàn)狀13-15
• 1.2.1 GFS 分布式文件系統(tǒng)和 Bigtable 分布式存儲系統(tǒng)13
• 1.2.2 Cassandra 分散式結(jié)構(gòu)化數(shù)據(jù)存儲系統(tǒng)13-14
• 1.2.3 SPAR 分配復(fù)制算法14
• 1.2.4 WEPAR 分配復(fù)制算法14-15
• 1.3 目前存在的問題15-17
• 1.3.1 社團結(jié)構(gòu)15-16
• 1.3.2 寫操作和存儲限制16-17
• 1.3.3 動態(tài)操作17
• 1.4 研究內(nèi)容及工作17
• 1.5 論文內(nèi)容17-18
• 第二章 相關(guān)理論技術(shù)18-32
• 2.1 圖劃分的相關(guān)定義18-27
• 2.1.1 圖劃分的相關(guān)定義18
• 2.1.2 均衡圖劃分的困難性18-23
• 2.1.3 圖劃分的啟發(fā)式算法23-27
• 2.2 社交網(wǎng)絡(luò)27-30
• 2.2.1 社交網(wǎng)絡(luò)的定義28
• 2.2.2 社交網(wǎng)絡(luò)的拓?fù)涮匦?/span>28-30
• 2.3 分布式數(shù)據(jù)存儲30-31
• 2.4 本章小結(jié)31-32
• 第三章 算法模型及定義32-41
• 3.1 相關(guān)符號及定義32-34
• 3.1.1 主本及副本32
• 3.1.2 讀操作寫操作32
• 3.1.3 關(guān)系社交圖32-33
• 3.1.4 交互社交圖33
• 3.1.5 衰退因子33
• 3.1.6 社交網(wǎng)絡(luò)的圖劃分33-34
• 3.1.7 讀權(quán)重34
• 3.1.8 寫權(quán)重34
• 3.2 需求分析34-35
• 3.2.1 有限的存儲容量34
• 3.2.2 最小化跨節(jié)點操作34
• 3.2.3 負(fù)載平衡34-35
• 3.2.4 高效并且穩(wěn)定的在線操作35
• 3.3 問題抽象35-36
• 3.3.1 最小化跨節(jié)點寫操作35-36
• 3.3.2 最小化跨節(jié)點讀操作36
• 3.4 動態(tài)劃分復(fù)制算法36-40
• 3.4.1 算法描述36-37
• 3.4.2 觸發(fā)事件37-40
• 3.4.3 算法時間復(fù)雜度分析40
• 3.5 本章小結(jié)40-41
• 第四章 社交網(wǎng)絡(luò)的數(shù)據(jù)獲取41-48
• 4.1 實驗流程41-42
• 4.2 數(shù)據(jù)獲取42-45
• 4.2.1 網(wǎng)絡(luò)爬蟲42-44
• 4.2.2 人人網(wǎng)開放平臺 API44-45
• 4.2.3 數(shù)據(jù)爬取45
• 4.3 數(shù)據(jù)清理及歸約45-46
• 4.4 網(wǎng)絡(luò)結(jié)構(gòu)46-47
• 4.5 本章小結(jié)47-48
• 第五章 動態(tài)劃分復(fù)制性能分析48-60
• 5.1 SPAR48-51
• 5.1.1 SPAR 設(shè)計思路48-49
• 5.1.2 SPAR 實驗效果49-50
• 5.1.3 SPAR 的指導(dǎo)意義50-51
• 5.2 實驗設(shè)計51-53
• 5.2.1 數(shù)據(jù)分配51
• 5.2.2 實驗流程51
• 5.2.3 UML 圖51-52
• 5.2.4 評價指標(biāo)52-53
• 5.2.5 對比方法53
• 5.3 實驗結(jié)果53-59
• 5.3.1 本地寫率53-54
• 5.3.2 主本交換率54-55
• 5.3.3 本地讀率55-57
• 5.3.4 響應(yīng)時間57-59
• 5.4 本章小結(jié)59-60
• 第六章 結(jié)束語60-62
• 6.1 論文主要工作60-61
• 6.2 未來工作展望61-62
• 參考文獻62-65
• 致謝65-66
• 攻讀碩士學(xué)位期間已發(fā)表或錄用的論文66-68

【參考文獻】

中國期刊全文數(shù)據(jù)庫 前1條

1 張奎,陳大岳;可滿足性(SAT)問題的概率研究[J];數(shù)學(xué)進展;2001年03期

本文編號：518167