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.