  We propose a novel dimensionality reduction method for 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 dimensions associated with the extreme values of the query signature
are enough to estimate inner products. Since CEOs only uses the sign of a small
subset of the query signature for estimation, we can precompute all inner
product estimators accurately before querying. These properties yield a
sublinear MIPS algorithm with an exponential indexing space complexity. We show
that our exponential space is optimal for the $(1 + \epsilon)$-approximate MIPS
on a unit sphere. The search recall of CEOs can be theoretically guaranteed
under a mild condition.
  To deal with the exponential space complexity, we propose two practical
variants, including sCEOs-TA and coCEOs, that use linear space for solving
MIPS. sCEOs-TA exploits the threshold algorithm (TA) and provides superior
search recalls to competitive MIPS solvers. coCEOs is a data and dimension
co-reduction technique and outperforms sCEOs-TA on high recall requirements.
Empirically, they are very simple to implement and achieve at least 100x
speedup compared to the bruteforce search while returning top-10 MIPS with
accuracy at least 90% on many large-scale data sets.
