EAGER: Dryads - Next Generation Tree Algorithms

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

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.