Durable Impact Period Queries on Time-Varying Preference

The reverse top-k query was proposed for market analysis over ten years ago. The query identifies users’ preferences whose top-k choices include a given object o. Users’ preferences are considered static in the traditional reverse top-k query. However, preferences change 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 with 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.