数据流频繁项算法性能提升的理论分析和算法研究
| 摘要 | 第1-4页 |
| Abstract | 第4-9页 |
| 第1章 引言 | 第9-15页 |
| ·数据挖掘与数据流 | 第9-11页 |
| ·数据流中的频繁项 | 第11-14页 |
| ·符号及其含义 | 第12页 |
| ·问题模型 | 第12-14页 |
| ·研究内容及主要贡献 | 第14-15页 |
| 第2章 相关工作 | 第15-23页 |
| ·数据流频繁项算法分类 | 第15-18页 |
| ·基于采样操作（Sampling-based） | 第15-16页 |
| ·基于哈希映射操作（Hashing-based） | 第16-17页 |
| ·基于计数操作（Counting-based） | 第17-18页 |
| ·层次数据流相关研究 | 第18页 |
| ·正性错误与负性错误 | 第18-19页 |
| ·典型算法举例 | 第19-23页 |
| ·Probabilistic InPlace | 第19-20页 |
| ·Group Test | 第20页 |
| ·Count Sketch | 第20-21页 |
| ·Frequent | 第21页 |
| ·Space Saving | 第21-23页 |
| 第3章 频繁项算法的误差边界 | 第23-41页 |
| ·Space Saving 回顾 | 第23-28页 |
| ·zip-f 分布 | 第23页 |
| ·数据结构与算法逻辑 | 第23-25页 |
| ·重要性质 | 第25-27页 |
| ·性能 | 第27-28页 |
| ·提升分析 | 第28-36页 |
| ·误差下界 | 第28页 |
| ·求解误差上界的更精确方法 | 第28-31页 |
| ·最小计数器组与严格上界 | 第31-33页 |
| ·严格上界的效率 | 第33-36页 |
| ·奢侈的解决方案 | 第36-40页 |
| ·方案描述 | 第36-39页 |
| ·实验 | 第39-40页 |
| ·本章小结 | 第40-41页 |
| 第4章 调整误差上界的新方法 | 第41-74页 |
| ·引子：层次信息的作用 | 第41-45页 |
| ·单计数器模型 | 第45-51页 |
| ·模型描述 | 第45-46页 |
| ·参数优化 | 第46-49页 |
| ·模拟优化实验 | 第49-50页 |
| ·放松条件的单计数器模型 | 第50-51页 |
| ·完备模型 | 第51-62页 |
| ·观察数据流的另一个视角 | 第51-54页 |
| ·模型描述 | 第54-56页 |
| ·性质 | 第56-58页 |
| ·完备模型下的SS_Random_r 合理性 | 第58-62页 |
| ·末BUCKET 生命周期策略 | 第62-67页 |
| ·策略描述 | 第62-64页 |
| ·参数优化 | 第64-67页 |
| ·末BUCKET 计数器策略 | 第67-71页 |
| ·策略描述 | 第67-68页 |
| ·参数转换 | 第68-69页 |
| ·误差分析 | 第69页 |
| ·变化边界的末BUCKET 计数器策略 | 第69-71页 |
| ·思考 | 第71-73页 |
| ·误差上界的增长速度 | 第71-72页 |
| ·算法参数与误差保证 | 第72-73页 |
| ·本章小结 | 第73-74页 |
| 第5章 实验 | 第74-87页 |
| ·算法性能评价标准 | 第74-76页 |
| ·人工数据生成器 | 第76-77页 |
| ·宏观对比 | 第77-80页 |
| ·频繁项查询 | 第77-79页 |
| ·top-k 查询 | 第79-80页 |
| ·微观对比 | 第80-86页 |
| ·排序偏差 | 第80-82页 |
| ·频率偏差 | 第82-84页 |
| ·top-k 准确率曲线 | 第84-85页 |
| ·最大可能误差 | 第85页 |
| ·微观指标与计数器替换次数的关系 | 第85-86页 |
| ·本章小结 | 第86-87页 |
| 第6章 对时间敏感数据流的处理 | 第87-90页 |
| ·时间权重 | 第87-88页 |
| ·权重的约束条件 | 第88-90页 |
| 第7章 结论 | 第90-93页 |
| ·研究工作总结 | 第90-91页 |
| ·进一步工作 | 第91-93页 |
| 参考文献 | 第93-96页 |
| 致谢 | 第96-97页 |
| 个人简历、在学期间发表的学术论文与研究成果 | 第97页 |
