Reverse k-ranks query

Abstract

Finding matching customers for a given product based on individual user's preference is critical for many applications, especially in e-commerce. Recently, the reverse top- k query is proposed to return a number of customers who regard a given product as one of the k most favorite products based on a linear model. Although a few "hot" products can be returned to some customers via reverse top- k query, a large proportion of products (over 90%, as our example illustrates, see Figure 2) cannot find any matching customers. Inspired by this observation, we propose a new kind of query (R- k Ranks) which finds for a given product, the top- k customers whose rank for the product is highest among all customers, to ensure 100% coverage for any given product, no matter it is hot or niche . Not limited to e-commerce, the concept of customer - product can be extended to a wider range of applications, such as dating and job-hunting. Unfortunately, existing approaches for reverse top- k query cannot be used to handle R- k Ranks conveniently due to infeasibility of getting enough elements for the query result. Hence, we propose three novel approaches to efficiently process R- k Ranks query, including one tree-based method and two batch-pruning-based methods. Analysis of theoretical and experimental results on real and synthetic data sets illustrates the efficacy of the proposed methods.