Bridging dense and sparse maximum inner product search

Bruch S., Nardini F. M., Ingber A., Liberty E.

Dense vectors  Information Retrieval (cs.IR)  Clustering-based approximate nearest neighbor search  FOS: Computer and information sciences  Computer Science - Information Retrieval  Hybrid vectors  Maximum inner product search  Sparse vectors  Top-k retrieval  Sketching 

Maximum inner product search (MIPS) over dense and sparse vectors have progressed independently in a bifurcated literature for decades; the latter is better known as top- retrieval in Information Retrieval. This duality exists because sparse and dense vectors serve different end goals. That is despite the fact that they are manifestations of the same mathematical problem. In this work, we ask if algorithms for dense vectors could be applied effectively to sparse vectors, particularly those that violate the assumptions underlying top- retrieval methods. We study clustering-based approximate MIPS where vectors are partitioned into clusters and only a fraction of clusters are searched during retrieval. We conduct a comprehensive analysis of dimensionality reduction for sparse vectors, and examine standard and spherical k-means for partitioning. Our experiments demonstrate that clustering-based retrieval serves as an efficient solution for sparse MIPS. As byproducts, we identify two research opportunities and explore their potential. First, we cast the clustering-based paradigm as dynamic pruning and turn that insight into a novel organization of the inverted index for approximate MIPS over general sparse vectors. Second, we offer a unified regime for MIPS over vectors that have dense and sparse subspaces, that is robust to query distributions.

Source: ACM TRANSACTIONS ON INFORMATION SYSTEMS, vol. 42 (issue 6), pp. 1-38

Metrics