网络技术的快速发展和信息共享系统的大量应用催生了大数据时代的来临,很多传统的基于单机的数据挖掘算法已经无法满足大数据的挖掘需求,如何进行高效的并行的数据挖掘成为当前研究的热点。当前各种计算机应用系统处理的数据规模日渐增长和结构日益复杂,大规模图数据和大规模高维数据的出现对传统的数据挖掘方法提出了挑战。大规模图结构数据在各种应用中大量出现,例如生物信息学领域包含庞大的基因相互作用网络；WEB数据管理领域包含庞大的社会网络、WEB网页网络,社会媒体数据也多是以图的形式描述的。很多互联网上的信息如音频、视频都可表示为高维数据,在大数据背景下有效地进行图数据和高维数据的数据挖掘需要合适的分布式计算模型。MapReduce计算模型是目前最流行的一种云计算环境下的分布式计算模型,它可以将计算均匀地分布在多台异构的计算机上,并且屏蔽了复杂的并行编程,使得复杂的并行应用可以归结到两个简单的函数,map函数和reduce函数,它的高可用性、高可扩展性、高容错性以及简单性使得其受到企业界和学术界的重视。一些著名的IT公司如Facebook、雅虎等均采用Hadoop作为云计算环境中的重要基础软件。虽然MapReduce在分布式计算方面取得了巨大的声誉,但由于很多图数据和高维数据的数据挖掘算法的计算及其分布式处理往往涉及复杂的处理流程,经常需要多次迭代和大量的通信,而MapReduce通常适用于大数据集上的简单应用,导致MapReduce模型并不适用于具有局部性和迭代性的数据挖掘应用。但是其他的图处理系统,如Pregel, Hama等却不具备MapReduce优异的可扩展性和容错性,这对大规模的数据挖掘是非常重要的一个性质。为了使得MapReduce模型适用于图数据和高维数据的挖掘,本文对其进行了改造,提出了基于MapReduc e的局部迭代的MapReduce模型(LI-MR模型),并且在局部迭代的MapReduce模型指导下,研究一些具体的具有局部迭代性的数据挖掘算法,包括社会网络的权威值计算和社会网络的社区挖掘,以及高维数据聚类问题。本文主要研究内容和研究贡献包含以下几个部分。1.提出局部迭代的MapReduce模型以支持图挖掘由于MapReduce编程模型缺乏对算法迭代性和局部性的有效的支持策略,为了适应数据挖掘算法的迭代性和局部性,我们提出了局部迭代的MapRedue模型(LI-MR模型),并且通过两种方式实现了LI-MR模型的主要思想,第一种方式是扩展Hadoop系统,对其内核API进行改造以实现缓存和索引,从而支持Hadoop应用对数据的随机存取需求；第二种方式是Hadoop系统集成HBase数据库来实现缓存和索引。LI-MR模型的主要思想包括以粗粒度的数据块作为处理单位,消息通讯主要为数据块之间的信息交互；通过缓存和索引机制从上一次迭代的结果中获得对应数据块计算需要的局部信息,支持数据块的内存计算,支持算法的局部计算。2.提出局部迭代的标号传播算法大规模图的划分问题一直是人们所关注的热点问题,社会网络的社区挖掘作为图划分问题的一个应用,有很高的时效性的要求。标号传播算法(LPA)是一个时间复杂度为线性的快速社区挖掘算法,但是对于大规模的社会网络其运行时间仍然过长,本文提出局部迭代的标号传播算法运用LI-M(?)模型来解决标号传播算法的并行化问题。3.提出局部迭代的PageRank算法以往在MapReduce上运行PageRank算法,采取的方法以边为处理单位,这样导致数据在集群内的大量迁移。局部迭代的PageRank算法在LI-MR模型的指导下,将传统的基于内存的PageRank算法与MapReduce的良好的可扩展性结合起来,采用子图作为处理单位,子图内部的通讯不必在整个集群中迁移,这样,既保存了传统内存算法的效率,又得益于MapReduce的高可用性。4.提出基于局部敏感哈希函数的海量高维数据的分布式聚类方法对于海量高维数据的聚类,本文提出一种有效的基于代表点的批量处理方式,通过局部敏感性哈希函数,可以将距离近的数据点快速地聚集在一个桶中,采用桶的中心点作为代表点来代表这个桶内的所有点,通过这种代表点机制可以有效地削减聚类的数据规模。对于海量数据,需要一个较大的分类个数来满足对数据精度的刻画,对于较大的分类个数,本文通过局部敏感哈希函数来对比较计算进行裁减,尤其是对于具有较大k值的聚类,该方法可以在保证聚类质量的前提下大幅度提高聚类的效率。提高k-means运行效率的另一种方法是提高所选中心点的质量,本文针对k-means++不易于并行化的问题,提出了一种基于LI-MR模型的中心点选取方法,提高了k-means++并行选取中心点的效率。