Simple Yet Efficient Algorithms for Maximum Inner Product Search via Extreme Order Statistics

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.