An Approximate Algorithm for Maximum Inner Product Search over Streaming Sparse Vectors

Understand

Maximum Inner Product Search or top-k retrieval on sparse vectors is well-understood in information retrieval, with a number of mature algorithms that solve it exactly.

• However, all existing algorithms are tailored to text and frequency-based similarity measures.
• To achieve optimal memory footprint and query latency, they rely on the near stationarity of documents and on laws governing natural languages.
• We consider, instead, a setup in which collections are streaming -- necessitating dynamic indexing -- and where indexing and retrieval must work with arbitrarily distributed real-valued vectors.