Cloud multimedia streaming is an evolving technology to meet intensive bandwidth that is required by conventional multimedia to stream live events. Managing device heterogeneity is critical and affects user experience drastically. Response time and bandwidth are other issues to be focused on. The streaming services involve both desktop users and mobile users. High-definition live streaming video applications are quite challenging when considering mobile devices due to their restrained handling capability and bandwidth-constrained network connectivity. To meet up with the problem of resource allocation, bandwidth allocation, fault tolerance and at the same time to guarantee the desired level of Quality of Experience (QoE) to the end users an entire framework is proposed with novel algorithms for all the above addressed issues. The resource allocation performed at the cloud-end needs to be a dynamic process. The proposed framework incorporates the novel Guess Fit algorithm to provision virtual machines dynamically based on the priority scores calculated using probabilities as a result of the combined Naive Bayes algorithm with association rule mining. The score takes into account the hit ratios and the penalty values. The proposed Guess Fit Algorithm is found to perform better than the existing Fit algorithms. © 2018, Springer Nature Singapore Pte Ltd.