Efficient computation of monochromatic reverse top-k queries

Reverse top- k queries are rank-aware problems from the view of the product manufacturers, and have gained popularity in recent studies. In this paper, we propose a novel online algorithm for processing monochromatic reverse top- k queries. The algorithm is based on dual plane transformation and is about 10 times faster than existing algorithms. We also propose a data structure RIL (Ranking Inverted List) to materialize the middle results, which enables us to utilize offline computing to accelerate online query processing. Furthermore, the RIL structure can be easily adapted to data stream environments. Extensive experiments show that our algorithm scales well with both time and space usage.