  Click-Through Rate prediction aims to predict the ratio of clicks to
impressions of a specific link. This is a challenging task since (1) there are
usually categorical features, and the inputs will be extremely high-dimensional
if one-hot encoding is applied, (2) not only the original features but also
their interactions are important, (3) an effective prediction may rely on
different features and interactions in different time periods. To overcome
these difficulties, we propose a new interaction detection method, named Online
Random Intersection Chains. The method, which is based on the idea of frequent
itemset mining, detects informative interactions by observing the intersections
of randomly chosen samples. The discovered interactions enjoy high
interpretability as they can be comprehended as logical expressions. ORIC can
be updated every time new data is collected, without being retrained on
historical data. What's more, the importance of the historical and latest data
can be controlled by a tuning parameter. A framework is designed to deal with
the streaming interactions, so almost all existing models for CTR prediction
can be applied after interaction detection. Empirical results demonstrate the
efficiency and effectiveness of ORIC on three benchmark datasets.
