| 数据流上的分位数近似算法研究 |
| |
| 引用本文： | 杨蓓,黄厚宽.数据流上的分位数近似算法研究[J].计算机研究与发展,2008,45(2):287-292. |
| |
| 作者姓名： | 杨蓓 黄厚宽 |
| |
| 作者单位： | 1. 北京交通大学计算机与信息技术学院,北京,100044;郑州大学信息工程学院,郑州,450001
2. 北京交通大学计算机与信息技术学院,北京,100044 |
| |
| 基金项目： | 国家九七三重点基础研究发展规划基金 |
| |
| 摘 要： | 数据流是一种新型数据模型,广泛应用于交通流量监控、通信管理、传感器网络、股票分析、Web点击流等众多领域.近年来越来越多的学者关注于数据流上的分位数计算研究.由于流数据的连续、无界、易失等特性,存储完整的流数据信息并得到精确的查询结果几乎是不可能的.在实施查询计算时追求内存用量与查询精度之间的最佳均衡.设计了规范数直方图的概要数据结构以存储流数据的摘要信息,并在此基础上提出了单遍扫描的、联机的分位数近似算法,其时间和空间复杂度均线性于概要结构中桶的个数,而与数据流的长度无关,因而具有很好的可规模性.该方法在均匀分布的数据上取得了优良性能.分析了算法精度与内存需求的关系.实验结果表明该算法具有较精确的查询结果,具备良好的实用性和有效性.
|
| 关 键 词： | 数据流 概要数据结构 直方图 分位数 近似算法 |
| 修稿时间： | 2006年12月26 |
Research on an Algorithm for Approximate Quantile Computation over Data Streams |
| |
| Yang Bei,Huang Houkuan.Research on an Algorithm for Approximate Quantile Computation over Data Streams[J].Journal of Computer Research and Development,2008,45(2):287-292. |
| |
| Authors: | Yang Bei Huang Houkuan |
| |
| Abstract: | |
| |
| Keywords: | data stream synopsis data structure histogram quantile approximate algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
