We present an approach for searching a large spatial database for a small set of two-dimensional objects based on their spatial relationships. We focus here on the specific problem of matching a sketched map containing several 2D objects to actual satellite imagery. Spatial relationships between objects are captured by the histograms of forces and encoded as an attributed relational graph. The matching process is performed by a memetic algorithm which combines the global search strategy of an evolutionary algorithm with a problem-specific local search method. We investigate several different local search methods and compare the results on randomly generated test data.