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

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

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

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

【相似文獻】

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

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

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

3 李平華,陸玉麒;可達性研究的回顧與展望[J];地理科學進展;2005年03期

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 劉紅;基于老年人游憩特征的長沙市公園可達性研究[D];湖南師范大學;2015年

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

7 李U

本文編號：940065