時間滑動窗口上數據流極值聚集的空間優化

丁維龍　韓燕波　王菁　趙卓峰

摘要：傳統的數據流極值聚集方法在極端情形下為獲得連續的精確解，會因維護大量候選項而導致巨大的內存開銷，為此文中提出了一種時間滑動窗口上內存有界的極值聚集方法，在候選項數量達到指定閾值時，該方法隨機抽樣新到達窗口的數據，使得內存維護有限數量的候選項，連續返回極值近似解，設計了一種空間有界的摘要數據結構REx-link，可以在有界的內存中基于隨機抽樣進行維護·實現時間滑動窗口上的數據流極值聚集，從理論上證明了隨機算法的出錯概率存在上界-并通過仿真實驗分析了算法的返回結果與精確解的近似程度，分析表明，計算精度和空間開銷的折中是實際應用可接受的。