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

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

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

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

【參考文獻(xiàn)】

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

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

本文編號(hào)：518167