數據流上面向可伸縮模式的查詢方法研究

《數據流上面向可伸縮模式的查詢方法研究》是依託北京大學，由李紅燕擔任負責人的面上項目。

基本介紹

• 中文名：數據流上面向可伸縮模式的查詢方法研究
• 項目負責人：李紅燕
• 項目類別：面上項目
• 依託單位：北京大學

項目摘要

諸如醫療等實際套用領域更關注數據流上連續的數據區段而並非單個數據點，如何靈活地在數據流上表達基於模式的查詢請求並完成查詢處理，就成為一個重要和現實的問題。本課題深入分析了典型套用領域內數據流模式查詢的需求和特徵，提出了可伸縮模式查詢的概念，支持用戶在查詢目標內設定重複、缺失和倒置語義，通過提取查詢目標中相對不變、可相互區分的穩定因素來形成基模式，通過基模式組合來得到複雜目標模式，以不變（有限基模式集合）應萬變（基模式的各種組合出現），既保證了可伸縮模式豐富的查詢語義，又實現了查詢表達的確定性和簡潔性。進而通過在連續數據段和基模式這兩種不同表達形式之間的比對把數據流實時轉換成基模式流，通過查詢重寫在可伸縮模式查詢網路上執行查詢處理和最佳化，並保證在大數據量爆發和高噪聲環境下查詢的有效性。最終為用戶提供一種靈活的、語義豐富的、通用的可伸縮模式查詢方式。同時研製基於理論研究成果的原型系統。

結題摘要

普適計算和感測器網路的飛速發展使得數據流技術在現實生活中得到越來越廣泛的套用，諸如醫療等實際套用領域更關注數據流上連續的數據段而並非單個數據點，如何靈活地在數據流上表達基於模式的查詢請求並完成查詢處理，就成為一個重要和現實的問題。 本課題深入分析了典型套用領域內對數據流模式查詢的需求和特徵，提出了可伸縮模式的概念，支持用戶在查詢目標內設定重複、缺失和倒置語義，通過提取查詢目標中相對不變、可相互區分的穩定因素來形成基模式，通過基模式組合來得到複雜目標模式，以“不變（有限基模式集合）”應“萬變（基模式的各種組合出現）”，既保證了可伸縮模式豐富的語義，又實現了查詢表達的確定性和簡潔性。在用戶定義的查詢目標上，為避免在波段之間交叉重疊處的可伸縮語義混亂和波段匹配的二義性，先通過劃分機制把查詢目標表示為一系列首尾相接、可相互區分、互不交叉重疊的基本波段，然後對這些基本波段進行模式提取後生成原查詢目標上的基模式覆蓋。進而通過在連續數據區段和基模式這兩種不同表達形式之間的比對把數據流實時轉換成基模式流，通過查詢重寫將可伸縮約束轉換到基模式覆蓋上，得到基於可伸縮模式的查詢表示形式，通過作用在基模式上的操作集合、適用於可伸縮模式查詢處理的快取技術和模式存儲結構，實現了可伸縮模式查詢處理及最佳化，並保證在大數據量爆發和高噪聲環境下查詢的有效性。最終為用戶提供了一種靈活的、語義豐富的、通用的可伸縮模式查詢方式。 在理論研究成果的基礎上，研製了數據流上面向可伸縮模式查詢的原型系統，在研究組收集到的重症監護數據流上進行了充分實驗，通過原型系統和實驗分析對理論研究進行了驗證和完善。通過千萬量級真實數據集上的實驗表明，本課題提出的可伸縮模式查詢處理方法在時間和空間消耗兩個方面都能夠滿足醫療領域的實際需求。另外在準確率、召回率和處理效率方面進行的對比實驗表明，採用基於最佳化後的模式複合圖來進行可伸縮模式查詢處理方法要優於目前相關研究方法ZStream和NFAb，能夠有效輔助醫療決策。 基於課題研究成果，在核心期刊《計算機學報》，《計算機研究與發展》以及ICDE，ApWeb，WAIM，BIBM等國際學術會議上共發表論文25篇，其中已被EI收錄16篇。完成博士學位論文1篇，碩士學位論文16篇。獲得發明專利3項。獲得全國資料庫學術會議NDBC2012優秀研究生論文獎，以及CCF第一屆大數據創新大賽二等獎。