本文關(guān)鍵詞：大規(guī)模圖中可擴(kuò)展的可達(dá)性查詢高效處理方法研究

  更多相關(guān)文章： 可達(dá)性查詢 遍歷樹 圖劃分 大規(guī)模圖數(shù)據(jù)處理

【摘要】：隨著復(fù)雜多元社交信息網(wǎng)絡(luò)的廣泛應(yīng)用,關(guān)聯(lián)數(shù)據(jù)對(duì)于人們周圍的現(xiàn)實(shí)世界和社交網(wǎng)絡(luò)而言具有越來越重要的地位。如Facebook擁有十億多的用戶。圖,作為一種通用化的數(shù)據(jù)結(jié)構(gòu),對(duì)于表達(dá)復(fù)雜的結(jié)構(gòu)化和半結(jié)構(gòu)化數(shù)據(jù),例如wikipedia,twitter,free-base等社交網(wǎng)絡(luò)數(shù)據(jù),具有重要意義。其中一個(gè)重要應(yīng)用是,如何在一個(gè)給定的大規(guī)模圖中高效地查詢兩個(gè)給定結(jié)點(diǎn)之間是否存在路徑,即可達(dá)性查詢處理。然而隨著圖數(shù)據(jù)的持續(xù)爆炸式增長(zhǎng),傳統(tǒng)方法由于存儲(chǔ)和時(shí)間局限性,很大程度上限制了它們?cè)诖笠?guī)模圖數(shù)據(jù)中的應(yīng)用。因此,如何保證在擁有緊湊存儲(chǔ)結(jié)構(gòu)的前提下,以更高效的時(shí)間解決大規(guī)模圖數(shù)據(jù)可達(dá)性問題,依然具有極大挑戰(zhàn)性。基于遍歷樹圖劃分和連續(xù)重編碼的索引策略Interval-Index,提出了一種擁有緊湊存儲(chǔ)結(jié)構(gòu)且能保證高效查詢效率的大規(guī)模圖索引。Interval-Index索引技術(shù)通過圖劃分提高了圖處理的局部性和并行性,并在劃分基礎(chǔ)上對(duì)大規(guī)模圖數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)進(jìn)行設(shè)計(jì),確保索引結(jié)構(gòu)具有較高壓縮比。為了提高數(shù)據(jù)訪問的順序性,方便建立高效索引,Interval-Index對(duì)每一個(gè)遍歷樹分區(qū)進(jìn)行連續(xù)重編碼。同時(shí)重編碼策略使得后續(xù)基于變長(zhǎng)字節(jié)的鄰接表壓縮具有更高的壓縮效率。利用基于遍歷樹生成圖的索引結(jié)構(gòu),可以通過二分查找實(shí)現(xiàn)對(duì)結(jié)點(diǎn)快速定位,提高了查詢處理速率。此外,Interval-Index采用mmap虛擬內(nèi)存技術(shù)實(shí)現(xiàn)對(duì)數(shù)據(jù)的按需調(diào)入,提高了內(nèi)存利用率和數(shù)據(jù)載入效率。通過對(duì)多種真實(shí)圖和合成圖在可達(dá)性查詢處理上的存儲(chǔ)性能和速度性能方面的測(cè)試。Interval-Index方法在存儲(chǔ)空間上比Feline至少降低了23%,在查詢處理時(shí)間上比Feline至降低了20%。實(shí)驗(yàn)表明,隨著數(shù)據(jù)集大小的增長(zhǎng),Interval-Index在存儲(chǔ)空間和查詢處理時(shí)間上都大致呈亞線性增長(zhǎng);相對(duì)而言,Feline的擴(kuò)展性則較差,尤其是在查詢處理時(shí)間方面相當(dāng)遜色于Interval-Index。
【關(guān)鍵詞】：可達(dá)性查詢 遍歷樹 圖劃分 大規(guī)模圖數(shù)據(jù)處理
【學(xué)位授予單位】：華中科技大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：O157.5
【目錄】：

• 摘要4-5
• Abstract5-9
• 1 緒論9-20
• 1.1 問題提出9-10
• 1.2 國內(nèi)外研究現(xiàn)狀10-18
• 1.3 研究?jī)?nèi)容18-19
• 1.4 文章框架結(jié)構(gòu)19-20
• 2 大規(guī)模圖數(shù)據(jù)可達(dá)性索引Interval-Index總體設(shè)計(jì)20-27
• 2.1 相關(guān)定義20-23
• 2.2 Interval-Index整體設(shè)計(jì)思路23-25
• 2.3 Interval-Index處理流程25-26
• 2.4 本章小結(jié)26-27
• 3 基于遍歷樹劃分的可達(dá)性索引Interval-Index27-44
• 3.1 基于遍歷樹的圖劃分27-35
• 3.2 重編碼遍歷樹35-37
• 3.3 Interval-Index索引構(gòu)建37-40
• 3.4 鄰接表壓縮存儲(chǔ)40-42
• 3.5 結(jié)點(diǎn)的快速定位42
• 3.6 本章小結(jié)42-44
• 4 實(shí)驗(yàn)與分析44-52
• 4.1 測(cè)試環(huán)境44
• 4.2 測(cè)試數(shù)據(jù)集與測(cè)試方法44-46
• 4.3 性能測(cè)試46-49
• 4.4 擴(kuò)展性能測(cè)試49-50
• 4.5 分析與總結(jié)50
• 4.6 本章小結(jié)50-52
• 5 總結(jié)與展望52-54
• 致謝54-56
• 參考文獻(xiàn)56-60
• 附錄1 攻讀學(xué)位期間被錄用的期刊論文60-61
• 附錄2 攻讀學(xué)位期間申請(qǐng)的軟件著作版權(quán)61

【相似文獻(xiàn)】

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

1 林宗振;;關(guān)于均勻錢幣投擲過程的可達(dá)性[J];暨南理醫(yī)學(xué)報(bào)(理科專版);1985年03期

2 許世蒙,張玉忠;有交易費(fèi)的折算資產(chǎn)優(yōu)化性質(zhì)和可達(dá)性[J];控制理論與應(yīng)用;2002年01期

3 李平華,陸玉麒;可達(dá)性研究的回顧與展望[J];地理科學(xué)進(jìn)展;2005年03期

4 賈鵬;劉瑞菊;楊忠振;;基于陸域和空域運(yùn)輸系統(tǒng)的空港可達(dá)性評(píng)價(jià)方法研究[J];經(jīng)濟(jì)地理;2013年06期

5 姜海寧;譚石柳;;軌道交通建設(shè)對(duì)金華城鎮(zhèn)可達(dá)性格局的影響[J];浙江師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2014年02期

6 劉俊;陸玉麒;;江蘇省公路交通網(wǎng)絡(luò)可達(dá)性評(píng)價(jià)研究[J];南京師大學(xué)報(bào)(自然科學(xué)版);2008年03期

7 劉志林;王茂軍;;北京市職住空間錯(cuò)位對(duì)居民通勤行為的影響分析——基于就業(yè)可達(dá)性與通勤時(shí)間的討論[J];地理學(xué)報(bào);2011年04期

8 蔣曉威;曹衛(wèi)東;羅健;朱勝清;唐云云;;安徽省公路網(wǎng)絡(luò)可達(dá)性空間格局及其演化[J];地理科學(xué)進(jìn)展;2012年12期

9 劉俊;陸玉麒;孟德友;;基于不同指標(biāo)的公路交通網(wǎng)絡(luò)可達(dá)性評(píng)價(jià)——以江蘇省為例[J];工業(yè)技術(shù)經(jīng)濟(jì);2009年02期

10 袁立科;張宗益;;創(chuàng)新系統(tǒng)的區(qū)域可達(dá)性研究[J];科研管理;2007年01期

中國重要會(huì)議論文全文數(shù)據(jù)庫 前10條

1 苗梅;Gerhard Weber;;推廣可達(dá)性[A];第四屆和諧人機(jī)環(huán)境聯(lián)合學(xué)術(shù)會(huì)議論文集[C];2008年

2 呂斌;張純;陳天鳴;;城市低收入群體的就業(yè)可達(dá)性變化研究:以北京為例[A];多元與包容——2012中國城市規(guī)劃年會(huì)論文集(13.城市規(guī)劃管理)[C];2012年

3 裴玉龍;蓋春英;;公路網(wǎng)絡(luò)可達(dá)性研究[A];科技、工程與經(jīng)濟(jì)社會(huì)協(xié)調(diào)發(fā)展——中國科協(xié)第五屆青年學(xué)術(shù)年會(huì)論文集[C];2004年

4 尹海偉;徐建剛;祁毅;;上海公園空間可達(dá)性與公平性分析[A];中國地理學(xué)會(huì)2007年學(xué)術(shù)年會(huì)論文摘要集[C];2007年

5 張莉;陸玉麒;趙元正;;基于可達(dá)性的長(zhǎng)江三角洲城市一日交流圈的動(dòng)態(tài)變化研究[A];地理學(xué)核心問題與主線——中國地理學(xué)會(huì)2011年學(xué)術(shù)年會(huì)暨中國科學(xué)院新疆生態(tài)與地理研究所建所五十年慶典論文摘要集[C];2011年

6 孟德友;范況生;高超;;鐵路客運(yùn)提速前后省際可達(dá)性及空間格局分析[A];中國地理學(xué)會(huì)百年慶典學(xué)術(shù)論文摘要集[C];2009年

7 劉志林;王茂軍;;北京市職住空間錯(cuò)位對(duì)居民通勤行為的影響分析——基于就業(yè)可達(dá)性與通勤時(shí)間的討論[A];中國地理學(xué)會(huì)百年慶典學(xué)術(shù)論文摘要集[C];2009年

8 張宇;張英杰;張曉東;鄭猛;;北京市區(qū)位可達(dá)性對(duì)房?jī)r(jià)影響分析[A];規(guī)劃創(chuàng)新：2010中國城市規(guī)劃年會(huì)論文集[C];2010年

9 朱琛;孫姍珊;;城市不同居住區(qū)位群體就業(yè)可達(dá)性差異研究——以上海市為例[A];城市時(shí)代，，協(xié)同規(guī)劃——2013中國城市規(guī)劃年會(huì)論文集（07-居住區(qū)規(guī)劃與房地產(chǎn)）[C];2013年

10 楊育軍;;可達(dá)性評(píng)價(jià)方法的比較:一種基于GIS的實(shí)證方法[A];中國地理信息系統(tǒng)協(xié)會(huì)第八屆年會(huì)論文集[C];2004年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 丁振;既有路網(wǎng)下基于中小城市的快速通道網(wǎng)布局研究[D];西南交通大學(xué);2015年

2 彭\~\~;基于區(qū)間標(biāo)記索引的可達(dá)性查詢?cè)O(shè)計(jì)及其在外包數(shù)據(jù)庫中的應(yīng)用[D];哈爾濱工業(yè)大學(xué);2014年

3 薛鵬;圖數(shù)據(jù)上可達(dá)性查詢關(guān)鍵技術(shù)研究[D];東北大學(xué);2014年

4 李建新;基于可達(dá)性的南昌市區(qū)域空間效應(yīng)研究[D];江西師范大學(xué);2015年

5 劉紅;基于老年人游憩特征的長(zhǎng)沙市公園可達(dá)性研究[D];湖南師范大學(xué);2015年

6 王于楠;基于公路可達(dá)性的青海省人口時(shí)空格局演變研究[D];青海師范大學(xué);2016年

7 李U

本文編號(hào)：940065