In some embodiments, a motion estimation search window cache is adaptively re-organized according to frame properties including a frame width and a number of reference frames corresponding to the current frame to be encoded/decoded. The cache reorganization may include an adaptive mapping of reference frame locations to search window cache allocation units (addresses). In some embodiments, a search window is shaped as a quasi-rectangle with truncated upper left and lower right corners, having a full-frame horizontal extent. A search range is defined in a central region of the search window, and is laterally bounded by the truncated corners.