Speeding up the Xbox recommender system using a euclidean transformation for inner-product spaces

By Yoram Bachrach, Yehuda Finkelstein, Ran Gilad-Bachrach, Liran Katzir, Noam Koenigstein, Nir Nice, Ulrich Paquet. 2014

166 citations recorded by the source corpus.

Subfields: Computer Vision and Pattern Recognition, Information Systems, Information Retrieval & Search, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

In Information Systems

In Information Retrieval & Search

In Signal Processing

Citations in the corpus

Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering (2019, methodology): “Borrowing ideas from Bachrach et al. (2014); Zaheer et al. (2019), we propose to use nearest neighbor (NN) search algorithms to perform the MIPS in sublinear time as follows.”
Quantization based Fast Inner Product Search (2015, methodology): “ curves) with 3 state-of-the-art methods: (1) Signed ALSH [15], (2) L2 ALSH [15]4; and (3) Simple LSH [12]. We also compare against the PCA-tree version adapted to inner product search as proposed in [2], which has shown better results than IP-tree [13]. The proposed quantization based methods perfo”
Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS) (2014, methodology): “[2] A.”
Adaptive multi-teacher multi-level knowledge distillation (2020, background): “Besides, many real application scenarios demand high speed execution, such as recommender systems [2].”
SMYRF: Efficient Attention using Asymmetric Clustering (2020, background): “Several previous works have proposed Asymmetric LSH transformations [32, 33, 34] but focus on the case where we have a single query q and multiple keys.”
Collaborative Metric Learning (2017, background): “proposed to transform a pre-trained dot-product space into an approximate euclidean embedding that preserves the item order [2].”
Improved Asymmetric Locality Sensitive Hashing (ALSH) for Maximum Inner Product Search (MIPS) (2014, background): “Note that transformations P andQ are not unique for this task and there are other possibilities [2, 19].”
Is Retriever Merely an Approximator of Reader? (2020, methodology): “…are reported using IndexFlatIP as in the work of Karpukhin et al. (2020), and those related to RAG are reported using IndexHNSWFlat with 512 neighbors to store per node, construction time search depth of 200, search depth of 128 and L2 search metric with the max norm trick (Bachrach et al., 2014).”
Asymmetric Minwise Hashing (2014, methodology): “ore, we have 0 ≤ S0 M ≤ 1. We plot the values of ρMH−ALSH and ρsign for S0 M = {0.1, 0.2,...,0.8, 0.9, 0.95} with c. The comparison is summarized in Figure 1. Note that here we use ρSign derived from [3, 31] instead of ρSign−ALSH for convenience although the two schemes perform essentially identical”
Learning and Inference via Maximum Inner Product Search (2016, methodology): “However, it appears that the reduction presented in (Bachrach et al., 2014) and used in (Neyshabur & Srebro, 2015) is simpler, faster, and more accurate.”
To Index or Not to Index: Optimizing Exact Maximum Inner Product Search (2017, methodology): “[1] also reduce MIPS to NNS using a novel Euclidean transformation, which”
Asymmetric Minwise Hashing for Indexing Binary Inner Products and Set Containment (2015, methodology): “Note that here we use ρSign based on the slightly more convenient transformation from [3, 32] instead of ρSign−ALSH for convenience although the two schemes perform essentially the same.”
Clustering is Efficient for Approximate Maximum Inner Product Search (2015, methodology): “In contrast, PCA-Tree (Bachrach et al., 2014), the current state-of-the-art tree-based approach to MIPS, first converts MIPS to NNS by appending an additional component to the vector that ensures that all vectors are of constant norm.”
The Faiss Library (2024, unknown): “To our knowledge, some of these were already identiﬁed [45], [46], while others are new.”