分散式不確定數據查詢處理關鍵技術研究

《分散式不確定數據查詢處理關鍵技術研究》是依託中國人民大學，由覃飆擔任項目負責人的面上項目。

基本介紹

• 中文名：分散式不確定數據查詢處理關鍵技術研究
• 項目類別：面上項目
• 項目負責人：覃飆
• 依託單位：中國人民大學

項目摘要

由於現代信息技術的發展，數據分散式地產生、存儲和處理成為一種常態。在分散式開放環境下，當數據產生時會不可避免地引入一些模糊、不確定甚至錯誤，本項目用分散式不確定資料庫來管理大數據。在分散式環境下，查詢處理的首要任務不是計算結果元組的機率值，而是計算分散式不確定數據的特徵值，包括top-k、直方圖、高頻數據、數據草案和概要等。本項目從新穎的採樣策略入手，擬提出高效的算法求出不確定數據的特徵值，該算法能夠近似線性擴展；接著提出大數據的加速處理策略，典型的方法是高效的歸併算法和索引技術。本項目還要研究分散式不確定數據的聚集查詢和統計技術；由於針對的是海量數據和開放式環境，增量維護是高效求解特徵值的關鍵技術。最後，研發一個分散式不確定資料庫原型系統，對本項目提出的理論和算法進行驗證和分析。本項目的工作不僅對分散式不確定資料庫查詢處理有直接意義，而且對MapReduce和資料庫的有機結合有理論指導。

結題摘要

由於現代信息技術的發展，數據分散式地產生、存儲和處理成為一種常態。在分散式開放環境下，當數據產生時會不可避免地引入一些模糊、不確定甚至錯誤，本項目用分散式不確定資料庫來管理大數據。如何讓用戶更高效地獲取所需的信息，是一項重要的研究，最簡單、有效的方式是信息檢索技術，搜尋結果的好壞與用戶滿足非常相關。本項目主要研究在後驗特徵不足的情況下，如何從有限的數據中，挖掘更好的先驗特徵及設計有效的排序模型來較快、較好地提升時效性檢索的排序效果。 在元組獨立的機率資料庫中根據不等式的結構特性，我們把不等式查詢語句被分為三類：路徑類型、樹類型和圖類型，我們提出了高效的算法來計算不等式查詢的機率和輸入元組對結果元組的敏感性。 在AI的不確定推理中，對信念有兩種有用的並且不同的理解：第一種是絕對信念或者命題中的信念程度，第二種是信念更新或者信念度量的改變。本項目通過為信念函式設計一個信念更新框架建立了Pignistic變換和似然變換的聯繫，在該信念更新框架中似然變換工作在信念更新，而Pignistic變換工作在絕對信念，進一步我們定義了一個新的信念更新操作來聯繫這兩種變換，並且解釋了在信念函式模型中參數統計推斷的架構。 本項目接著研究了一個公理驗證系統，它的適用對象是帶有信用函式的決策支持。我們採用的策略是研究信用函式的對立面Savage理論，它的狀態空間是有限的並且結果集是連續系統。一致性公理用於確保所有的行動對同樣的最大和最小結果必須是一致的。我們的獨立性公理表明存在一個功能函式並且隱含著信用函式狀態空間的唯一性。我們進一步證明在沒有獨立性公理的中性理論中兩個事實是相同的，無論什麼時候他們都產生相同的信用函式。 近年來因果關係研究成為大數據的研究熱點之一，將因果關係研究與資料庫查詢相結合，以研究表中的元組對查詢結果的重要性，resilience是其中一種典型研究。針對帶有不等式關係的路徑類型查詢，實現了基於最大流最小割方法計算resilience的算法Min-Cut，並提出一個線性複雜度的動態規劃DPResi算法，通過將不等式的布爾連線查詢語句的resilience求解問題轉換為溯源圖中最短距離計算的問題，並結合溯源圖的包含關係及最優子結構性質，運用動態規劃的思想實現了線性時間開銷的DPResi算法，理論分析及實驗驗證了DPResi算法計算resilience的高效性並具有較好的擴