THOR: A New Programming Model for Data Analysis and Mining

THOR：数据分析和挖掘的新编程模型

• 批准号: 0833136
• 负责人: Richard Vuduc
• 金额: $ 68.66万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-09-01 至 2012-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0833136&HistoricalAwards=false
• 关键词: THOR; New; Programming; Model; Data

Virtually every human endeavor in a broad variety of disciplines in science, engineering, and finance, is encountering the need to make new discoveries through the analysis of massive datasets. Yet, the task of creating the necessary scalable analysis tools for modern high-performance parallel hardware is a daunting task, due to the complexity of developing efficient algorithms and subsequently having to parallelize and tune these algorithms for real systems. This research project aims to address this problem by developing a new domain-specific programming model, called the Tree-based High-Order Reduce (THOR) model, that enables rapid automatic implementation of customized parallel data analysis and mining tasks with minimal coding effort.The key enabling insight behind THOR is the generalized n-body problem (GNP) theory, a mathematical formalism that unifies the expression of seemingly disparate statistical data analysis tasks, including n-point correlation, hierarchical clustering, k-nearest neighbors classification, and kernel density estimation, among numerous others. As its name suggests, a GNP elegantly generalizes the classical n-body problem from physics to a much broader class of problems. Most importantly, the GNP form permits the development of asymptotically fast solutions, e.g., generalized versions of the fast multipole method. The THOR model enables the data analyst to specify a GNP, from which the THOR program generator can automatically produce a highly tuned parallel implementation. In short, this project aims to show how a programming model, which is bound to an appropriately high-level mathematical formalism while having the simplicity of a model like MapReduce, can lead to both scalable data analysis algorithms and their efficient implementation.

事实上，人类在科学、工程和金融等各个学科领域的每一项努力，都需要通过分析海量数据集来获得新发现。然而，由于开发高效算法以及随后必须针对实际系统并行化和调整这些算法的复杂性，为现代高性能并行硬件创建必要的可扩展分析工具的任务是一项艰巨的任务。该研究项目旨在通过开发一种新的特定于领域的编程模型（称为基于树的高阶归约（THOR）模型）来解决此问题，该模型能够以最少的编码工作快速自动实现定制的并行数据分析和挖掘任务。 THOR 背后的关键洞察力是广义 n 体问题 (GNP) 理论，这是一种数学形式主义，统一了看似不同的统计数据分析任务的表达，包括 n 点相关性、层次聚类、k 最近邻分类和核密度估计，其中众多 其他的。顾名思义，GNP 优雅地将经典的 n 体问题从物理学推广到更广泛的问题。最重要的是，GNP 形式允许开发渐进快速解决方案，例如快速多极子方法的广义版本。 THOR 模型使数据分析师能够指定 GNP，THOR 程序生成器可以根据该 GNP 自动生成高度调整的并行实现。简而言之，该项目旨在展示编程模型如何能够实现可扩展的数据分析算法及其高效实现，该模型与适当的高级数学形式绑定，同时具有 MapReduce 等模型的简单性。