Configuration similarity is a special form of content based image retrieval which considers relative object locations. It can be used as a standalone method, or to complement retrieval based on visual or semantic features. The corresponding queries ask for sets of objects that satisfy some spatio-temporal constraints, e.g., "find all triplets of objects (v₁,v₂,v₃) such that v₁ is northeast of v₂ which is inside v₃". Processing of configuration similarity queries is a hard combinatorial problem which cannot be effectively solved for large image databases....[ Read more ]

Configuration similarity is a special form of content based image retrieval which considers relative object locations. It can be used as a standalone method, or to complement retrieval based on visual or semantic features. The corresponding queries ask for sets of objects that satisfy some spatio-temporal constraints, e.g., "find all triplets of objects (v₁,v₂,v₃) such that v₁ is northeast of v₂ which is inside v₃". Processing of configuration similarity queries is a hard combinatorial problem which cannot be effectively solved for large image databases.

This work proposes the application of local search algorithms which provide good, but not necessarily optimal, solutions in a pre-determined time threshold. First, we study techniques based on Genetic Algorithms, Iterative Improvement and Simulated Annealing. Next, we propose a number of techniques derived from Iterative Improvement, applying different transition mechanisms. Further, we perform an analysis of the search space and at last we propose enhanced algorithms that take into account the results of the search space analysis and the special characteristics of the problem. We evaluate the algorithms through extensive experimentation using various combinations of datasets and queries.

The quality of the output is calculated using a relation framework which allows the employment of the proposed methods in multiple resolutions and dimensions, thus covering a wide range of application needs.