THOR: A New Programming Model for Data Analysis and Mining

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

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.