Reverse top-k queries and the most influential products

Nowadays, most applications return to the user a limited set of ranked results based on the individual user´s preferences. From the perspective of a manufacturer, it is imperative that her products appear in the highest ranked positions for many different user preferences, otherwise the product is not visible to potential customers. This paper defines a query type, namely the reverse top-k query, that covers this requirement: “Given a potential product, which are the user preferences that make this product belong to the top-k query result set?.” Reverse top-k queries identifies the top-k most influential products to customers, where influence is defined as the cardinality of the reverse top-k result. This definition of influence is useful for market analysis, since it is directly related to the number of customers that value a particular product and consequently to its visibility and impact in the market. Further this paper shows the implication of each dimension on the design of the underlying techniques and the efficiency of the algorithms.