Finding the most influential product under distribution constraints through dominance tests

摘要

Market analysis is crucial for companies to remain invincible in the increasingly fierce market competition. A typical application is to find the most influential product, which attracts the largest number of customers, from a collection of candidate products. Previous work assumes a random distribution of the candidates. However, in many cases, there is a set of constraints on the distribution of candidate products. In this paper, we study the most influential product problem under constraints of the distribution. We model the constraints as both non-linear and linear constraints, where the candidate products reside in a hyper-rectangle and hyper-plane of the data space, respectively. We capitalize on reverse skyline queries to define the most influential product as the product with the largest reverse skyline set. We propose a general framework to solve the problem efficiently by taking advantage of candidate distributions. More specifically, we introduce a constraint-based filtering scheme, which prunes searching space and enables quick identification of some reverse skyline points, through pre-processing based on distribution constraints. We also propose a distance-based ordering technique, such that the processing results of a candidate can be utilized for data pruning of subsequent candidates. By combining the filtering scheme and ordering technique, we present two algorithms for handling different constraint models. Our experimental results with both real and synthetic datasets demonstrate the effectiveness and efficiency of our proposed algorithms.