時間滑動窗口上數(shù)據(jù)流極值聚集的空間優(yōu)化

丁維龍　韓燕波　王菁　趙卓峰

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