Querying by absolute locations cannot be easily extended to include relative locations of regions. For example, for a target with L regions and a query image with K regions, there are L!/((L-K)!K!) possible matches, each of which requires a distance computation. For example, L=20 and K=3 requires 1,140 comparisons. To circumvent this exhaustive search, we utilize a convenient representation of image spatial relationships and their comparisons based upon 2-D strings [6].
Figure: 2-D string representation of spatial relationships (a) un-rotated 2-D string, (b) rotated projection.
The 2-D string represents spatial relationships as illustrated in Figure 11(a). The 2-D string is a symbolic projection of the image along the x and y directions [18]. For example, the 2-D string for the image in Figure 11(a) is given as 
, where the symbol '<' denotes the left-right or bottom-top relation. Using 2-D strings, the match complexity is reduced to approximately 
per target image. Since we evaluate spatial relationships only at the final stage of the query, the complexity is further reduced to 
, where L' is the number of candidate regions in a target image, and L' < L and 
.