ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2014, Vol. 51 ›› Issue (10): 2206-2215.doi: 10.7544/issn1000-1239.2014.20130827

Previous Articles     Next Articles

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

Zhang Jianfeng1, Han Weihong1, Fan Hua1, Zou Peng2, Jia Yan1   

  1. 1(College of Computer, National University of Defense Technology, Changsha, 410073); 2(Academy of Equipment Command and Technology, Beijing, 101416)
  • Online:2014-10-01

Abstract: 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.

Key words: top-k query, why-not question, user’s feedback, preference refinement, query refinement

CLC Number: