A mechanism for performing a motion vector search at a current block within a current frame of video data. For each test vector position v of a plurality of test vector positions, compute a rate distortion value J(v) based on a combination of a distortion value D(v) and a bit cost value R(v,p,C). The distortion value D(v) represents a measure of distortion of the current block relative to a corresponding block Bv in the reference frame. The bit cost value R(v,p,C) depends on the test vector position v, a prediction vector p for the current block and a set C of one or more vectors c1, c2, . . . , cn. The one or more vectors c1, c2, . . . , cn are estimates (or predictions) of statistically-popular motion vectors for the current frame. The test vector position v* that gives a minimum rate-distortion value J(v*) is selected as the motion vector for the current block.