本文關(guān)鍵詞：圖數(shù)據(jù)搜索引擎Trinity中正則表達式匹配子系統(tǒng)的設(shè)計與實現(xiàn)

  更多相關(guān)文章： 圖數(shù)據(jù) 圖模式匹配 正則表達式 分布式算法 查詢優(yōu)化

【摘要】：在許多大規(guī)模圖數(shù)據(jù)的應(yīng)用領(lǐng)域當中,找出圖中路徑上節(jié)點之間滿足的某種限制是非常有必要的。利用正則表達式強大的描述序列模式的能力,本文中,定義圖模式匹配的一種特殊形式:正則表達式在大規(guī)模圖上的查詢匹配。在這個查詢中,用正則表達式表示節(jié)點之間所滿足的限制。本文的研究將有利于查找圖中滿足某種限制的路徑,只要這種路徑可以用正則表達式表示。本課題是基于微軟亞洲研究院分布式圖引擎Trinity,Trinity是一個分布式大規(guī)模圖處理引擎,從底層支持強類型的隨機存儲和通用計算,在大規(guī)模集群上,分布式的隨機存儲提供全局地址和高效的鍵值存儲,通過隨機存儲,Trinity保證了在大規(guī)模分布式的數(shù)據(jù)集上對數(shù)據(jù)進行高效的隨機訪問。本論文研究內(nèi)容包括對正則表達式的處理、圖的生成器的研究、查詢優(yōu)化算法、分布式匹配算法的設(shè)計與實現(xiàn)。通過對yacc的分析,實現(xiàn)了對正則表達式的處理,處理后的形式能很好的適應(yīng)分布式環(huán)境。處理后的形式更容易在圖上進行匹配。通過對Power Low類型的圖的研究實現(xiàn)了圖生成器。依靠圖生成器,實現(xiàn)了手工建造大規(guī)模圖數(shù)據(jù)。通過對查詢優(yōu)化模型的構(gòu)建實現(xiàn)了基于代價估計的查詢優(yōu)化方法,依靠此優(yōu)化方法大幅提高了系統(tǒng)運行效率。通過對物理操作的實現(xiàn),完成了大規(guī)模集群環(huán)境下的分布式算法,依靠這些分布式匹配算法,完成了圖上的模式匹配。實驗數(shù)據(jù)證明,本論文中的正則表達式匹配已經(jīng)滿足了實時查詢的需要。
【關(guān)鍵詞】：圖數(shù)據(jù) 圖模式匹配 正則表達式 分布式算法 查詢優(yōu)化
【學位授予單位】：哈爾濱工業(yè)大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：TP311.13
【目錄】：

• 摘要4-5
• ABSTRACT5-9
• 第1章 緒論9-15
• 1.1 課題背景及研究的目的和意義9
• 1.2 國內(nèi)外研究現(xiàn)狀分析9-13
• 1.2.1 正則表達式對于數(shù)據(jù)抽象的研究9-10
• 1.2.2 圖數(shù)據(jù)的研究現(xiàn)狀10-13
• 1.3 本論文主要研究內(nèi)容和結(jié)構(gòu)13-15
• 1.3.1 本論文主要研究內(nèi)容13-14
• 1.3.2 論文的結(jié)構(gòu)14-15
• 第2章 正則表達式匹配系統(tǒng)需求分析與總體設(shè)計15-26
• 2.1 系統(tǒng)工作流程分析15-20
• 2.2 功能需求分析20-23
• 2.2.1 正則表達式處理需求分析20-21
• 2.2.2 數(shù)據(jù)生成需求分析21
• 2.2.3 數(shù)據(jù)提取需求分析21-22
• 2.2.4 索引構(gòu)建需求分析22
• 2.2.5 正則表達式匹配需求分析22
• 2.2.6 查詢優(yōu)化需求分析22-23
• 2.2.7 結(jié)果提取需求分析23
• 2.3 非功能性需求分析23
• 2.4 系統(tǒng)總體設(shè)計23-25
• 2.5 本章小結(jié)25-26
• 第3章 正則表達式匹配系統(tǒng)詳細設(shè)計26-51
• 3.1 正則表達式處理26-32
• 3.1.1 構(gòu)建分析結(jié)構(gòu)27-28
• 3.1.2 數(shù)據(jù)預(yù)處理28-29
• 3.1.3 數(shù)據(jù)轉(zhuǎn)化29-31
• 3.1.4 分析提取31-32
• 3.2 數(shù)據(jù)生成32-38
• 3.2.1 改進的Rmat算法33-34
• 3.2.2 分布式數(shù)據(jù)生成34-38
• 3.3 數(shù)據(jù)提取38-40
• 3.3.1 數(shù)據(jù)預(yù)處理38-39
• 3.3.2 生成數(shù)據(jù)模型39-40
• 3.3.3 數(shù)據(jù)轉(zhuǎn)化40
• 3.4 索引構(gòu)建40-42
• 3.4.1 構(gòu)建索引模型40-41
• 3.4.2 數(shù)據(jù)模型訓練41-42
• 3.5 正則表達式匹配42-45
• 3.5.1 非閉包匹配算法42-44
• 3.5.2 閉包匹配算法44-45
• 3.5.3 算法復雜度分析45
• 3.6 查詢優(yōu)化45-48
• 3.6.1 代價估計模型構(gòu)建46-47
• 3.6.2 動態(tài)規(guī)劃算法47-48
• 3.6.3 查詢運行時優(yōu)化48
• 3.7 結(jié)果提取48-50
• 3.7.1 過濾器構(gòu)建49
• 3.7.2 獨立數(shù)據(jù)同步49-50
• 3.7.3 遠程數(shù)據(jù)同步50
• 3.8 本章小結(jié)50-51
• 第4章正則表達式匹配系統(tǒng)的實現(xiàn)51-75
• 4.1 正則表達式處理51-54
• 4.1.1 構(gòu)建分析結(jié)構(gòu)51-52
• 4.1.2 數(shù)據(jù)預(yù)處理52
• 4.1.3 數(shù)據(jù)轉(zhuǎn)化52-54
• 4.1.4 分析提取54
• 4.2 數(shù)據(jù)生成54-60
• 4.3 數(shù)據(jù)提取60-62
• 4.3.1 數(shù)據(jù)預(yù)處理60-61
• 4.3.2 生成數(shù)據(jù)模型61-62
• 4.3.3 數(shù)據(jù)轉(zhuǎn)化62
• 4.4 索引構(gòu)建62-65
• 4.4.1 構(gòu)建索引模型63
• 4.4.2 數(shù)據(jù)模型訓練63-65
• 4.5 正則表達式匹配65-68
• 4.5.1 非閉包算法65-68
• 4.5.2 閉包算法68
• 4.6 查詢優(yōu)化68-71
• 4.6.1 基于代價估計的查詢優(yōu)化69-71
• 4.6.2 系統(tǒng)運行時優(yōu)化71
• 4.7 結(jié)果提取71-74
• 4.7.1 過濾器構(gòu)建71-72
• 4.7.2 獨立數(shù)據(jù)同步72-73
• 4.7.3 遠程數(shù)據(jù)同步73-74
• 4.8 本章小結(jié)74-75
• 第5章 正則表達式匹配系統(tǒng)測試75-90
• 5.1 系統(tǒng)測試內(nèi)容75
• 5.2 表達式處理模塊測試內(nèi)容75-76
• 5.3 數(shù)據(jù)生成模塊測試內(nèi)容76-82
• 5.4 表達式匹配模塊測試內(nèi)容82-87
• 5.5 查詢優(yōu)化模塊測試內(nèi)容87-88
• 5.6 與現(xiàn)有研究成果的對比88
• 5.7 本章小結(jié)88-90
• 結(jié)論90-92
• 參考文獻92-98
• 致謝98-99
• 個人簡歷99

【相似文獻】

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

1 孟巖;;一夫當關(guān)——《精通正則表達式》書評[J];程序員;2007年08期

2 路個的;;請個伙伴,助你成長為正則表達式高手[J];電腦愛好者;2008年23期

3 余晟;;正則表達式隨筆[J];程序員;2008年03期

4 李國晶;王景強;;淺析正則表達式[J];科技資訊;2010年04期

5 馬永萍;;正則表達式及其應(yīng)用[J];電腦編程技巧與維護;2012年04期

6 侯秀紅;董峰;;Visual Basic 6.0中正則表達式的應(yīng)用[J];鄭州輕工業(yè)學院學報;2005年04期

7 楊樹林;;正則表達式在網(wǎng)絡(luò)教學系統(tǒng)中的應(yīng)用[J];北京印刷學院學報;2005年04期

8 黃曉春;孟巖;;理解正則表達式(下)[J];程序員;2007年06期

9 魏蓉;王文忠;仲蘭芬;;正則表達式在現(xiàn)代漢語語法處理中的應(yīng)用[J];陰山學刊(自然科學版);2007年04期

10 李麗莉;李婭;周琪云;;正則表達式在網(wǎng)絡(luò)信息監(jiān)控分析系統(tǒng)中的應(yīng)用[J];信息技術(shù);2008年04期

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

1 管杰裕;;正則表達式在氣象信息處理中的應(yīng)用[A];2005年廣西氣象學會學術(shù)年會論文集[C];2005年

2 劉琪;牛文靜;;正則表達式在惡意代碼動態(tài)分析中的應(yīng)用[A];2009通信理論與技術(shù)新發(fā)展——第十四屆全國青年通信學術(shù)會議論文集[C];2009年

3 王輝;丁明君;楊進;;正則表達式在企業(yè)信息管理開發(fā)中的應(yīng)用[A];2010年MIS/S&A學術(shù)交流會議論文集（中國造船工程學會學術(shù)論文集）[C];2010年

4 田珂;趙國鴻;;利用TCAM與正則表達式對郵件協(xié)議進行二次識別的思想研究[A];第十六屆計算機工程與工藝年會暨第二屆微處理器技術(shù)論壇論文集[C];2012年

5 李佳;魏更宇;胡楠;王樅;楊義先;;基于特征自生成的畸形SIP信令檢測算法[A];2010通信理論與技術(shù)新發(fā)展——第十五屆全國青年通信學術(shù)會議論文集（下冊）[C];2010年

6 周小甲;周慶利;;中文病歷文本中時間信息自動標注[A];2011年浙江省醫(yī)學會醫(yī)學工程學分會第九屆學術(shù)年會論文匯編[C];2011年

7 周小甲;周慶利;;中文病歷文本中時間信息自動標注[A];浙江生物醫(yī)學工程學會第九屆年會論文匯編[C];2011年

中國重要報紙全文數(shù)據(jù)庫 前1條

1 彭福祥 張鈞;ASP.NET基本數(shù)值處理技巧[N];計算機世界;2006年

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

1 彭坤楊;基于TCAM的高速可擴展的正則表達式匹配技術(shù)[D];中國科學技術(shù)大學;2013年

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

1 李哲夫;正則表達式在電信業(yè)務(wù)處理中的應(yīng)用研究[D];暨南大學;2008年

2 范慧萍;基于正則表達式的協(xié)議識別研究與實現(xiàn)[D];國防科學技術(shù)大學;2007年

3 段海生;基于正則表達式的深度包壓縮算法研究[D];西安電子科技大學;2010年

4 姜英杰;支持正則表達式的文本匹配優(yōu)化算法[D];東北大學;2012年

5 張潔坤;時空高效的正則表達式匹配算法研究[D];湖南大學;2010年

6 張娜;基于正則表達式的深度包檢測研究[D];華東師范大學;2007年

7 劉鵬;面向存儲的正則表達式匹配算法研究[D];解放軍信息工程大學;2010年

8 劉俊超;基于正則表達式的應(yīng)用層協(xié)議識別技術(shù)研究[D];國防科學技術(shù)大學;2008年

9 蔣俐峗;基于多步投機的正則表達式匹配算法的研究[D];湖南大學;2011年

10 金軍航;面向深度包檢測的存儲高效的正則表達式匹配算法研究[D];湖南大學;2010年

，

本文編號：1106049