丁維龍　韓燕波　王菁　趙卓峰

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