海量数据近似top--k查询算法研究

目录

第1章 绪 论

1.1 课题来源

1.2 背景和意义

1.3 国内外研究现状

1.3.1 传统top-k查询研究现状

1.3.2 近似查询研究现状

1.3.3 确定性近似top-k查询研究现状

1.3.4 概率性近似top-k查询研究现状

1.4 国内外文献研究现状分析

1.5 主要研究内容

1.5.1 确定性近似top-k查询主要研究内容

1.5.2 概率性近似top-k查询主要研究内容

1.6 本文主要结构安排

第2章 近似top-k查询技术研究

2.1 Top-k查询技术

2.2 近似查询技术

2.2.1 简单随机抽样

2.2.2 伯努利抽样和泊松抽样

2.2.3 分层抽样

2.3 近似top-k查询相关定义

2.4 本章小结

第3章 确定性近似top-k查询

3.1 基线算法的研究

3.2 基于有序列表的近似算法

3.2.1 算法概述

3.2.2 预处理

3.2.3 增长剪切

3.2.4 收缩剪枝

3.2.5 算法代价理论分析

3.3 实验结果分析

3.4 本章小结

第4章 概率性近似top-k查询

4.1 基于概率测试的近似算法

4.1.1 算法概述

4.1.2 均匀分布情况下的概率预测

4.1.3 泊松分布情况下的概率预测

4.1.4 Top-k结果保证

4.2 基于抽样的近似查询方法

4.2.1 算法概述

4.2.2 预计算

4.2.3 近似误差估计

4.3 实验结果分析

4.3.1 效率分析

4.3.2 置信度分析

4.4 本章小结

结 论

参考文献

攻读硕士学位期间发表的论文及其它成果

声明

致 谢