Cloud Tree: A Library to Extend Cloud Services for Trees

In this work, we propose a library that enables on a cloud the creation and management of tree data structures from a cloud client. As a proof of concept, we implement a new cloud service Cloud Tree. With Cloud Tree, users are able to organize big data into tree data structures of their choice that are physically stored in a cloud. We use caching, prefetching, and aggregation techniques in the design and implementation of Cloud Tree to enhance performance. We have implemented the services of Binary Search Trees (BST) and Prefix Trees as current members in Cloud Tree and have benchmarked their performance using the Amazon Cloud. The idea and techniques in the design and implementation of a BST and prefix tree is generic and thus can also be used for other types of trees such as B-Tree, and other link-based data structures such as linked lists and graphs. Preliminary experimental results show that Cloud Tree is useful and efficient for various big data applications.