不確定圖數據查詢處理關鍵技術的研究

《不確定圖數據查詢處理關鍵技術的研究》是依託哈爾濱工業大學，由張煒擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：不確定圖數據查詢處理關鍵技術的研究
• 依託單位：哈爾濱工業大學
• 項目類別：青年科學基金項目
• 項目負責人：張煒

項目摘要

近年來，人們針對化合物、蛋白質等具有複雜結構的圖數據的管理技術開展了很多研究工作。目前的大多數研究工作都假設圖數據是準確無誤的。但是，大量實際套用中的圖數據往往並不準確，含有噪音、錯誤和不確定信息。這使得上述研究成果難以得到有效地套用。如何有效地存儲和索引大量不確定圖數據，以高效地支持各種複雜的查詢與檢索，是資料庫領域面臨的一個新的挑戰性問題。因此，本課題從資料庫的角度，研究不確定圖資料庫查詢處理關鍵理論和技術，包括不確定圖數據模型、不確定圖數據的存儲與索引方法、不確定圖數據的基本操作算法以及不確定圖數據查詢與最佳化處理算法，並研製相應的不確定圖數據查詢處理系統原型，驗證課題所提出方法的正確性和有效性。本項研究將提出一系列有關不確定圖數據查詢處理的理論、技術和方法，取得國際一流研究成果，具有重要學術意義。上述研究成果在化學、生物信息學和複雜社會網路等實際領域具有廣闊的套用前景。

結題摘要

如何高效地存儲和索引大量不確定圖數據以支持各種複雜的查詢是資料庫領域面臨的挑戰性問題。針對圖數據的存儲和索引問題，本課題設計了基於雙分支特徵編碼的索引和基於頻繁閉圖的索引結構。雙分支特徵編碼是由圖的短路徑及路徑兩側端點的鄰接點標籤的散列向量構成。基於雙分支特徵編碼的索引具有創建速度快和維護代價低的特點，適合於索引頻繁更新的圖數據。基於頻繁閉圖特徵的索引採用數據挖掘獲得的頻繁子圖特徵來構造。通過選擇適當的閉圖特徵集合構造的索引能夠高效的支持數據操作和查詢處理過程中的候選數據集的獲取。針對基本的圖數據操作算法，本課題研究了基於索引的子圖匹配和圖包含操作算法。基於雙分支特徵的子圖匹配操作算法首先計算查詢圖的最小雙分支特徵覆蓋。套用查詢圖的最小覆蓋特徵和部分隨機選擇的雙分支特徵疊代查詢雙分支特徵索引來獲得候選結果集。基於頻繁閉圖索引的圖包含操作算法在遍歷索引樹的同時將索引閉圖特徵與查詢圖進行子圖同構增量驗證，有效地減小了操作算法的代價。本課題研究了不確定圖上的複雜查詢處理算法。針對基於機率閾值距離閾值的可達性查詢，提出了基於最佳化分類樹的自適應雙向遍歷隨機抽樣算法來處理查詢。基於機率閾值的不確定圖匹配查詢處理算法通過模式圖簡化方法消除查詢圖模式中的冗餘信息，再根據節點可達機率上下界的估計值來過濾候選結果。從而減少模式圖匹配過程的代價。課題組還研究了不確定圖數據上的頻繁圖模式挖掘問題。提出了基於近似算法的不確定頻繁子圖挖掘算法和基於隨機遊走的K極大頻繁子模式挖掘算法。這些頻繁子圖模式挖掘算法獲得的結果有助於構造基於頻繁子圖特徵的不確定圖數據索引。