ness of query refinement, there exists no work on how to implement query refinement efficiently in a multimedia database system. We explore such approaches in this paper. The proposed approaches are independent of the refinement model used (e.g., QPM or QEX) and hence work for all models. We assume that each feature is indexed using a multidimensional index structure (called the F-index). A similarity query can then be answered by executing a k-NN query on each F-index and merging the individual feature results to obtain the final results. 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’ kNN algorithm and merge results). The second and the main problem we address is how to evaluate refined queries efficiently. A naive approach is to treat a refined query just like a starting query and execute it from scratch. We observe that the refined queries are not modified drastically from one iteration to another. As a result, most of the execution cost can be saved by appropriately exploiting the information generated during the previous iterations of the query. We propose 3 techniques, namely Reuse (RU), Full Reconstruction (FR) and Selective Reconstruction (SR), that cache certain information during the execution of the previous iterations of the query and use that cached information to save the execution cost (both I/O and CPU costs) during the subsequent iterations. We define notions of I/O optimality and CPU optimality and evaluate the three schemes in terms of these criteria. We find that although RU is significantly better than the naive approach, it is not I/O optimal. So we propose FR and show that it is I/O optimal and is significantly more efficient compared to RU. However, FR is not CPU optimal. We finally propose SR and show that SR, like FR, is I/O optimal, and, under certain conditions, also CPU optimal. Even though SR is not always CPU optimal, it is always better than FR in terms of CPU cost and is hence the best technique. Our experiments show that the above techniques speed up the execution of refined queries by several orders of magnitude compared to the naive technique.
['Kaushik Chakrabarti', 'Kriengkrai Porkaew', 'Sharad Mehrotra']
Efficient Query Refinement in Multimedia Databases