该文做了三个方面的工作:首先从两个层次上提出了基于kd-树的过滤搜索算法和信息可传递的过滤搜索算法;其次,运用概率论和更严格的BBD-树结构对上述算法的时间复杂度和空间复杂度进行了理论的分析和论证;最后,通过大量的实验性能比较和分析从另一方面验证了该文提出的算法的高效性.首先在绪论部分介绍了数据库中知识发现(KDD)技术的概貌、聚集分析的重要研究意义和算法概况.在kd-树和BBD-树的预备知识基础上,研究了两种基于kd-树的提高k-means算法效率的搜索算法—过滤搜索算法和信息可传递的过滤搜索算法.通过理论分析对算法的复杂度进行了上限的估计,提出并证明了有关结论,为后面章节的实验分析提供有利的理论依据.最后,该文通过大量实验测试验证了该文提出的算法高效性并证实了对于算法的理论分析.