EAGER: Dryads - Next Generation Tree Algorithms

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

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.