We present a novel dimensionality reduction method for the approximate maximum inner product search (MIPS), named CEOs, based on the theory of concomitants of extreme order statistics. Utilizing the asymptotic behavior of these concomitants, we show that a few projections associated with the extreme values of the query signature are enough to estimate inner products. This yields a sublinear approximate MIPS algorithm with search recall guarantee under a mild condition. The indexing space is exponential but optimal for the approximate MIPS on a unit sphere.

To deal with the exponential space complexity, we present practical variants, including CEOs-TA and coCEOs, that use near-linear indexing space and time. CEOs-TA exploits the threshold algorithm (TA) and provides superior search recalls to LSH-based MIPS solvers. coCEOs is a new data and dimension co-reduction technique that outperforms CEOs-TA and other competitive methods. Empirically, they are simple to implement and achieve at least 100x speedup compared to the bruteforce search while returning top-10 MIPS with recall of at least 90% on many large-scale data sets.