《大規模機率數據的管理與查詢最佳化》是依託清華大學，由李建擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：大規模機率數據的管理與查詢最佳化
- 依託單位：清華大學
- 項目負責人：李建
- 項目類別：青年科學基金項目
項目摘要,結題摘要,
項目摘要
幾乎所有的決策問題都不可避免的包含了一定程度的非確定因素，如數據測量中產生的噪音，參數估計的誤差等等。一般來講，處理非確定性數據的一個系統的方法是將這些數據視為隨機變數，然後以機率論為原則去進行數據處理和最佳化。隨著生成的非確定數據的規模日益增加，處理和查詢這些數據的難度也越來越大。因此我們需要新型的處理隨機數據的資料庫系統和新的查詢最佳化算法。今年來，關於機率資料庫和處理隨機輸入數據的最佳化算法是國際上研究的熱點和難點，存在很多挑戰。我們計畫在本項目中對隨機數據的管理和查詢最佳化算法進行深入系統的研究。具體來講，我們計畫深入探索如下問題：（1）關於非確定數據上的SQL查詢，排序，區間查詢等問題的更有效的算法；（2）非確定數據的流算法；（3）在非確定輸入下的各種最佳化問題；（4）非確定數據處理算法的套用，特別是在如感測器網路數據監控、民眾外包等新興領域中的套用。
結題摘要
近年來，隨著各種信息採集、整合系統，社會網路數據，機器學習預測算法的普遍採用，這些算法和系統所產生的非確定數據，隨機數據，機率數據的規模也日益增加。同時，各類決策問題也都不可避免的包含了一定程度的非確定因素。因此，處理和查詢這些數據，並基於這些數據來解決最佳化問題的難度也隨之加大。 該項目在這個大的背景下，有步驟的、系統的研究了處理和查詢非確定數據，以及隨機最佳化領域的若干問題，並取得了重要進展。其中，有代表性的成果包括（1）在隨機組合最佳化領域，我們發展了泊松近似的技術，並利用該技術給出了一大類隨機組合最佳化問題的最優近似算法，改進了前人在多個相關問題上的結果；（2）在機率模型學習與表示領域，我們第一次給出了最優的學習離散混合模型的採樣複雜度；（3）在隨機學習算法領域，我們第一次給出了多臂bandit選取問題的最優採樣算法。另外我們對於隨機數據上區間查詢，大規模數據的清洗等問題進行了深入研究並給出了更有效的算法。我們結合了機率論，組合最佳化，凸幾何，泛函分析，矩陣攝動理論，傅立葉分析和函式近似理論等多個領域的思想和工具，提出了處理隨機數據，學習機率模型，以及解決隨機最佳化問題的若干新技術，並利用這些技術解決了若干該領域內重要理論問題。在項目支持下，我們還在相關領域如近似算法、最近鄰查詢算法以及網路算法方面取得了若干成果。 在該項目支持下共發表會議與期刊文章 22 篇，其中 CCF A 類會議及期刊文章 8 篇，包括計算機科學頂級會議及期刊STOC，SODA，VLDB，NIPS，ICML，PAMI，TON等。
