A Partitioning Scheme for Big Dynamic Trees

In this paper, we propose a scheme for partitioning dynamically growing big trees and its implementation. The scheme is based on the history-pattern encoding scheme for dynamic multidimensional datasets. Our scheme of handling big dynamic trees is relying on the history-pattern encoding, by which large scale datasets can be treated efficiently. In order to partition these dynamic trees efficiently, the encoding scheme will be improved and adapted to the partitioning. In our partitioning scheme of a tree T, the path from the T’s root node to the root node of a partitioned subtree, is treated as an index for selecting the subtree. The path is split into a shared path and the local path in the subtree and each path is encoded by using the history-pattern encoding. The partitioning scheme contributes to the reduction of the storage cost and the improvement of the retrieval cost. In this paper, after our tree encoding scheme designed for the partitioning is described, some problems caused in the encoding are addressed and their countermeasure is presented. Finally, an implemented prototype system is described and evaluated.