A Parallel Bulk Loading Algorithm for M-tree on Multi-core CPUs

A parallel bulk loading algorithm of M-tree is proposed in this paper, which takes advantage of the multi-core chips. The sequential bulk loading algorithm of M-tree consists of three steps: partition, recursion and aggregation, and we parallelize the first two steps. In the partition step, the whole dataset are split and assigned to several independent threads. Then, a tree-structure tasks graph is adopted to parallelize the second step recursion. The problems of load balancing and synchronization are both considered carefully in our algorithm. Experimental results have illustrated that the proposed parallel algorithm can speed up the procedure of bulk loading of M-tree significantly.