The task of smart similarity search in huge multimedia databases remains still a big challenge for the image retrieval research. The domain experts try to design more effective retrieval models which often utilize complex and expensive similarity measures. At the same time, the database experts developing similarity-based indexes have to fight with less "indexable" similarity spaces induced by the more complex similarity measures.