基于區(qū)間標記索引的可達性查詢設計及其在外包數(shù)據(jù)庫中的應用.pdf

1、圖是數(shù)據(jù)結構中重要的組成部分。在圖模型中，點代表事物，邊代表事物之間的關系。圖模型有著非常廣泛的應用背景，如生物網(wǎng)絡、web網(wǎng)絡、計算機網(wǎng)絡等。近幾年來，隨著互聯(lián)網(wǎng)的發(fā)展，各種網(wǎng)絡內容成指數(shù)級增長，對其進行快速有效地分析與查詢是研究重點。其中許多問題都可以用圖模型來解決，這使得圖數(shù)據(jù)分析成為一個研究熱點。在圖數(shù)據(jù)分析中，可達性查詢是一項基本的查詢。而在眾多的可達性查詢方法中，區(qū)間標記索引近來備受關注。然而，當圖發(fā)生更新時，傳統(tǒng)的區(qū)間標記

2、索引算法并不能迅速地更新索引。
　　本文研究了基于區(qū)間標記索引的可達性查詢，利用預留空間的思想提出了一種可以動態(tài)更新區(qū)間索引的方法，又結合了二進制索引樹以使可達性查詢代價降低。該方法能針對不同的圖更新情形進行處理。實驗部分驗證了本文提出的動態(tài)更新算法能有效支持區(qū)間索引的更新。
　　另外，目前企業(yè)的存儲數(shù)據(jù)量迅速增長，一些中小型企業(yè)處理并非核心業(yè)務的數(shù)據(jù)代價太高，這時將數(shù)據(jù)庫外包也成為企業(yè)的合理選擇。隨著圖數(shù)據(jù)的發(fā)展與應用，圖

3、數(shù)據(jù)的外包查詢驗證成為一個研究熱點。然而針對圖數(shù)據(jù)的外包文獻相對較少，主要集中在子圖相似性查詢等領域。截止到本文完稿，可達性查詢尚無已發(fā)表的查詢驗證機制。
　　本文針對區(qū)間索引方式的可達性查詢設計了驗證信息及查詢驗證方案，使得用戶能夠在外包數(shù)據(jù)庫的背景下驗證數(shù)據(jù)的正確性及完整性。本文結合了MB-tree等驗證索引方式，簡化了驗證對象的大小，降低了驗證數(shù)據(jù)量。本文的驗證索引數(shù)據(jù)結構能夠合理的應用于外包數(shù)據(jù)庫中。實驗評估部分顯示該方案