Abstract: Evaluating similarity queries over image collections effectively and efficiently is an important but difficult issue. In many settings, a system does not deal with individual queries1 in isolation, there rather is a stream of queries. Re-searchers have proposed a number of query-evaluation alternatives and generalizations, in particular parallel methods over several components, and methods that yield approximate results. Choosing a plan for a given query is subject to more criteria than in conventional settings, notably result quality next to response time and resource consumption. We have designed and implemented a query planner that incorporates these concepts. We describe our space of possible plans and how we search this space. The usefulness of such a planner depends on a number of criteria, e.g., increase of throughput, adaptivity to different workloads, query planning overhead, or influence of the scoring function in quantitative terms. This article describes respective evaluations and shows that the benefit of our particular approach is significant.