In this paper, we propose the use of data mining algorithms to create a macroblock partition mode decision algorithm for inter-frame prediction, to be used as part of a high-efficient H.263 to H.264 transcoder. We use machine learning tools to exploit the correlation and derive decision trees to classify the incoming H.263 MC residual into one of the several coding modes in H.264. The proposed approach reduces the H.264 MB mode computation process into a decision tree lookup with very low complexity. Experimental results show that the proposed approach reduces the inter-prediction complexity by as much as 60% while maintaining the coding efficiency. ©2007 IEEE.