An Algorithm for Top-k Query Refinement Based on User’s Feedback

Top-k queries are mainly used to return the most important objects in the potentially huge answer space. After huge effort working on top-k query performance, an explain capability has attract more attentions in recent years. In top-k query, since users can not precisely specify their own preferences, he/she may feel frustrated with the top-k results and propose a question such that “why my expecting tuple m is not appeared in top-k results as long as tuple p has been appeared in top-k results”. To solve this problem, a novel method is proposed to answer user’s why-not question by modifying original top-k query. Firstly, an assessment model is defined to evaluate the difference between the original top-k query and the modified new query. Then based on the assessment model, a sample method is used to sample the candidate weight vectors from an accuracy subspace of weight space. After that, for each candidate weight vector, a progressive top-k algorithm is used to get the optimal new query, and the terminal conditions of the progressive top-k algorithm are improved by the assessment model. Furthermore, the new query with the best evaluated score is returned as the solution. Finally, an extensive performance study using synthetic data set is reported to verify the efficiency of the proposed algorithm.