# The xyz algorithm for fast interaction search in high-dimensional data

arXiv: https://arxiv.org/abs/1610.05108 · HTML: https://mlsanity.com/paper/1610.05108/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Oct 2016.

## Built on by (most cited first, 4 of 4)

- [Discovering Categorical Main and Interaction Effects Based on Association Rule Mining](https://mlsanity.com/paper/2104.04728/) (2021)
- [Random Intersection Chains](https://mlsanity.com/paper/2104.04714/) (2021)
- [BELIEF in Dependence: Leveraging Atomic Linearity in Data Bits for Rethinking Generalized Linear Models](https://mlsanity.com/paper/2210.10852/) (2022)
- [Online Interaction Detection for Click-Through Rate Prediction](https://mlsanity.com/paper/2106.15400/) (2021)

## Abstract (arXiv)

When performing regression on a dataset with p variables, it is often of interest to go beyond using main linear effects and include interactions as products between individual variables. For small-scale problems, these interactions can be computed explicitly but this leads to a computational complexity of at least O(p2) if done naively. This cost can be prohibitive if p is very large. We introduce a new randomised algorithm that is able to discover interactions with high probability and under mild conditions has a runtime that is subquadratic in p. We show that strong interactions can be discovered in almost linear time, whilst finding weaker interactions requires O(pα) operations for 1 < α < 2 depending on their strength. The underlying idea is to transform interaction search into a closestpair problem which can be solved efficiently in subquadratic time. The algorithm is called mathitxyz and is implemented in the language R. We demonstrate its efficiency for application to genome-wide association studies, where more than 1011 interactions can be screened in under 280 seconds with a single-core 1.2 GHz CPU.