A computer system for motion estimation in screen remoting scenarios, the system comprising: an input buffer configured to receive one or more pictures in a video sequence; a video encoder configured to encode the one or more pictures to produce encoded data by performing operations that include: splitting a reference picture into multiple grid areas along horizontal and vertical grid lines; storing hash values for candidate blocks in the reference picture in a multi-level data structure that organizes the hash values for the candidate blocks by grid area and hash index; encoding a current picture of the one or more pictures using the multi-level data structure, including: calculating a hash value for a current block in the current picture; and searching, subject to a spatial constraint, for a matching block in a reference picture based at least in part on the hash value for the current block, wherein the spatial constraint defines a search area in the reference picture within which hash values for the candidate blocks in the reference picture may be compared to the hash value for the current block, the search area being either a given grid area among the multiple grid areas that includes a block collocated with the current block, or the given grid area and multiple grid areas adjacent to the given grid area in the reference picture; and an output buffer configured to store the encoded data for output as part of a bitstream. an input buffer configured to receive one or more pictures in a video sequence; a video encoder configured to encode the one or more pictures to produce encoded data by performing operations that include: splitting a reference picture into multiple grid areas along horizontal and vertical grid lines; storing hash values for candidate blocks in the reference picture in a multi-level data structure that organizes the hash values for the candidate blocks by grid area and hash index; encoding a current picture of the one or more pictures using the multi-level data structure, including: calculating a hash value for a current block in the current picture; and searching, subject to a spatial constraint, for a matching block in a reference picture based at least in part on the hash value for the current block, wherein the spatial constraint defines a search area in the reference picture within which hash values for the candidate blocks in the reference picture may be compared to the hash value for the current block, the search area being either a given grid area among the multiple grid areas that includes a block collocated with the current block, or the given grid area and multiple grid areas adjacent to the given grid area in the reference picture; and splitting a reference picture into multiple grid areas along horizontal and vertical grid lines; storing hash values for candidate blocks in the reference picture in a multi-level data structure that organizes the hash values for the candidate blocks by grid area and hash index; encoding a current picture of the one or more pictures using the multi-level data structure, including: calculating a hash value for a current block in the current picture; and searching, subject to a spatial constraint, for a matching block in a reference picture based at least in part on the hash value for the current block, wherein the spatial constraint defines a search area in the reference picture within which hash values for the candidate blocks in the reference picture may be compared to the hash value for the current block, the search area being either a given grid area among the multiple grid areas that includes a block collocated with the current block, or the given grid area and multiple grid areas adjacent to the given grid area in the reference picture; and calculating a hash value for a current block in the current picture; and searching, subject to a spatial constraint, for a matching block in a reference picture based at least in part on the hash value for the current block, wherein the spatial constraint defines a search area in the reference picture within which hash values for the candidate blocks in the reference picture may be compared to the hash value for the current block, the search area being either a given grid area among the multiple grid areas that includes a block collocated with the current block, or the given grid area and multiple grid areas adjacent to the given grid area in the reference picture; and an output buffer configured to store the encoded data for output as part of a bitstream.