【作者】 邱海艳； 陈立军； 赵加奎；

【机构】 北京大学计算机科学与技术系；

【摘要】 <正>Maintaining data stream synopsis is very important in DSMS.Data stream tuple is real-time,continuous and ordered(namely,aged).Query engine needs to adjust query plan by on-line synopsis to guarantee its processing efficiency.In this paper,we propose a new synopsis structure called ETHs,which partitions time dimension into exponential intervals by EH partitioning technique.In each subinterval,we use tiny histogram which has small space and time complexity to record summary information.So,it can reflect the stateness of certain data elements and share computations under n-of-N model.With a guaranteed precision ofεN,it continuously maintaining the summary information of the most recent N elements over data stream with little time and space overhead.Performance study shows that ETHs is a good data stream synosis maintaining algorithm.更多还原

【Abstract】 Maintaining data stream synopsis is very important in DSMS.Data stream tuple is real-time,continuous and ordered(namely,aged).Query engine needs to adjust query plan by on-line synopsis to guarantee its processing efficiency.In this paper,we propose a new synopsis structure called ETHs,which partitions time dimension into exponential intervals by EH partitioning technique.In each subinterval,we use tiny histogram which has small space and time complexity to record summary information.So,it can reflect the stateness of certain data elements and share computations under n-of-N model.With a guaranteed precision ofεN,it continuously maintaining the summary information of the most recent N elements over data stream with little time and space overhead.Performance study shows that ETHs is a good data stream synosis maintaining algorithm.更多还原