在现实应用中存在大量的海量数据,由于其太大而不能完全装入计算机内存。因此在快速的内存和相对慢速的外存(比如硬盘)之间的输入/输出(I/O)通讯就成了制约算法性能的主要瓶颈。特别在以下方面:空间数据库中的海量几何数据、地理信息系统(GIS)、约束逻辑规划、数据库、统计学、虚拟现实系统、计算机图形学。由此产生了外存储算法与数据结构的设计和分析领域,其主要目标就是研究算法的局部性以尽量减小程序的输入/输出代价。极大点查找问题是是计算几何的一个重要的基本问题。由于极大点集在一个点集的边界上存在很多有意义的特性,其与凸包、最近点对等问题均有密切的联系。同时极大点查找问题也出现了越来越多的各种应用。本文研究了已有的极大点查找算法。在此基础上提出一种针对海量点集数据的极大点查找概率算法,并证明了算法的可靠性。通过实验取得了很好的实验效果。并对其在数据库查询中的应用进行了研究。本文的研究工作和创新包括以下两个方面:(1)针对极大点查找问题,目前还没有线性输入/输出次数的外存储算法。本文根据极大点数目的概率特性,针对独立同分布数据集,设计出了一种针对海量数据的线性输入/输出次数的极大点查找算法。并通过理论和试验证明了算法的可靠性。(2)随着信息技术的不断发展和应用的不断深入,数据收集手段越来越丰富,海量存储在数据库中也越来越普遍。本文将设计的算法应用到数据库的Skyline查询处理中,取得了良好的试验效果。