西安交通大学学报
西安交通大學學報
서안교통대학학보
JOURNAL OF XI'AN JIAOTONG UNIVERSITY
2012年
11期
106-111
,共6页
丁维龙%韩燕波%王菁%赵卓峰
丁維龍%韓燕波%王菁%趙卓峰
정유룡%한연파%왕정%조탁봉
数据流%极值聚集%抽样
數據流%極值聚集%抽樣
수거류%겁치취집%추양
传统的数据流极值聚集方法在极端情形下为获得连续的精确解,会因维护大量候选项而导致巨大的内存开销,为此文中提出了一种时间滑动窗口上内存有界的极值聚集方法.在候选项数量达到指定阈值时,该方法随机抽样新到达窗口的数据,使得内存维护有限数量的候选项,连续返回极值近似解.设计了一种空间有界的摘要数据结构REx-link,可以在有界的内存中基于随机抽样进行维护,实现时间滑动窗口上的数据流极值聚集.从理论上证明了随机算法的出错概率存在上界,并通过仿真实验分析了算法的返回结果与精确解的近似程度.分析表明,计算精度和空间开销的折中是实际应用可接受的.
傳統的數據流極值聚集方法在極耑情形下為穫得連續的精確解,會因維護大量候選項而導緻巨大的內存開銷,為此文中提齣瞭一種時間滑動窗口上內存有界的極值聚集方法.在候選項數量達到指定閾值時,該方法隨機抽樣新到達窗口的數據,使得內存維護有限數量的候選項,連續返迴極值近似解.設計瞭一種空間有界的摘要數據結構REx-link,可以在有界的內存中基于隨機抽樣進行維護,實現時間滑動窗口上的數據流極值聚集.從理論上證明瞭隨機算法的齣錯概率存在上界,併通過倣真實驗分析瞭算法的返迴結果與精確解的近似程度.分析錶明,計算精度和空間開銷的摺中是實際應用可接受的.
전통적수거류겁치취집방법재겁단정형하위획득련속적정학해,회인유호대량후선항이도치거대적내존개소,위차문중제출료일충시간활동창구상내존유계적겁치취집방법.재후선항수량체도지정역치시,해방법수궤추양신도체창구적수거,사득내존유호유한수량적후선항,련속반회겁치근사해.설계료일충공간유계적적요수거결구REx-link,가이재유계적내존중기우수궤추양진행유호,실현시간활동창구상적수거류겁치취집.종이론상증명료수궤산법적출착개솔존재상계,병통과방진실험분석료산법적반회결과여정학해적근사정도.분석표명,계산정도화공간개소적절중시실제응용가접수적.
