信息科技的飞速发展使得全球数据量爆炸增长,在海量数据中快速、有效地检索到目标数据的top-k查询方法是当前计算机研究的热点问题。在海量数据中,使用传统的top-k查询方法返回精确结果往往需要很长的响应时间。因此,以牺牲精度为代价来换取更快响应速度的近似top-k查询具有重要的研究意义。本文主要从确定性保证和概率性保证两方面对海量数据上的近似top-k查询算法展开研究。在具有确定性保证的近似top-k查询研究中,本文提出了基线算法BACG算法,基线算法在经典TA算法中加入近似因子?,放宽了阈值界限,使得返回的近似查询结果具有确定性保证。为了避免随机访问带来过大的时空开销,本文提出了基于有序列表的具有确定性保证的近似top-k查询算法AQCG算法,AQCG算法包括预处理、增长阶段和收缩阶段。在AQCG算法的增长阶段加入偏好扫描,使在扫描过程中能跳过属性列上的不必要元组,尽快收敛到阈值,进入收缩阶段。为了尽早结束查询过程,加入增长剪切和收缩剪切,剪切大部分元组,大大减少了I/O次数。通过实验验证,AQCG算法可以有效计算确定性近似top-k查询结果。在具有概率性保证的近似top-k查询研究中,本文提出了基于抽样的近似查询方法以及具有概率性保证的近似top-k查询算法TAPG算法。基于抽样的近似查询方法采用加权采样方法预计算构建数据梗概结构,根据数据的分布不断更新梗概结构来回答近似查询,通过对查询结果进行误差估计保证近似结果是符合用户的要求的近似top-k查询结果。TAPG算法在查询中加入概率阈值测试,减少查询过程中扫描的元组数,通过加入优先队列周期性的实现索引剪枝,剪切掉绝大多数最终可能出现在top-k查询结果中的概率非常小的元组,大大减少了I/O次数。结果表明,TPAG算法在概率保证和查询成本方面具有令人满意的性能。