EAGER: Dryads - Next Generation Tree Algorithms

EAGER：Dryads - 下一代树算法

• 批准号: 1647432
• 负责人: Robert Brunner
• 金额: $ 29.98万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-08-01 至 2019-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1647432&HistoricalAwards=false
• 关键词: EAGER; Dryads; Next; Generation; Tree

Many data sets can be represented via a natural hierarchical ordering, which can be easily represented programmatically by using tree data structures. For example, two-dimensional spatial data can be organized by using quad-trees, while three-dimensional data can be organized by using oct-trees. As data volumes continue to increase, compact representations of the extremely large data become increasingly important since the representations can enable much more efficient data selection, transportation, and processing. Yet the development of standardized, generic and efficient tree data structures that both scale to massive data and leverage the capabilities of modern computer architectures remains an unmet need. This research effort addresses this need by designing and implementing a library of generic implicit tree abstractions that will provide the foundation for next generation analysis codes in data driven sciences. By working with the C++ standardization committee, this research will potentially impact millions of software developers, worldwide, since this low level language is implicitly used by many high-level language analysis tools and libraries.This research will investigate generic and high performance tree building blocks by exploring two key elements. First, low-level bit manipulation techniques will be created that can be optimized for specific computer architectures (such as the Intel Haswell). These techniques will be developed in conjunction with the international C++ standardization committee as an open source library and will impact a wide range of applications areas including arbitrary precision arithmetic, cryptography, and tree indexing strategies. Second, a generic library of implicit tree structures will be developed, by using the previously developed bit manipulation techniques, and submitted as a new, open-source library to the Boost community for broader dissemination. Finally, to demonstrate the efficacy of these new software libraries, two example tree applications will be developed and published: an oct-tree used for numerical simulations and a decision trees used for machine learning.

许多数据集可以通过自然的层次顺序表示，可以使用树数据结构以编程方式轻松表示。例如，二维空间数据可以使用四叉树来组织，而三维数据可以使用八叉树来组织。随着数据量不断增加，超大数据的紧凑表示变得越来越重要，因为这些表示可以实现更有效的数据选择、传输和处理。然而，开发能够扩展到海量数据并利用现代计算机架构功能的标准化、通用和高效的树数据结构仍然是一个未满足的需求。这项研究工作通过设计和实现通用隐式树抽象库来满足这一需求，该库将为数据驱动科学中的下一代分析代码奠定基础。通过与 C++ 标准化委员会合作，这项研究将可能影响全球数百万软件开发人员，因为这种低级语言被许多高级语言分析工具和库隐式使用。这项研究将通过探索两个关键元素来研究通用和高性能树构建块。首先，将创建可以针对特定计算机架构（例如 Intel Haswell）进行优化的低级位操作技术。这些技术将作为开源库与国际 C++ 标准化委员会联合开发，并将影响广泛的应用领域，包括任意精度算术、密码学和树索引策略。其次，将使用先前开发的位操作技术来开发隐式树结构的通用库，并将其作为新的开源库提交给 Boost 社区以进行更广泛的传播。最后，为了展示这些新软件库的功效，将开发并发布两个示例树应用程序：用于数值模拟的八叉树和用于机器学习的决策树。