Revisiting Wedge Sampling for Budgeted Maximum Inner Product Search (Extended Abstract)

1 Introduction

Maximum inner product search (MIPS) is the task of, given a point set X ⊂ Rd of size n and a query point q ∈ Rd , finding the point p ∈ X such that,

MIPS and its variant top-k MIPS, which finds the topk largest inner product points with a query, are central tasks in the retrieval phase of standard collaborative filtering based recommender systems [Cremonesi et al., 2010; Koren et al., 2009]. They are also algorithmic ingredients in a variety of machine learning tasks, for instance, prediction tasks on multi-class learning [Dean et al., 2013; Russakovsky et al., 2015] and neural network [Covington et al., 2016; Spring and Shrivastava, 2017].

Modern real-world online recommender systems often deal with very large-scale data sets and a limited amount of response time. Such collaborative filtering based systems often present users and items as low-dimensional vectors. A large inner product between these vectors indicates that the items are relevant to the user preferences. The recommendation is often performed in the online manner since the user vector is updated online with ad-hoc contextual information only available during the interaction [Bachrach et al., 2014; Koenigstein et al., 2011]. A personalized recommender needs to infer user preferences based on the online user behavior, e.g. recent search queries and browsing history, as implicit feedback to return relevant results [Hu et al., 2008; Rendle et al., 2009]. Since the retrieval of recommended items is only performed online, the result of this task might not be "perfect" given a small amount of waiting time but its accuracy should be improved given more waiting time. Hence, it is challenging to not only speed up the MIPS process, but to trade the search efficiency for the search quality.

∗This is an extended abstract of work published as [Lorenzen and Pham, 2020], that won the best data mining paper award at the 2020 European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases.

Motivated by the computational bottleneck in the retrieval phase of modern recommendation systems, we study the budgeted MIPS problem, a natural extension of MIPS with an explicit computational limit for the search efficiency and quality trade-off. Our budgeted MIPS addresses the following question:

Given a data structure built in ˜O(dn) time 1 and budgeted computational operations, can we have an algorithm to return the best approximate top-k MIPS?

To measure the accuracy of approximate top-k MIPS, we use the search recall, i.e. the empirical probability of retrieving the true top-k MIPS. In our budgeted setting, we limit the time complexity of building a data structure to ˜O (dn) since when a context is used in a recommender system, the learning phase cannot be done entirely offline [Bachrach et al., 2014; Koenigstein et al., 2011]. In other words, the item vectors are also computed online and hence a high cost of constructing the data structure will significantly degrade the performance.

It is worth noting that the budgeted MIPS has been recently studied in [Yu et al., 2017] given a budget of B = ηn inner product computation where η is a small constant, e.g. 5%. Furthermore, such budget constraints on the number of computational operations or on accessing a limited number of data points are widely studied not only on search problems [Ram et al., 2012] but also on clustering [Mai et al., 2013; Shamir and Tishby, 2011] and other tasks [Fetaya et al., 2015;

1 Polylogarithmic factors, e.g. log d logn is absorbed in the ˜Onotation.

Zilberstein, 1996] when dealing with large-scale data sets.

Our work studies sampling methods for solving the budgeted MIPS since they naturally fit to the class of budgeted problems. Sampling schemes provide not only the trade-off between search quality and search efficiency but also a flexible mechanism to control this trade-off via the number of samples S and the number of inner product computations B. Our contributions are as follows:

• We revise popular sampling methods for solving MIPS, including basic sampling, wedge sampling [Cohen and Lewis, 1999], and diamond sampling [Ballard et al., 2015]. We show that diamond sampling is essentially a combination of basic sampling and wedge sampling.
• We propose dWedge, a simple but efficient deterministic variant of wedge sampling, with a flexible mechanism to govern the trade-off between search quality and efficiency for the budgeted top-k MIPS. Empirically, dWedge outperforms other competitive budgeted MIPS solvers [Neyshabur and Srebro, 2015; Yan et al., 2018; Yu et al., 2017] on popular real-world data sets.

2 SamplingMethods for Top-k MIPS

For notation, we present the point set X as a matrix X ⊂ Rn×d where each point xi corresponds to the ith row, and the query point q as a column vector q = (q1, . . . , qd)⊤. We use i ∈ [n] to index row vectors of X, i.e. xi = (xi1, . . . , xid) ∈ Rd . Since we will describe sampling methods using the columnwise matrix-vector multiplication Xq, we use j ∈ [d] to index column vectors of X, i.e. yj = (x1j, . . . , xnj)⊤ ∈ Rn . For each column j, we pre-compute its 1-norm cj = ‖yj‖1.

We briefly review sampling approaches for estimating inner products zi = x⊤i q. For simplicity, we assume that X and q are non-negative. The extension of these approaches to handle negative inputs can be found in the original paper [Lorenzen and Pham, 2020]. We consider the column-wise matrix-vector multiplication Xq as follows.

2.1 Basic Sampling

Basic sampling is a very straightforward method to estimate the inner product x⊤i q for the point xi. For any row i, we sample a column j with probability qj/‖q‖1 and return xij. Define a random variable Zi = xij , we have

The basic sampling suffers large variance when most of the contribution of x⊤i q are from a few coordinates. In particular, the variance will be significantly large when the main contributions of x⊤i q are from a few coordinates xijqj and qj are very small. Note that this basic sampling approach has been used in [Drineas et al., 2006] as an efficient sampling technique for approximating matrix-matrix multiplication.

2.2 Wedge Sampling

[Cohen and Lewis, 1999] proposed an efficient sampling approach, called wedge sampling, to approximate matrix multiplication and to isolate the largest inner products as a byproduct. Wedge sampling needs to pre-compute some statistics, including the sum of all inner products z = ∑i zi where zi = x⊤i q and 1-norm of column vectors cj = ‖yj‖1. Since we can pre-compute cj before querying, computing z = ∑j qjcj clearly takes O (d) query time. We can think of qjcj/z as the contribution ratio of the column j to the sum of inner product values z.

The basic idea of wedge sampling is to randomly sample a row index i corresponding to xi with probability zi/z. Hence, the larger the inner product zi = x⊤i q, the larger the number of occurrences of i in the sample set. Consider Equation (1), wedge sampling first samples a column j corresponding to yj with probability qjcj/z, and then samples a row i corresponding to xi from yj with probability xij/cj . By Bayes's theorem, we have

Applying wedge sampling on Xq, we obtain a sample set where each index i corresponding to xi is sampled according to an independent Bernoulli distribution with parameter pi = zi/z. To answer top-k MIPS, we execute wedge sampling and find the points with the largest counters. Given S samples and a constant cost for each sample, wedge sampling runs in O (S +min(S, n) log k) time to answer approximate top-k MIPS. If we have an additional budget of B > k inner product computation, we can compute the inner product values of the top-B points with the largest counter values for ranking. Such ranking (or post-processing) phase with an additional O (dB) cost will provide higher accuracy for top-k MIPS.

We note that since wedge sampling uses the contribution ratio qjcj/z to sample the column j, it can alleviate the effect of skewness of x⊤i q where large contributions are from a few coordinates. Hence wedge sampling achieves lower variance than the basic sampling in practice.

2.3 Diamond Sampling

[Ballard et al., 2015] proposed diamond sampling to find the largest magnitude elements from a matrix-matrix multiplication XQ without computing the final matrix directly. The method considers XQ as a weighted tripartite graph, and samples a diamond, i.e. four cycles from this graph with probability proportional to the value (XQ)2ij , in order to amplify the focus on the largest magnitude elements.

Consider a vector q as a one-column matrix Q, it is clear that diamond sampling can be applied to solve MIPS. Indeed, we will show that diamond sampling is essentially a combination of wedge sampling and basic sampling when approximating Xq. In particular, diamond sampling first makes use of wedge sampling to return a random row i corresponding to xi with probability zi/z. Given such row i, it then applies basic sampling to sample a random column j ′ with probability qj ′/‖q‖1 and return xij ′ as a scaled estimate of (x⊤i q)2 . Define a random variable Zi = xij ′ corresponding to xi, using the properties of wedge sampling and basic sampling we have

Since diamond sampling builds on basic sampling, it suffers from the same drawback as basic sampling. To answer top-k MIPS, diamond follows the same procedure as wedge hence shares the same asymptotic running time.

3 Wedge Sampling for Budgeted Top-k MIPS

We first show a concentration bound of wedge sampling, which shows that wedge requires fewer samples than diamond for approximating top-k MIPS. Then we present a drawback of wedge sampling for the budgeted MIPS and propose dWedge, a simple deterministic variant to handle this drawback. dWedge can govern the trade-off between search quality and efficiency with two parameters: the number of samples S and the number of inner product computations B.

3.1 ANewAnalysis of Wedge Sampling

This subsection presents the analysis of wedge sampling on non-negative inputs. Consider a counting histogram of n counters corresponding to n point indexes, the following theorem states the number of samples required to distinguish between two inner product values τ1 and τ2.

Theorem 1. Fix two thresholds τ1 > τ2 > 0 and suppose S ≥ 3z lnn (√τ1-√τ2)2 where z = ∑i x⊤i q. With probability at least 1 - 1n , the following holds for all pairs i1, i2 ∈ [n]: if x⊤i1 q ≥ τ1 and x⊤i2 q ≤ τ2, then counter[i1] > counter[i2].

The detailed proof can be found in [Lorenzen and Pham, 2020]. We will discuss some implications of Theorem 1.

Trade-off between search quality and efficiency. By choosing S as in Theorem 1, we have √τ1 - √τ2 ≥ √3z(lnn)/S. Assume that the top-k value is τ1, it is clear the more samples we use, the smaller gap between the top-k MIPS values and the other values we can distinguish. We note that we can compute and rank B inner products of the top-B points with the largest counter values in the ranking phase. Increasing B corresponds to increasing the gap τ1 - τ2. This means that both B and S can be used to control such trade-off.

Comparison to diamond sampling. For a fair theoretical comparison, we consider the same setting as in [Ballard et al., 2015, Theorem 4] where we want to distinguish x⊤i1 q ≥ τ and x⊤i2 q ≤ τ/4, and all entries in X and q are non-negative. 2 Applying Theorem 1, wedge sampling needs Sw ≥ 12z ln n/τ . Diamond sampling needs Sd ≥ 12K‖q‖1z ln n/τ 2 where all entries in X are at most K. Since K‖q‖1 ≥ τ for any τ, wedge requires strictly less samples than diamond.

2 The analysis of diamond sampling only works for non-negative inputs.

Algorithm 1 dWedge Sampling

Require: For each dimension j, sort data in descending order on xij and store them in the list Lj. Other pre-computed statistics z, cj, and the query q.

Ensure: A counting histogram of sampled data points.

• 1: Compute the number of samples sj = Scjqj/z for each list Lj .
• 2: for each sorted list Lj do
• 3: Select xi in the descending order of xij.
• 4: Increase the counter of xi in the histogram and the current number of samples used of Lj by ⌈sjxij/cj⌉.
• 5: If the current number of samples is larger than sj, stop iterating Lj .
• 6: end for

3.2 dWedge: A Simple Deterministic Variant for Budgeted MIPS

This subsection presents a significant drawback of wedge sampling for solving top-k MIPS with a o(n) budgeted computation. We then introduce dWedge, a simple deterministic variant to handle this drawback. For simplicity, we present our approach on non-negative X and q.

Drawback. We observe that wedge sampling first samples the column j and then samples the point xi for this column j. In other words, given a fixed number of samples S, wedge sampling allocates S samples to d columns. Each column j receives sj samples and ∑j sj = S. To ensure that wedge provides an accurate estimate, these sj samples must approximate the discrete distribution yj/‖yj‖1 well. Given the budget of S = o(n) samples, the number of samples sj of the column j is roughly S/d ≪ n in expectation. Since sj ≪ n and the data set is often dense, it is impossible to approximate the discrete distribution yj/‖yj‖1 by sj samples. Hence the performance of wedge (and hence diamond) sampling dramatically degrades in the budgeted setting.

dWedge. Observing that wedge sampling carefully distributes S samples to each dimension. Dimension j receives sj = Scjqj/z samples and hence the point xi for dimension j will receive sjxij/cj samples in expectation. Given S = o(n), we have sj ≪ n and therefore can only sample a few points for dimension j. Due to this limit, we propose to greedily sample xi with the largest xij values in column j. For each selected xi, we sample ⌈sjxij/cj⌉ times. Algorithm 1 presents our simple heuristic solution for non-negative X and q. For negative inputs, dWedge executes on the absolute values of X and q. If selected, the counter for xi is increased by sgn(xij )sgn(qj )⌈sj xij /cj ⌉.

Time complexity. It is clear that the pre-processing step takes O (dn log n) time and O (dn) additional space. dWedge sampling takes O(S) time. If S ≪ n, we can use a hash table to maintain the counting histogram. Otherwise, we use a vector of size n. The running time of dWedge for answering top-k MIPS with a post-processing B inner products is O (S + min(S, n) log B + dB).

Relation to Greedy-MIPS. Greedy-MIPS [Yu et al., 2017] exploits the upper bound xi · q ≤ dmaxj{qjxij} to construct B candidates. In principle, it greedily selects B points xi with the largest qjxij values for each dimension j, then merges them to find top-B candidates with maxj{qjxij}. While dWedge shares the same pre-processing step and greedy spirit, there is a significant difference between dWedge and Greedy. dWedge greedily estimates and differentiates the largest elements on each dimension j using sj samples. The more samples used, the more largest elements considered. This leads to a higher quality of top-B candidates and top-k MIPS.

4 Experiment

Since diamond exploits wedge, applying dWedge to diamond derives a new variant, called dDiamond. 3 Our implemented algorithms 4 include: (1) The traditional wedge (Wedge) and diamond (Diamond) sampling and the proposed solutions dWedge and dDiamond; (2) The Greedy-MIPS approach (Greedy) [Yu et al., 2017]; and (3) Brute-force algorithm with the Eigen3.3.4 library for the fast C++ matrix-vector multiplication.

We conduct experiments on standard real-world data sets, 5 including Netflix (n = 17, 770; d = 300) and Yahoo (n = 624, 961; d = 300) from [Cremonesi et al., 2010], and Gist (n = 1, 000, 000; d = 960). For Netflix and Yahoo, the item matrices are used as the data points. We randomly pick 1000 users from the user matrices to form the query sets. All randomized results are the average of 5 runs of the algorithms.

Wedge vs. Diamond. Figure 2 reveals that the proposed deterministic generator gives higher accuracy than the randomized one. dWedge and dDiamond outperformWedge and Diamond, respectively, over a wide range of S. In term of speedup, dWedge runs significantly faster than dDiamond, especially at least twice faster when S = n. Wedge variants run faster than diamond variants since diamond builds on basic sampling that requires expensive cost for random accesses.

3 This variant is not deterministic due to the randomness from the basic sampling.

4 https://github.com/NinhPham/MIPS/tree/dWedge PKDD2020

5 https://drive.google.com/drive/

dWedge vs. Greedy-MIPS. Note that dWedge's cost is about 2S/d+B inner product computations. Since we want to show that dWedge always runs as fast as Greedy but achieves higher accuracy, we use 2S/d+B inner product computations for Greedy. Given this setting, Figure 1 shows that dWedge runs faster and provides dramatically higher accuracy than Greedy on Yahoo and Gist. On Yahoo, since the screening phase of Greedy incurs remarkable cost, dWedge yields substantially higher accuracy and speedup. In order to show the benefit of the sampling phase of dWedge, we measure its performance on Gist while fixing B = 200 and varying S. Since we add additional inner product computation into the post-processing phase, dWedge and Greedy achieve similar speedup, as shown in Figure 1 (c). Figure 1 (d) shows that Greedy suffers from very small accuracy, achieving at most 40%, while dWedge achieves nearly perfect recall, i.e. 99% when S = 2n. In general, dWedge with two parameters, i.e. number of samples S and number of inner products B, governs the trade-off between search efficiency and quality more efficiently than Greedy.

dWedge vs. Locality-sensitiveHashing. Detailed comparisons between dWedge and recent advanced locality-sensitive hashing methods for budgeted top-k MIPS [Neyshabur and Srebro, 2015; Yan et al., 2018] can be found in [Lorenzen and Pham, 2020].

5 Conclusion

This paper studies top-k MIPS given a limited budget of computational operations and investigates recent advanced sampling algorithms, including wedge and diamond sampling, for solving it. We theoretically and empirically show that wedge sampling is competitive (often superior) to diamond sampling for approximating top-k MIPS regarding both efficiency and accuracy. We propose dWedge, a simple deterministic wedge-based variant for the budgeted top-k MIPS. Empirically, dWedge runs significantly faster than other competitive budgeted MIPS solvers on real-world benchmark data sets while maintaining a very competitive accuracy.