Extreme-scale algorithms for geometric graphical data models in imaging, social and network science

成像、社会和网络科学中几何图形数据模型的超大规模算法

• 批准号: 1417674
• 负责人: Andrea Bertozzi
• 金额: $ 30万
• 依托单位: University of California-Los Angeles
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-08-01 至 2018-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1417674&HistoricalAwards=false
• 关键词: Extreme; scale; algorithms; geometric; graphical

Big data is important right now; and extreme scale hardware, programming models and storage solutions are being developed. However the connection between transformational algorithms and the big data sets needs to be addressed. Researchers talk often about the upcoming "big data problem," yet skim over the relevant algorithms that can truly attack the problems in a concrete fashion, often because the traditional means of data analysis are not prevalent in the high-performance computing (HPC) world, and in concert, the HPC expertise is not prevalent in the data world. This project will solidify this connection, making the "big data" problem real by attacking the issues through identifiable concrete algorithmic research and by implementing the methods on the latest hardware platforms. Recently the principal investigator has developed scalable desktop algorithms that bridge that gap, leveraging fast spectral solvers to compute solutions of sparse classification problems for big data. This project will build on these scalable algorithms to implement them on several large-scale platforms and will address important application areas, for which desktop computing is insufficient. Examples of application areas for this project include high dimensional hyperspectral video data for chemical and biological agents, a problem of importance to homeland security, and statistical analysis of spatio-temporal multimodal crime data, and large-scale social network analysis.This project focuses on a new class of data-clustering algorithms that are designed to solve variants of the minimum cut problem on graphs for big data applications such as hyperspectral video data analysis, statistical analysis of spatio-temporal multimodal crime data, and large-scale social network analysis. Semi-supervised and unsupervised machine learning problems are included in the class of problems considered. The graph mincut problem is equivalent to total variation minimization on a graph and is a popular model for machine learning applications, except for its computational complexity. Building on ideas such as diffuse interfaces and dynamic thresholding, originally developed for physical sciences models and subsequently transferred to low dimensional image processing applications, this project will develop methods to solve the true graph cut problem by leveraging recent advances in scalable spectral graph algorithms. New codes for these methods will be developed for large parallel architectures. The research will advance both theoretical algorithmic issues and application areas.

大数据现在很重要;正在开发极端规模的硬件，编程模型和存储解决方案。然而，转换算法和大数据集之间的联系需要解决。 研究人员经常谈论即将到来的“大数据问题”，但却忽略了可以真正以具体方式解决问题的相关算法，这通常是因为传统的数据分析方法在高性能计算（HPC）世界中并不普遍，并且HPC专业知识在数据世界中并不普遍。该项目将巩固这种联系，通过可识别的具体算法研究和在最新硬件平台上实施方法来解决“大数据”问题，使“大数据”问题成为真实的。最近，首席研究员开发了可扩展的桌面算法，弥补了这一差距，利用快速谱求解器来计算大数据稀疏分类问题的解决方案。 该项目将建立在这些可扩展的算法上，在几个大规模平台上实现它们，并将解决桌面计算不足的重要应用领域。 该项目的应用领域包括化学和生物制剂的高维超光谱视频数据，这是一个对国土安全很重要的问题，以及时空多模式犯罪数据的统计分析，和大规模的社会网络分析。这个项目的重点是一类新的数据-聚类算法被设计为解决图上的最小割问题的变体，用于大数据应用，例如高光谱视频数据分析，时空多模态犯罪数据统计分析和大规模社会网络分析。 半监督和无监督机器学习问题包括在考虑的问题类。 图分割问题等价于图上的全变差最小化，并且是机器学习应用的流行模型，除了其计算复杂度之外。 基于最初为物理科学模型开发并随后转移到低维图像处理应用程序的扩散接口和动态阈值等想法，该项目将通过利用可扩展谱图算法的最新进展来开发解决真实图切割问题的方法。 这些方法的新代码将开发大型并行架构。 该研究将推进理论算法问题和应用领域。