数据流上的分位数近似算法研究

• 作者: 杨蓓 黄厚宽
• 来源期刊: 计算机研究与发展
• 学科: 工学
• 关键词: 数据流 概要数据结构 直方图 分位数 近似算法
• 年，卷（期）: 2008,（2）
• 所属期刊栏目: 人工智能
• 页码范围: 287-292
• 页数: 6页
• 分类号: TP311
• 字数: 4652字
• 语种: 中文

摘要

数据流是一种新型数据模型,广泛应用于交通流量监控、通信管理、传感器网络、股票分析、Web点击流等众多领域.近年来越来越多的学者关注于数据流上的分位数计算研究.由于流数据的连续、无界、易失等特性,存储完整的流数据信息并得到精确的查询结果几乎是不可能的.在实施查询计算时追求内存用量与查询精度之间的最佳均衡.设计了规范数直方图的概要数据结构以存储流数据的摘要信息,并在此基础上提出了单遍扫描的、联机的分位数近似算法,其时间和空间复杂度均线性于概要结构中桶的个数,而与数据流的长度无关,因而具有很好的可规模性.该方法在均匀分布的数据上取得了优良性能.分析了算法精度与内存需求的关系.实验结果表明该算法具有较精确的查询结果,具备良好的实用性和有效性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杨蓓	北京交通大学计算机与信息技术学院	8	83	5.0	8.0
3	黄厚宽	北京交通大学计算机与信息技术学院	139	2476	26.0	44.0