EAGER: Dryads - Next Generation Tree Algorithms

University Of Illinois At Urbana-Champaign, Urbana IL

Investigators

Abstract

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.