The proposed approaches are independent of the refinement model used (e.g., QPM or QEX) and hence work for all models. Our first contribution is to generalize the notion of similarity queries and allow multiple query points in a query (referred to as multipoint queries). This generalization is necessary since refined queries cannot be always expressed as single point queries.We develop a k-NN algorithm that can handle multipoint queries and show that it performs significantly better than the naive approach (i.e. execute several single point queries using the 'single-point' k-NN algorithm and merge results). The second and the main problem we address is how to evaluate refined queries efficiently.