数据流上若干查询处理算法的研究.pdf

文档介绍：棋 大
博 士 学 位 论 文
数据流上若干查询处理算法的研究
院 系 信息科学与工程 学院
专 业 计算机 软件 与理论
姓 名 金澈清
指 导 教 师 周 傲英 教授
指 导 小 组 周傲英 教授
薛 向阳 教授
周水庚 教授
中文摘 要
,
过 去十 年 中 数据 流模型在 一 些信息 处理应 用 中广 泛 出现 , 这些 应用 包括 因
、 、 、 、 、 、
特 网 传感 器网络 网络 交通 监控 计 算机 网络 安全 数据 挖 掘 金 融监 控 制
、 。
造 业 天 文等 等 和 传 统数据 模 型相 比 , 数据 流模型具 有 几个 截然不 同的特征
数据 总量 被假 定 为是无 限的 数据 到达速率 非常快 数据 到达 次
, 。
序不 受应 用所 约 束 除非可 以保存 每个 元 素 均 只 能够 “ 看 ” 一 次 针 对
。 ,
数据 流模 型 的 查询 处理 技术具有几 点特殊要 求 首 先 该技术必 须能 够快 速 处理
, 。 ,
每 一 个 元组 实 时输 出 查询 处理结 果 其 次 , 该技 术 的空 间复 杂度 要 低 因 为数
。 ,
据流 的规模被假 定 为是 无 限的而 内存是 有限 的 再 次 这类技 术 由于 空 间复杂度
、
低 处理 元 组 速率 高, 往往只 能够 得到近似解 , 但 一般而 言 , 该近似解都 具备 一
。 。
定 的精确 度 最后 , 该技术适 应性 要 强 数据流 在某些应用 中可能非 常不 稳 定 ,
,
不仅 数据 分 布 , 而 且流 速都可 能发 生剧 烈变 化 “ 好 ” 的数据流 查询 处理 技术必
。
须 能够 在各 种状况下 都具 备 良好 的性 能
。
传 统 的 数 据 处 理 技 术 很 难 被 应 用 到 数 据 流 模 型 中 去 数 据 库 管 理 系 统
, ,
需 要 先 将 所 有 数 据 保 存 起 来 再 提 交