Durable Impact Period Queries on Time-varying Preference

Reverse top-k query has been proposed for market analysis for more than ten years. The query identifies users' preference whose top k choices include a given object o. Users' preference is considered static in the traditional reverse top-k query. However, preference changes over time due to factors like mood, seasons, and economic conditions. In this paper, to address the dynamic nature of preference in market analysis, a new query, called the durable impact period query, is proposed. Taking a query object o and a time period I as inputs, the durable impact period query aims to determine whether I is a durable impact period of o. This involves checking whether, for most of the time in I, more than a certain proportion of users include o in their top k choices. The impact period serves as a critical determinant in the decision making process for product launches. To process durable impact period queries efficiently, three algorithms are proposed. First, an exhaustive search algorithm is designed. Then, by transforming the durable impact period query into the halfspace range thresholding query, a pruning-based algorithm is proposed. Notably, the pruning-based algorithm demonstrates a significant reduction in time cost, often by two orders of magnitude compared to the exhaustive search algorithm. Moreover, a sampling-based approximate algorithm is presented to further enhance efficiency. Finally, extensive experiments show that the proposed algorithms are correct and efficient.