Abstract
Given a set of products and users, the Bichromatic Reverse Skyline query from a product returns a set of users who consider this product as one of their skyline points. In recent researches on addressing bichromatic reverse skyline query, the state-of-the-art algorithm is the BRS algorithm [WTW09], which utilizes some properties of R-tree index structure to speed up the processing time by reducing IO accesses. BRS finds the reverse skyline of one product rapidly. In this thesis, we make the first attempt to study a new problem on extracting the k most popular products by reverse skyline retrieval. If using BRS to solve this problem, BRS has to be applied to every product, and the reverse skyline of all products generated has to be sorted such that the top k products are the results. Different from the above method, we design an algorithm to directly estimate which k products have the most reverse skyline, avoiding calculating some products that could not be the answers in advance. We combine the properties of R-tree structure and the computed information to speed up the estimating time. Then we compare our method with a basic method and the BRS algorithm by many experiments. As in conclusion, we get a good performance when the amount of users is big.