《基於略圖挖掘的在不同時空域的網路流式數據實時處理》是依託東南大學，由肖卿俊擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：基於略圖挖掘的在不同時空域的網路流式數據實時處理
- 項目類別：青年科學基金項目
- 項目負責人：肖卿俊
- 依託單位：東南大學
中文摘要,結題摘要,
中文摘要
近年來隨著計算機網路和感測器技術的發展，人們從世界各個角落採集數據，帶來了數據規模的飛速增長。為了滿足人們對實時數據處理的需要，學者們提出了流式數據：它是數據的一個序列，並且要求在處理過程中任何元素只能讀取一次，以及只能利用空間受限的高速存儲介質。流式數據處理在實際系統得到廣泛的套用，比如骨幹網流量分析、無線電子標籤監測、搜尋引擎數據分析等等。然而，現有的算法主要關注單個數據流的實時分析，在海量數據流的並行處理以及多時空數據流的關聯分析方面仍然不夠深入和完善。為此，本課題擬對時空域的流式處理的關鍵技術和理論進行深入研究。在符合套用需求的前提下，設計一套分散式的流式數據實時處理機制及算法，包括海量數據流聚合信息挖掘、不同時間段的數據流的關聯分析和模式識別、不同空間域的數據流處理節點的協同工作。基於上述階段性研究成果，申請人將研製流式數據處理算法庫，並實際驗證所提出方法的正確性和有效性。
結題摘要
隨著軟體定義網路和數據中心網的快速發展，基於流式數據處理方法的網路流量測量成為研究熱點，可以為網路故障診斷和網路異常檢測提供基礎測度數據。此外，隨著無源感測網的發展，無線射頻標籤RFID技術逐步普及，物流倉儲系統中的大量射頻標籤的高效估算和管理成為近年的另一個研究熱點。然而，傳統的網路測量技術和RFID標籤集合估算技術無法實現高精度、低開銷、近實時的估算測度數據估算，也無法有效支持跨時空域的聯合數據分析。本報告研究了如何改進和利用基於略圖挖掘的流式數據處理方法實現上述目標。 具體來說，在本項目的資助下，我們分別研究了如下的科學問題。（1）單數據流的存儲空間緊湊的基數近似估算問題：我們的算法空間需求比最新的HyperLogLog數據流基數估算法壓縮20%-50%。在Hacker News上，我們的算法成為最受歡迎的HyperLogLog算法改進之一，並被英國的Axiom Inc.公司實現和用來分析時序數據。（2）海量數據流並發輸入時的大基數流估算問題：申請人所提出的基數估量器，已被用於分析來自CAIDA的真實網路流量數據，相對傳統估算法將空間要求降低十倍。該論文算法的實現代碼被世界領先的鍵值記憶體資料庫Redis和時序資料庫Influx接收成為標準模組之一，用於檢測top-k的大基數流。（3）兩個RFID標籤集合的聯合估算問題：我們額外利用了射頻標籤間的無線信號衝突信息，將兩個標籤集合的交並補規模估算在達到預設精度的前提下，將協定執行的時間成本降低35%。（4）RFID標籤集合掃描的時間長度自適應調整算法和雙標籤集合的聯合估算問題：我們自適應調整每個標籤集合掃描的幀長度，允許利用不同長度的幀掃描數據，推斷出兩個標籤集合交並補的規模。這與傳統的固定幀長度的標籤集合掃描算法相比，達到同樣估算精度的時間成本降低了數倍。（5）任意多個RFID標籤集合的聯合估算問題：我們研究如何準確估算任意多個RFID標籤集合的交並補運算結果的基數。我們的算法兼容RFID標準協定EPC C1G2，且允許幀長度的自適應調整。相比於以前的多集合聯合估算法，我們的算法將各個標籤集合的掃描時間減少了數倍。 截止目前，我們項目的研究成果是6篇第一作者SCI/EI論文，其中發表了在中國計算機學會CCF的計算機網路方向A類期刊論文四篇，在A類會議論文一篇，和B類會議論文一篇。
