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. Moreover, since there is a common practice that the provided similarity measures are considered as black-box algorithms, only general ap-proaches enabling efficiency tuning can be employed (e.g., the TriGen algorithm). However, the general approaches are not sufficient and so the database experts can no longer stand aside from the similarity modeling. In this project, we would like to "open the Pandora's box" and enter the world of domain experts, in order to design "indexable" similarity spaces. In general, we would like to describe a new similarity space modeling schema considering not only the retrieval quality but also the efficiency issues. In other words, we plan to introduce indexability measures to the similarity modeling process and investigate more variants of popular multimedia distance spaces. As we have recently shown [Beecks et al. 2011] in cooperation with RWTH Aachen, this ap-proach can result in interesting tradeoffs, where at least two orders of magnitude speedup can be achieved for the price of only slightly decreased retrieval quality.