Papers › The xyz algorithm for fast interaction search in high-dimensional data
The xyz algorithm for fast interaction search in high-dimensional data
Gian-Andrea Thanei, Nicolai Meinshausen, Rajen D. Shah
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 𝒪(p²) 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 𝒪(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 𝑥𝑦𝑧 and is implemented in the language R. We demonstrate its efficiency for application to genome-wide association studies, where more than 10¹¹ interactions can be screened in under $280$ seconds with a single-core $1.2$ GHz CPU.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
1 archive task tag without a task page not shown.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections