In this paper we present a framework and the associated algorithms 
for evaluating similarity-based queries with expensive predicates.
As typically used in multimedia systems, a similarity-based query 
is evaluated using a scoring function that combines the scores of 
individual predicates (or conditions).  Users can ask for some k 
top-ranked objects (e.g., k = 10) or all the objects scored greater 
than a threshold (e.g., 0.9).  Efficient evaluation for such queries 
are quite different from that in traditional databases mainly because
of the generalization from Boolean to continuous scores.  Furthermore, 
query optimization is challenging because of the different access 
interfaces and cost models that a subsystem may support to evaluate 
individual predicates.  The related work assumes that the subsystems 
can support efficient sorted output through index access.  In contrast, 
our work generally considers the expensive predicates that can only 
support random access with per-object cost.  Expensive predicates 
include, for instance, user-defined functions and the conditions 
involving complex high-dimensional features that no effective index 
structures exist yet.  We first study the fundamental optimization 
principles for such queries, and then develop an optimal framework, 
called merged one-stream, which minimizes the cost of expensive predicates.
However, we also show that the general problem of finding the optimal 
schedule for expensive predicates is NP-hard, in contrast to that in the 
traditional Boolean context.  Furthermore, based on the framework, we 
present an algorithm for incremental processing, so that a query incurs
only cost proportional to the amount of the results that are 
actually retrieved. We also report the experiments based on our 
implementation to show the effectiveness of our approach.