Multimedia databases are increasingly common in science, business, entertainment and many other applications. Their size and high dimensionality of features are major challenges for efficient and effective retrieval and mining. Effective similarity models are usually computationally far too complex for straightforward usage in large high dimensional multimedia databases. We propose efficient algorithms for these effective models that show substantially improved scalability. Our index-based methods for efficient query processing and mining restrict the search space to task relevant data. Multistep filter-and-refine approaches using novel filter functions with quality guarantees ensure that fast response times are achieved without any loss of result accuracy.