Abstract: Improving data availability while achieving privacy protection is a challenging problem in the research of high-dimensional structured data publishing. The classical algorithm PrivBayes provides a solution to this problem. In order to further reduce the computational overhead and improve the data availability, a differential privacy data publishing algorithm ELPrivBayes based on Bayesian network is proposed. The theoretical calculation cost of the Bayesian network structure learning stage is analyzed, and the correlation matrix of mutual information between attributes is constructed to avoid the redundant calculation of mutual information in the iterative process of the structure learning algorithm and reduce the time complexity. Based on the average mutual information, the order of nodes entering the Bayesian network is optimized, the expectation of mutual information contributed by the exponential mechanism in the iterative process of structural learning is improved, and the statistical approximation between the generated dataset and the original dataset is improved. The low sensitivity of the network structure quality to the first node selection is empirically analyzed. The experimental results on four typical datasets show that compared with the classical algorithm PrivBayes and its improved scheme, the computational cost of the structure learning phase is reduced by 97%-99%, the mutual information captured based on the exponential mechanism is increased by 14%-67%, the average variation distance between the generated dataset and the original dataset is reduced by 32%-40%, and the accuracy of the constructed SVM classifier is increased by 4%-5%. When ε≤0.8, the availability of data generated by ELPrivBayes algorithm is improved more significantly.