Efficient And Exact Why-not Reverse Top-k Query Processing

Top-k query and reverse top-k query are two of the most important queries in database system.Given a user preference vector and a product data set,Top-k query can find k products that a customer is most interested in;Given a target product,a product data set and a user preference vector set,reverse top-k query can find potential customers who treat the target product as one of the top-k favorite products.Reverse top-k query has a wide range of applications such as market analysis.When a product seller uses reverse top-k query to find potential customers of a target product,if he(she)find that some old customers do not appear in the query results,he(she)must wonder "Why not?",and hope to know why these customers do not appear in the query results? And how to make these customers appear in the query results? This is a typical application scenario of why-not reverse top-k query,which is also one of the motivations of this research topic.This paper aims to design an efficient and exact algorithm to provide suggestions to the seller for query modification,so that the target customers can appear in the reverse top-k query results in the modified query.Meanwhile,let the product seller pay lowest cost.This paper mainly researches on why-not reverse top-k query,and solves this problem by the following two methods:(1)modifying the user preference vector set W_m,(2)modifying the user preference vector set W_m and parameter k.For modifying W_m problem:this dissertation proposes P-CTA-I algorithm,which completely indices user preference space and then searches for the optimal solution.Then we propose BFS-I algorithm which improves the performance of P-CTA-I algorithm by optimizing the search order and only constructing necessary part of the user preference space according to the problem characteristics.Furthermore,the RH-I algorithm uses a priority queue to index the user preference space.And a hyperplane filtering technology is used to improve the performance of the algorithm.For modifying W_m and k problem: this dissertation reduces it to modifying W_m problem,and then proposes P-CTA-II algorithm,BFS-II algorithm,and RH-II algorithm according to the problem characteristics.Finally,extensive experimental evaluations using both real and synthetic data sets are conducted to verify the effectiveness of the proposed optimizations and efficiency of proposed algorithms.The key contributions of this paper are summarized as follows:(1)We proposean efficient and exact algorithm on modifying W_mproblem.To our best knowledge,there is no prior work on this problem;(2)We propose an efficient and exact algorithm on modifying W_m and k.To our best knowledge,there is no exact algorithm on this problem before;(3)We propose optimization to improve the performance of the proposed algorithm;(4)We conduct extensive experiments with both real and synthetic dataset to demonstrate the efficiency of the proposed algorithm.