云环境下基于BSP模型的大规模不动点迭代计算研究

Fixed point iterations widely exist in data mining and machine learning algorithms. These fixed point iterative algorithms are broadly used in the areas of online social networks, high-performance computing, recommendation systems, search engine, pattern recognition,etc. In recent years, in order to meet the needs of big data processing, people are exploiting cloud environment to launch large-scale fixed point iterative computations, which is a hot research topic in cloud computing and big data. Researchers have proposed a series of approaches and systems to support large-scale fixed point iterative computations under cloud environment. In this proposal, based on these previous works, we extend BSP (Bulk Synchronous Parallel) model to support large-scale fixed point iterative computations. To address the recently emerged challenges in big data processing, we will research on the multi-start iterative process, delta-based asynchronous iteration model, and dependency-based incremental processing. These research works aim at improving the performance of large-scale iterative computations from various aspects. In addition, in order to test and publicize our research results, we will design and implement a distributed computing framework prototype supporting large-scale iterative computations, which will integrate all of our optimization techniques.

不动点迭代广泛存在于数据挖掘和机器学习算法中，在社会网络分析、高性能计算、推荐系统、搜索引擎、模式识别等领域都有广泛应用。近年来，人们开始利用云环境进行大规模不动点迭代计算以适应大数据处理的需要，这也是当今云计算和大数据领域的研究热点，并且已经取得了一系列研究成果。本申请基于这些已有工作，以BSP（Bulk Synchronous Parallel）模型为基础，研究适合大规模不动点迭代计算的改进BSP模型。针对大数据新形势下的性能优化需求，研究基于多初始点的迭代过程优化、基于差别消息的异步迭代模型、基于数据依赖关系的增量处理技术，从多个方面提高大规模不动点迭代计算的处理速度。另外，为了便于验证和推广研究成果，本课题将基于研究内容，实现一个支持大规模不动点迭代计算的分布式计算框架原型系统。

不动点迭代广泛存在于数据挖掘和机器学习算法中，在社会网络分析、高性能计算、推荐系统、搜索引擎、模式识别等领域都有广泛应用。近年来，人们开始利用云环境进行大规模不动点迭代计算以适应大数据处理的需要，这也是当今云计算和大数据领域的研究热点，并且已经取得了一系列研究成果。本课题基于这些已有工作，以BSP（Bulk Synchronous Parallel）模型为基础，研究适合大规模不动点迭代计算的改进BSP模型。针对大数据新形势下的性能优化需求，研究基于多初始点的迭代过程优化、基于差别消息的异步迭代模型、基于数据依赖关系的增量处理技术，从多个方面提高大规模不动点迭代计算的处理速度。..本课题经过3年多的研究，取得了一系列的研究成果，基于异步计算、增量处理、高效聚类算法等方面研究成果发表了3篇国际顶级学术期刊论文（CCF推荐A类期刊），在学术界产生了一定的影响力。具体包括：提出了基于差别消息的异步迭代模型并开发了分布式异步计算框架Maiter，大大提高了部分图算法的运行效率；提出了基于MapReduce的大数据增量处理技术i2MapReduce，大大减少了增量迭代计算的运行时间；提出了高效的避免迭代计算的聚类算法LSH-DDP，避免了反复迭代计算所造成的大量开销。..关于高效分布式聚类算法的论文获第32届全国数据库学术会议（NDBC 2015）最佳论文奖，介绍部分研究成果的论文获2016年度东北大学优秀硕士论文奖1项，获辽宁省优秀学术成果奖2项，沈阳市优秀学术成果奖2项；并申请技术发明专利1项。关于异步优先级调度的技术成果被一些企业公司（包括GraphLab）所采用，应用到实际生产中。在本项目研究成果的基础上，本课题组负责人张岩峰获批国家自然科学基金面上项目1项、海外与港澳台学者合作项目1项，课题主要参与人李凤云获批国家自然科学基金青年基金项目1项。..另外，为了便于验证和推广研究成果，本课题将基于研究内容，实现一个支持大规模不动点迭代计算的分布式计算框架原型系统，并在Github上开放源代码https://github.com/zhangyf-neu/maiter。