TPR-tree is a practical index structure for moving object databases. Due to the uniform distribution assumption, TPR-tree?s bulk loading algorithm (TPR) is relatively inefficient in dealing with non-uniform datasets. In this paper we present a histogram-based bottom up algorithm (HBU) along with a modi.ed top-down greedy split algorithm (TGS) for TPR-tree. HBU uses histograms to refine tree structures for different distributions. Empirical studies show that HBU outperforms both TPR and TGS for all kinds of non-uniform datasets, is relatively stable over varying degree of skewness and better for large datasets and large query windows.