This paper presents two one-pass algorithms for dynamically computing frequency counts in sliding window over a data stream-computing frequency counts exceeding user-specified threshold ε. The first algorithm constru...This paper presents two one-pass algorithms for dynamically computing frequency counts in sliding window over a data stream-computing frequency counts exceeding user-specified threshold ε. The first algorithm constructs subwindows and deletes expired sub-windows periodically in sliding window, and each sub-window maintains a summary data structure. The first algorithm outputs at most 1/ε ＋ 1 elements for frequency queries over the most recent N elements. The second algorithm adapts multiple levels method to deal with data stream. Once the sketch of the most recent N elements has been constructed, the second algorithm can provides the answers to the frequency queries over the most recent n （ n≤N） elements. The second algorithm outputs at most 1/ε ＋ 2 elements. The analytical and experimental results show that our algorithms are accurate and effective.展开更多
Classification,using the decision tree algorithm,is a widely studied problem in data streams.The challenge is when to split a decision node into multiple leaves.Concentration inequalities,that exploit variance informa...Classification,using the decision tree algorithm,is a widely studied problem in data streams.The challenge is when to split a decision node into multiple leaves.Concentration inequalities,that exploit variance information such as Bernstein's and Bennett's inequalities,are often substantially strict as compared with Hoeffding's bound which disregards variance.Many machine learning algorithms for stream classification such as very fast decision tree(VFDT) learner,AdaBoost and support vector machines(SVMs),use the Hoeffding's bound as a performance guarantee.In this paper,we propose a new algorithm based on the recently proposed empirical Bernstein's bound to achieve a better probabilistic bound on the accuracy of the decision tree.Experimental results on four synthetic and two real world data sets demonstrate the performance gain of our proposed technique.展开更多
文章研究并解决数据中心的远程内存直接读取(remote direct memory access, RDMA)技术的网络拥塞控制问题。针对主流拥塞控制算法数据中心量化拥塞通知(data center quantized congestion notification, DCQCN)的收敛速度慢和缺乏硬件...文章研究并解决数据中心的远程内存直接读取(remote direct memory access, RDMA)技术的网络拥塞控制问题。针对主流拥塞控制算法数据中心量化拥塞通知(data center quantized congestion notification, DCQCN)的收敛速度慢和缺乏硬件实现方案的不足,提出可参数硬件化的数据中心量化拥塞通知(parameterized DCQCN,DCQCN-p)算法,该算法通过优化拥塞流的速度因子a、g调整速度比例Rc,并通过电路设计减少降速的频次;通过建立算法模型和搭建网络仿真NS-3平台,对比DCQCN-p算法在面临拥塞时单个调度流速度调整的性能以及多个调度流并发情况下的时延和吞吐量。仿真结果表明:在单个流面临拥塞时,DCQCN-p算法的数据传输速率比DCQCN算法的提高了50%;DCQCN-p算法在链路上最小速率为13.28 Gbit/s,相较于DCQCN、TIMELY、数据中心传输控制协议(data center transmission control protocol, DCTCP)算法,分别增长了24%、48%、23%;DCQCN-p算法(方差65%)的带宽分配公平性相较于TIMELY算法(方差216%)和DCTCP算法(方差191%)表现出显著的性能提升。展开更多
基金Supported by the National Natural Science Foun-dation of China (60403027)
文摘This paper presents two one-pass algorithms for dynamically computing frequency counts in sliding window over a data stream-computing frequency counts exceeding user-specified threshold ε. The first algorithm constructs subwindows and deletes expired sub-windows periodically in sliding window, and each sub-window maintains a summary data structure. The first algorithm outputs at most 1/ε ＋ 1 elements for frequency queries over the most recent N elements. The second algorithm adapts multiple levels method to deal with data stream. Once the sketch of the most recent N elements has been constructed, the second algorithm can provides the answers to the frequency queries over the most recent n （ n≤N） elements. The second algorithm outputs at most 1/ε ＋ 2 elements. The analytical and experimental results show that our algorithms are accurate and effective.
基金the National Natural Science Foundation of China(Nos.60873108,61175047 and 61152001)the Fundamental Research Funds for the Central Universities of China(No.SWJTU11ZT08)
文摘Classification,using the decision tree algorithm,is a widely studied problem in data streams.The challenge is when to split a decision node into multiple leaves.Concentration inequalities,that exploit variance information such as Bernstein's and Bennett's inequalities,are often substantially strict as compared with Hoeffding's bound which disregards variance.Many machine learning algorithms for stream classification such as very fast decision tree(VFDT) learner,AdaBoost and support vector machines(SVMs),use the Hoeffding's bound as a performance guarantee.In this paper,we propose a new algorithm based on the recently proposed empirical Bernstein's bound to achieve a better probabilistic bound on the accuracy of the decision tree.Experimental results on four synthetic and two real world data sets demonstrate the performance gain of our proposed technique.
文摘文章研究并解决数据中心的远程内存直接读取(remote direct memory access, RDMA)技术的网络拥塞控制问题。针对主流拥塞控制算法数据中心量化拥塞通知(data center quantized congestion notification, DCQCN)的收敛速度慢和缺乏硬件实现方案的不足,提出可参数硬件化的数据中心量化拥塞通知(parameterized DCQCN,DCQCN-p)算法,该算法通过优化拥塞流的速度因子a、g调整速度比例Rc,并通过电路设计减少降速的频次;通过建立算法模型和搭建网络仿真NS-3平台,对比DCQCN-p算法在面临拥塞时单个调度流速度调整的性能以及多个调度流并发情况下的时延和吞吐量。仿真结果表明:在单个流面临拥塞时,DCQCN-p算法的数据传输速率比DCQCN算法的提高了50%;DCQCN-p算法在链路上最小速率为13.28 Gbit/s,相较于DCQCN、TIMELY、数据中心传输控制协议(data center transmission control protocol, DCTCP)算法,分别增长了24%、48%、23%;DCQCN-p算法(方差65%)的带宽分配公平性相较于TIMELY算法(方差216%)和DCTCP算法(方差191%)表现出显著的性能提升。
基金国家自然科学基金(the National Natural Science Foundation of China under Grant No.60273043)安徽省自然科学基金(the Natural Science Foundation of Anhui Province of China under Grant No.050460402)
