Random projection (RP) is a powerful dimension reduction technique widely used in analysis of high dimensional data. We demonstrate how this technique can be used to improve the computational efficiency of gravitational wave searches from compact binaries of neutron stars or black holes. Improvements in low-frequency response and bandwidth due to detector hardware upgrades pose a data analysis challenge in the advanced LIGO era as they result in increased redundancy in template databases and longer templates due to a higher number of signal cycles in band. The RP-based methods presented here address both these issues within the same broad framework. We first use RP for an efficient, singular value decomposition-inspired template matrix factorization and develop a geometric intuition for why this approach works. We then use RP to calculate approximate time-domain correlations in a lower dimensional vector space. For searches over parameters corresponding to nonspinning binaries with a neutron star and a black hole, a combination of the two methods can reduce the total on-line computational cost by an order of magnitude over a nominal baseline. This can, in turn, help free up computational resources needed to go beyond current spin-aligned searches to more complex ones involving generically spinning waveforms.