High utility itemset mining discovers itemsets whose utility is above a given threshold, where the utility measures the importance of an itemset. It overcomes the limitation of frequent pattern mining, which uses frequency as its quality measure. To speed up the performance for mining high utility itemsets, many algorithms have been proposed which usually focus on optimizing the candidate generation process. However, memory and time performance limitations still cause scalability issues, especially when the dataset is very large. In this paper, the problem is addressed by proposing a distributed parallel algorithm, PHUI-Miner, and a sampling strategy, which can be used either separately or simultaneously. PHUI-Miner parallelizes the state-of-the-art high utility itemset mining algorithm HUI-Miner. In PHUI-Miner, the search space of the high utility itemset mining problem is divided and assigned to nodes in a cluster, which splits the workload. The sampling strategy investigates the required sample size of a dataset, in order to achieve a given accuracy. The sample size is selected based on a new theorem, which provides a theoretical guarantee on the accuracy of results. We also propose an approach combining sampling with PHUI-Miner, which mines an approximate set of results, but could provide better time performance. In our experiments, we show that PHUI-Miner has high performance on different datasets and outperforms the state-of-the-art non-parallel algorithm HUI-Miner. The sampling strategy achieves accuracies much higher than the guarantee provided by the theorems in practice. Extensive experiments are also conducted to compare the time performance of PHUI-Miner with and without sampling.