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.