Succinct Data Structure for Efficient Operations on Trees in Scikit-bio

Scikit-bio offers a great toolkit for working with biological data that has a tree-like structure. Although the current implementation, TreeNode, can accommodate a large variety of use-cases, its pointer-based nature limits its scalability to large trees with billions or even trillions of nodes. This project aims to remedy this problem by implementing a succinct data structure for trees based on its balanced parentheses representation, such that the memory usage and the time required for operations are minimized. There are two main components to this project. The first component pertains to the implementation of the data structure proposed in using Numba and NumPy based on improved-octo-waddle, a previous implementation using Cython. The other component relates to integrating the new data structure into the back-end of the existing TreeNode class within the library to enable compatibility with the existing APIs. The core deliverables include: an implementation of the new data structure that can be interfaced via TreeNode, an extensive suite of tests for correctness and benchmarking to ensure performance uplifts, and documentation to guide users on the usage of the new data structure. As a potential extension, GPU support will be investigated along with the exploration of an alternative solution proposed by Córdova, J. and Navarro, G. (2016).