A method encodes an inter-frame of a compressed video, the inter-frame including multiple macroblocks in a predetermined order. Each macroblock has an associated motion vector. For each current macroblock in the predetermined order, a set of near macroblocks are identified. An index is assigned to each near macroblock. A difference between the motion vector of the current macroblock and the motion vector of each near macroblocks is determined. The indices of the near macroblocks are then sorted in order of the differences and appended to the inter-frame.