arXiv:1610.03317v1 [] 11 Oct 2016

A Greedy Approach for Budgeted Maximum Inner Product Search
Hsiang-Fu Yu
The University of Texas at Austin
rofuyu@cs.utexas.edu

Cho-Jui Hsieh
The University of California, Davis
chohsieh@cs.ucdavis.edu

Qi Lei
The University of Texas at Austin
leiqi@ices.utexas.edu

Inderjit S. Dhillon
The University of Texas at Austin
inderjit@cs.utexas.edu

Abstract
Maximum Inner Product Search (MIPS) is an important task in many machine learning applications
such as the prediction phase of a low-rank matrix factorization model for a recommender system. There
have been some works on how to perform MIPS in sub-linear time recently. However, most of them
do not have the flexibility to control the trade-off between search efficient and search quality. In this
paper, we study the MIPS problem with a computational budget. By carefully studying the problem
structure of MIPS, we develop a novel Greedy-MIPS algorithm, which can handle budgeted MIPS by
design. While simple and intuitive, Greedy-MIPS yields surprisingly superior performance compared to
state-of-the-art approaches. As a specific example, on a candidate set containing half a million vectors
of dimension 200, Greedy-MIPS runs 200x faster than the naive approach while yielding search results
with the top-5 precision greater than 75%.

1

Introduction

In this paper, we study the computational issue in the prediction phase for many matrix factorization based
latent embedding models in recommender systems, which can be mathematically formulated as a Maximum
Inner Product Search (MIPS) problem. Specifically, given a large collection of n candidate vectors

H = hj ∈ Rk : 1, . . . , n

and a query vector w ∈ Rk , MIPS aims to identify a subset of candidates that have top largest inner product
values with w. We also denote H = [h1 , . . . , hj , . . . , hn ]> as the candidate matrix. A naive linear search
procedure to solve MIPS for a given query w requires O(nk) operations to compute n inner products and
O(n log n) operations to obtain the sorted ordering of the n candidates.1
Recently, MIPS has drawn a lot of attention in the machine learning community. Matrix factorization
(MF) based recommender system [7, 10] is one of the most important applications. In an MF based recommender system, each user i is associated with a vector wi of dimension k, while each item j is associated
with a vector hj of dimension k. The interaction (such as preference) between a user and an item is modeled
by the value of the inner product between wi and hj . It is clear that identifying top-ranked items in such
a system for a user is exactly a MIPS problem. Because both the number of users (the number of queries)
and the number of items (size of vector pool in MIPS) can easily grow to millions, a naive linear search
is extremely expensive; for example, to compute the preference for all m users over n items with latent
embeddings of dimension k in a recommender system requires at least O(mnk) operations. When both m
and n are large, the prediction procedure is extremely time consuming; it is even slower than the training

1 When only the largest B elements are required, the sorting procedure can be reduced to O(n + B log B) on average using
a selection algorithm [6].

1

procedure used to obtain the m + n embeddings, which costs only O(|Ω|k) operations per iteration. Taking
the yahoo-music dataset as an example, we have m = 1M , n = 0.6M , |Ω| = 250M , and
mn = 600B  250M = |Ω|.
As a result, the development of efficient algorithms for MIPS is needed in large-scale recommender systems.
In addition, MIPS can be found in many other machine learning applications, such as the prediction for
a multi-class or multi-label classifier [15, 18], an object detector, a structure SVM predicator, and many
others.
There is a recent line of research on accelerating MIPS for large n, such as [2, 3, 9, 11–13]. However, most
of them do not have the flexibility to control the trade-off between search efficiency and search quality in the
prediction phase. In this paper, we consider the budgeted MIPS problem, which is a generalized version of
the standard MIPS with a computation budget: how to generate a set of top-ranked candidates under a given
budget on the number of inner products one can perform. By carefully studying the problem structure of
MIPS, we develop a novel Greedy-MIPS algorithm, which handles budgeted MIPS by design. While simple
and intuitive, Greedy-MIPS yields surprisingly superior performance compared to existing state-of-the-art
approaches.
Contributions. Our contributions can be summarized as follows:
• We carefully study the MIPS problem and develop Greedy-MIPS, which is a novel algorithm without
any nearest neighbor search reduction that is essential in many state-of-the-art approaches [2, 11, 13].
• Greedy-MIPS is orders of magnitudes faster than many state-of-the-art MIPS approaches to obtain a
desired search performance. As a specific example, on the yahoo-music data sets with n = 624, 961
and k = 200, Greedy-MIPS runs 200x faster than the naive approach and yields search results with
the top-5 precision more than 75%, while the search performance of other state-of-the-art approaches
under the similar speedup drops to less than 3% precision.
• Greedy-MIPS supports MIPS with a budget, which brings the ability to control of the trade-off between
computation efficiency and search quality in the prediction phase. To the best of our knowledge,
among existing MIPS approaches, only the sampling approaches proposed in [3, 5] support the similar
flexibility under a limited situation where all the candidates and query vectors are non-negative.
Organization. We first review existing fast MIPS approaches in Section 2 and introduce the budgeted
MIPS problem in Section 3. In Section 4, we propose a novel greedy budgeted MIPS approach called
Greedy-MIPS. We then show the empirical comparison in Section 5 and conclude this paper in Section 6.

2

Existing Approaches for Fast MIPS

Because of its wide applicability, several algorithms have been proposed to design efficient algorithms for
MIPS. Most of existing approaches consider to reduce the MIPS problem to the nearest neighbor search
problem (NNS), where the goal is to identify the nearest candidates of the given query, and apply an existing
efficient NNS algorithm to solve the reduced problem [1, 2, 11, 13, 14]. [2] is the first MIPS work which
adopts such a MIPS-to-NNS reduction. Variants MIPS-to-NNS reduction are also proposed in [13, 14].
Experimental results in [2] show the superiority of the NNS reduction over the traditional branch-and-bound
search approaches for MIPS [9, 12].
Fast MIPS approaches with sampling schemes have become popular recently [3, 5]. Various sampling
schemes have been proposed to handle MIPS problem with different constraints. We will briefly review two
popular sampling schemes in Section 2.2.

2

z

(
ĥ2

h3

x2 + y 2 + z 2 = M,
q
2
z = M − kh2 k

ĥ3
y

h2

y

h1

w

ŵ

x2 + y 2 = M

ĥ1

x2 + y 2 = M, z = 0

x

x

(a) Original MIPS in R2 .

(b) Reduced NNS in R3 .

Figure 1: MIPS-to-NN reduction. In 1(a), all the candidate vectors {hj } and the query vector w are
in R2 . h2 is the nearest neighbor of w, while h1 is the vector yielding the maximum value of the inner
>
product with
q w. In 1(b), the reduction proposed in [2] is applied to w and {hj }: ŵ = [w; 0] and
2

2

M − khj k ]> , ∀j, where M = maxj khj k . All the transformed vectors are in the 3-dimensional
√
sphere with radius M . As a result, the nearest neighbor of ŵ in this transformed 3-dimensional NNS
problem, ĥ1 , corresponds to the vector h1 which yields the maximum inner product value with w in the
original 2-dimensional MIPS problem.

ĥj = [hj ;

2.1

Approaches with Nearest Neighbor Search Reduction

We briefly introduce the concept of the reduction proposed in [2]. First, we consider the relationship between
the Euclidean distance and the inner product:
2

2

2

2

2

2

kw − hj1 k = kwk + khj1 k − 2w> hj1

kw − hj2 k = kwk + khj2 k − 2w> hj2 .

When all the candidate vectors hj share the same length; that is,
kh1 k = kh2 k = · · · = khn k,
the MIPS problem is exactly the same as the NNS problem because
kw − hj1 k > kw − hj2 k ⇐⇒ w> hj1 < w> hj2

(1)

when khj1 k = khj2 k. However, when khj1 k =
6 khj2 k, (1) no longer holds. See Figure 1(a) for an example
where not all the candidate vectors have the same length. We can see that h1 is the candidate vector yielding
the maximum inner product with w, while h2 is the nearest neighbor candidate.
To handle the situation where candidates have different lengths, [2] proposes the following transform to
reduce the original MIPS problem with H and w in a k dimensional space to a new NNS problem with

3

n
o
Ĥ = ĥ1 , . . . , ĥn and ŵ in a k + 1 dimensional space:
>

ŵ = [w; 0] ,
>

q
2
, ∀j = 1, . . . , n,
ĥj = hj ; M − khj k

(2)

where M is the maximum squared length over the entire candidate set H:
2

M = max khj k .
j=1,...,n

First, we can see that with the above transform, ĥj
ĥj

2

2

= M for all j:

2

2

= khj k + M − khj k = M, ∀j.

Then, for any j1 6= j2 , we have
ŵ − ĥj1 < ŵ − ĥj2
2

2

⇐⇒ M + kwk − 2w> hj1 < M + kwk − 2w> hj2
⇐⇒ w> hj1 > w> hj2 .

With the above relationship, the original k-dimensional MIPS problem is equivalent to the transformed k + 1
dimensional NNS problem. In Figure 1(b), we show the transformed NNS problem for the original MIPS
problem presented in Figure 1(a).
In [14], another MIPS-to-NNS reduction has been proposed. The high level idea is to apply a transformation to H such that all the candidate vectors roughly have the same length by appending additional k̄
dimensions. In the procedure by [14], all the hj vectors are assumed (or scaled) to have khj k ≤ U, ∀j, where
U < 1 is a positive constant. Then the following transform is applied to reduce the original k-dimensional
MIPS problem to a new NNS problem with (k + k̄)-dimensional vectors Ĥ and ŵ defined as:
>

ŵ = [w; 0k̄ ]
h
i>
21
22
2k̄
ĥj = hj ; 1/2 − khj k ; 1/2 − khj k ; . . . ; 1/2 − khj k
,

(3)

where 0k̄ is a zero vector of dimension k̄. Because U < 1, [14] shows that with the transform (3), we
have ĥj

2

= k̄/4 + khj k

2k̄+1

, with the second term vanishing as k̄ → ∞. Thus, all the candidates ĥj

approximately have the same length. We can see the idea behind (3) is similar to (2): transforming H to Ĥ
such that all the candidates have the same length. Note that (2) achieves this goal exactly while (3) achieves
this goal approximately. Both transforms show a similar empirical performance in [11].
There are many choices to solve the transformed NNS problem after the MIPS-to-NN reduction has been
applied. In [11, 13, 14], various locality sensitive hashing schemes have been considered. In [2], a PCA-tree
based approach is proposed, and shows better performance than LSH-based approaches, which is consistent
to the empirical observations in [1] and our experimental results shown in Section 5. In [1], a simple K-means
clustering algorithm is proposed to handled the transformed NNS problem.

2.2

Sampling-based Approaches

The idea of the sampling-based MIPS approach is first proposed in [5] as an approach to perform approximate
matrix-matrix multiplications. Its applicability on MIPS problems is studied very recently [3]. The idea
4

behind a sampling-based approach called Sample-MSIPS, is about to design an efficient sampling procedure
such that the j-th candidate is selected with probability p(j):
p(j) ∼ h>
j w.
In particular, Sample-MSIPS is an efficient scheme to sample (j, t) ∈ [n] × [k] with the probability p(j, t):
p(j, t) ∼ hjt wt .
Each time a pair (j, t) is sampled, we increase the count for the j-th item by one. By the end of the sampling
process, the spectrum of the counts forms an estimation of n inner product values. Due to the nature of the
sampling approach, it can only handle the situation where all the candidate vectors and query vectors are
nonnegative.
Diamond-MSIPS, a diamond sampling scheme proposed in [3], is an extension of Sample-MSIPS to handle
the maximum squared inner product search problem (MSIPS) where the goal is to identify candidate vectors
2
>
with largest values of h>
j w . If both w and H are nonnegative or hj w ≥ 0, ∀j, MSIPS can be used to
generate the solutions for MIPS. However, the solutions to MSIPS can be very different from the solutions
to MIPS in general. For example, if all the inner product values are negative, the ordering for MSIPS is the
exactly reverse ordering induced by MIPS. Here we can see that the applicability of both Sample-MSIPS and
Diamond-MSIPS to MIPS is very limited.

3

Budgeted Maximum Inner Product Search

The core idea behind the fast approximate MIPS approaches is to trade the search quality for the shorter
query latency: the shorter the search latency, the lower the search quality. In most existing fast MIPS
approaches, the trade-off depends on the approach-specific parameters such as the depth of the PCA tree in
[2] or the number of hash functions in [11, 13, 14]. Such approach-specific parameters are usually required
to construct approach-specific data structures before any query is given, which means that the trade-off is
somewhat fixed for all the queries. Particularly, the computation cost for all the query requests is fixed.
However, in many real-world scenarios, each query request might have a different computational budget,
which raises the question: Can we design a fast MIPS approach which supports the dynamic adjustment of
the trade-off in the query phase?
In this section, we formally define the budgeted MIPS problem which is an extension of the standard
MIPS problem with a computational budget as a parameter given in the query phase. We first summarize
the essential components for fast MIPS approaches in Section 3.1 and give the problem definition of budgeted
MIPS in Section 3.2.

3.1

Essential Components for Fast MIPS Approaches

Before diving into the details of budgeted MIPS, we first review the essential components in fast MIPS
algorithms:
• Before any query request:
– Query-Independent Data Structure Construction: A pre-processing procedure is performed on the
entire candidate sets to construct an approach-specific data structure D to store information about
H, such as the LSH hash tables [11, 13, 14], space partition trees (e.g., KD-tree or PCA-tree [2]),
or cluster centroids [1].

• For each query request:

– Query-dependent Pre-processing: In some approaches, a query dependent pre-processing is needed.
For example, a vector augmentation is required in all approaches with the MIPS-to-NNS reduction
[1, 2, 11, 13]. In addition, [2] also requires another normalization. TP is used to denote the time
complexity of this stage.
5

– Candidate Screening: In this stage, based on the pre-constructed data structure D, an efficient
procedure is performed to filter candidates such that only a subset of candidates C(w) ⊂ H is
selected. In a naive linear approach, no screening procedure is performed, so C(w) simply contains
all the n candidates. For a tree-based structure, C(w) contains all the candidates stored in the
leaf node of the query vector. In a sampling-based MIPS approach, an efficient sampling scheme
is designed to generate highly possible candidates to form C(w). TS denotes the computational
cost of the screening stage.
– Candidate Ranking: An exact ranking is performed on the selected candidates in C(w) obtained
from the screening stage. This involves the computation of |C(w)| inner products and the sorting
procedure among these |C(w)| values. The overall time complexity TR is
TR = O(|C(w)|k + |C(w)| log|C(w)|).
The per-query computational cost TQ is
TQ = TP + TS + TR .
It is clear that the candidate screening stage is the key component for a fast MIPS approach. In terms of
the search quality, the performance highly depends on whether the screening procedure can identify highly
possible candidates. In terms of the query latency, the efficiency highly depends on the size of C(w) and how
fast to generate C(w). The major difference between various fast MIPS approaches is the choice of the data
structure D and the corresponding screening procedure.

3.2

Budgeted MIPS: Problem Definition

Budgeted maximum inner product search is an extension of the standard approximate MIPS problem with a
computation budget: how to generate top-ranked candidates under a given budget on the number of inner
product operations one can perform. Budgeted MIPS has a wide applicability. For example, a real-time
recommender system must provide a list of recommended items for its users in a very short response time.
Note that the cost for the candidate ranking (TR ) is inevitable in the per-query cost: TQ = TP + TS + TR .
A viable approach to support budgeted MIPS must include a screening procedure which satisfies the following
requirements:
• the flexibility to control the size of C(w) in the candidate screening stage such that |C(w)| ≤ B, where
B is a given budget, and
• an efficient screening procedure to obtain C(w) in O(Bk) time such that the overall per-query cost is
TQ = O(Bk + B log B).
As mentioned earlier, most recently proposed efficient algorithms such as PCA-MIPS [2] and LSH-MIPS [11,
13, 14] adopt the approach to reduce the MIPS problem to an instance of NNS problem, and apply various
search space partition data structures or techniques (e.g., LSH, KD-tree, or PCA-tree) designed for NNS to
index the candidates H in the query-independent pre-processing stage. As the construction of D is query
independent, both the search performance and the computation cost are fixed when the construction is
done. For example, the performance of a PCA-MIPS depends on the depth of the PCA-tree. Given a query
vector w, there is no control to the size of C(w) in the candidate generating phase. LSH-based approaches
also have the similar issue. As a result, it is not clear how to generalize PCA-MIPS and LSH-MIPS in a
principled way to handle the situation with a computational budget: how to reduce the size of C(w) under
a limited budget and how to improve the performance when a larger budget is given.
Unlike other NNS-based algorithms, the design of Sample-MSIPS naturally enables it to support budgeted
MIPS for a nonnegative candidate matrix H and a nonnegative query w. Recall that the core idea behind
Sample-MSIPS is to draw a sample candidate j among n candidates such that
p(j) ∝ h>
j w.
6

The more the number of samples, the lower the variance of the estimated frequency spectrum. Clearly,
Sample-MSIPS has the flexibility to control the size of C(w), and thus is a viable approach for the budgeted
MIPS problem. However, Sample-MSIPS works only on the situation where the entire H and w are nonnegative. Diamond-MSIPS has the similar issue.

4

Greedy-MIPS: A Novel Approach for Budgeted MIPS

In this section, we carefully study the problem structure of MIPS and develop a simple but novel algorithm
called Greedy-MIPS, which handles budgeted MIPS by design. Unlike the most recent approaches [1, 2, 11,
13, 14], Greedy-MIPS is an approach without any reduction to a NNS problem. Moreover, Greedy-MIPS is
a viable approach for the budgeted MIPS problem without the non-negativity limitation inherited in the
sampling approaches.
As mentioned earlier that the key component for a fast MIPS approach is the algorithm used in the
candidate screening phase. In budgeted MIPS, for any given budget B and query w, an ideal procedure
for the candidate screening phase costs O(Bk) time to generate C(w) which contains the B items with the
largest B inner product values over the n candidates in H. The requirement on the time complexity O(Bk)
implies that the procedure is independent from n = |H|, the number of candidates in H. One might wonder
whether such an ideal procedure exists or not. In fact, designing such an ideal procedure with the requirement
to generate the largest B items in O(Bk) time is even more challenging than the original budgeted MIPS
problem.

4.1

A Motivating Example for Greedy-MIPS

Although the existence of an ideal procedure for a general budgeted MIPS problem seems to be impossible,
we demonstrate that an ideal approach exists for budgeted MIPS when k = 1. It is not hard to observe that
Property 1 holds for any given H = {h1 , . . . , hn | hj ∈ R}:
Property 1. For any nonzero query w ∈ R and any budget B > 0, there are only two possible results for
that top B inner products between w and H:
w > 0 ⇒ Largest B elements in H,

w < 0 ⇒ Smallest B elements in H.

This property leads to the following simple approach, which is an ideal procedure for the budgeted MIPS
problem when k = 1:
• Query-independent data structure: a sorted list of indices of H: s[r], r = 1, . . . , n such that s[r] stores
the index to the r-th largest candidate. That is
hs[1] ≥ hs[2] ≥ · · · ≥ hs[n] ,
• Candidate screening phase: for any given w 6= 0 and B > 0,
(
first B elements: {s[1], . . . , s[B]}
return
last B elements: {s[n], . . . , s[n − B + 1]}

if w > 0,
if w < 0

as the indices of the exact largest-B candidates.
Note that for this simple scenario (k = 1), neither the query dependent pre-processing nor the candidate
ranking is needed. Thus, the overall time complexity per query is TQ = O(B). We can see that Property 1 is
the key to the correctness of the above procedure. Nevertheless, it is not clear how to generalize Property 1
for MIPS problems with k ≥ 2. Fortunately, we can directly utilize the fact that Property 1 holds for k = 1
to design an efficient greedy procedure for the candidate screening when k ≥ 2.
7

Z > = diag(w)H > : zjt = hjt wt , ∀j, t
joint ranking
π(j, t|w)

+

z11

z21

z31

z41

z51

z61

z71

z12

z22

z32

z42

z52

z62

z72

z13

z23

z33

z43

z53

z63

z73

h1>w h2>w h3>w h4>w h5>w h6>w h7>w

conditional ranking
πt (j|w)

marginal ranking
π(j|w)

Figure 2: nk multiplications in a naive linear MIPS approach.

4.2

A Greedy Procedure to Candidate Screening

To better describe the idea of the proposed algorithm Greedy-MIPS, we consider the following definition (4):

Definition 1. The rank of an item x among a set of items X = x1 , . . . , x|X | is defined as
rank(x | X ) :=

|X |
X
j=1

I[xj ≥ x],

(4)

where I[·] is the indicator function. A ranking induced by X is a function π(·) : X → {1, . . . , |X |} such that
π(xj ) = rank(xj | X ) ∀xj ∈ X .
One way to store a ranking π(·) induced by X is by a sorted index array s[r] of size |X | such that
π(xs[1] ) ≤ π(xs[2] ) ≤ · · · ≤ π(xs[|X |] ).
We can see that s[r] stores the index to the item x with π(x) = r.
In order to design an efficient candidate screening procedure, we carefully study the operations required
for MIPS. In the
MIPS approach, nk multiplication operations are required to obtain n inner
 naive linear
>
product values h>
1 w, . . . , hn w . To understand and analyze the computation required for MIPS, we define
an implicit matrix Z ∈ Rn×k :
Z = H diag(w),
where diag(w) ∈ Rk×k is a matrix with w as it diagonal. The (j, t) entry of Z denotes the multiplication
operation zjt = hjt wt and zj = diag(w)hj denotes the j-th row of Z. In Figure 2, we use Z > to demonstrate
the implicit matrix. The implicit matrix Z is query dependant, that is, the values of Z depend on the query
vector w. Note that n inner product values can be obtained by taking the column-wise summation of Z > .
In particular, we have
k
X
>
hj w =
zjt , j = 1, . . . , n.
t=1

Thus, the ranking induced by the n inner product values can be characterized by the marginal ranking
π(j|w) defined on the implicit matrix Z as follows:
( k
)!
k
k
X
X
X
π(j|w) := rank
zjt
z1t , · · · ,
znt
(5)
= rank

t=1
>
hj w

|



t=1
t=1

>
>
h1 w, . . . , hn w .

As mentioned earlier, it is hard to design an ideal candidate screening procedure which generates C(w)
based on the marginal ranking. Because the main goal for the candidate screening phase is to quickly
8

identify candidates which are highly possible to be top-ranked items, it suffices to have an efficient procedure
generating C(w) by an approximation ranking. Here we propose a greedy heuristic ranking:
 k
n k
o
k
π̄(j|w) := rank max zjt
max z1t , · · · , max znt ,
(6)
t=1

t=1

t=1

which is obtained by replacing the summation terms in (5) by max operators. The intuition behind this
heuristic is that the largest element of zj multiplied by k is an upper bound of h>
j w:
h>
j w =

k
X
t=1

 k

zjt ≤ k max zjt .
t=1

Thus, π̄(j|w), which is induced by such an upper bound of h>
j w, could be a reasonable approximation
ranking for the marginal ranking π(j|w).
Next we design an efficient procedure which generates C(w) according to the ranking π̄(j|w) defined in
(6). First, based on the relative orderings of {zjt }, we consider the joint ranking and the conditional ranking
defined as follows:
• Joint ranking: π(j, t|w) is the exact ranking over the nk entries of Z.
π(j, t|w) := rank(zjt | {z11 , . . . , znk }).
• Conditional ranking: πt (j|w) is the exact ranking over the n entires of the t-th row of Z > .
πt (j|w) := rank(zjt | {z1t , . . . , znt }).
See Figure 2 for an illustration for both rankings. Similar to the marginal ranking, both joint and conditional
rankings are query dependent.
Observe that, in (6), for each j, only a single maximum entry of Z, maxkt=1 zjt , is considered to obtain the
ranking π̄(j|w). To generate C(w) based on π̄(j|w), we can iterate (j, t) entries of Z in a greedy sequence
such that (j1 , t1 ) is visited before (j2 , t2 ) if zj1 t1 > zj2 t2 , which is exactly the sequence corresponding to the
joint ranking π(j, t|w). Each time an entry (j, t) is visited, we can include the index j into C(w) if j ∈
/ C(w).
In Theorem 1, we show that the sequence to include a newly observed j into C(w) is exactly the sequence
induced by the ranking π̄(j|w) defined in (6).
Theorem 1. For all j1 and j2 such that π̄(j1 |w) < π̄(j2 |w), j1 will be included into C(w) before j2 if we
iterate (j, t) pairs following the sequence induced by the joint ranking π(j, t|w).
Proof. Let t1 = arg maxkt=1 zj1 t and t2 = arg maxkt=1 zj2 t . By the definition of t1 , we have π(j1 , t1 |w) <
π(j1 , t|w), ∀t 6= t1 . Thus, (j1 , t1 ) will be first entry among {(j1 , 1), . . . , (j1 , k)} to be visited in the sequence corresponding to the joint ranking π(j, t|w). Similarly, (j2 , t2 ) will be the first visited entry among
{(j2 , 1, ), . . . , (j2 , k)}. We also have
π̄(j1 |w) < π̄(j2 |w) ⇒ zj1 t1 > zj2 t2 ⇒ π(j1 , t1 |w) < π(j2 , t2 |w).
Thus, j1 will be included into C(w) before j2 .
At first glance, generating (j, t) in the sequence according to the joint ranking π(j, t|w) might require the
access to all the nk entries of Z and cost O(nk) time. In fact, based on Property 2 of conditional rankings,
we can design an efficient variant of the k-way merge algorithm [8, Chapter 5.4.1] to generate (j, t) pairs in
the desired sequence iteratively.
Property 2. Given a fixed candidate matrix H, for any possible w with wt 6= 0, the conditional ranking
πt (j|w) is either πt+ (j) or πt− (j):
• πt+ (j) = rank(hjt | {h1t , . . . , hnt }),
• πt− (j) = rank(−hjt | {−h1t , . . . , −hnt }).
9

Algorithm 1 ConditionalIterator: an iterator iterates j ∈ {1, . . . , n} based on the conditional ranking
πt (j|w). This pseudo code assumes that the k sorted index arrays st [r], r = 1, . . . , n, t = 1, . . . , k are
available.
class ConditionalIterator:
def constructor(dim idx, query val):
t, w, ptr ← dim idx, query val, 1
(
st [ptr]
if w > 0,
def current(): return
st [n − ptr + 1] otherwise.
def hasNext(): return (ptr < n)
def getNext(): ptr ← ptr + 1 and return current()
In particular, we have
πt (j|w) =

(

πt+ (j)
πt− (j)

if wt > 0,
if wt < 0.

Similar to Property 1, Property 2 enables us to characterize a query dependent conditional ranking πt (j|w)
by two query independent rankings πt+ (j) and πt− (j). As a result, similar to the motivating example in
Section 4.1,for each t, we can construct and store a sorted index array st [r], r = 1, . . . , n such that
πt+ (st [1]) ≤ πt+ (st [2]) ≤ · · · ≤ πt+ (st [n]),

(7)

πt− (st [1]) ≥ πt− (st [2]) ≥ · · · ≥ πt− (st [n]).

(8)

or equivalently

Thus, in the phase of query-independent data structure construction of Greedy-MIPS, we compute and store
query-independent rankings πt+ (·), t = 1, . . . , k by k sorted index arrays of length n: st [r], r = 1, . . . , n, t =
1, . . . , n such that (7) holds. The entire construction costs O(kn log n) time and O(kn) space.
Next we describe the details of the proposed Greedy-MIPS algorithm when a query w and the budget B
are given. As mentioned earlier, Greedy-MIPS utilizes the idea of the k-way merge algorithm to visit (j, t)
entries of Z according to the joint ranking π(j, t|w). Designed to merge k sorted sublists into a single sorted
list, the k-way merge algorithm uses 1) k pointers, one for each sorted sublist, and 2) a binary tree structure
(either a heap or a selection tree) containing the elements pointed by these k pointers to obtain the next
element to be appended into the sorted list [8, Chapter 5.4.1.].
4.2.1

Query-dependent Pre-processing

In Greedy-MIPS, we divide nk entries of (j, t) into k groups. The t-th group contains n entries:
{(j, t) : j = 1, . . . , n}.
Here we need an iterator playing a similar role as the pointer which can iterate index j ∈ {1, . . . , n} in the
sorted sequence induced by the conditional ranking πt (·|w). Utilizing Property 2, the t-th pre-computed
sorted arrays st [r], r = 1, . . . , n can be used to construct such an iterator, called ConditionalIterator,
which iterates an index j one by one in the desired sorted sequence. ConditionalIterator needs to support
current() to access the currently pointed index j and getNext() to advance the iterator. In Algorithm 1,
we describe a pseudo code for ConditionalIterator, which utilizes the facts (7) and (8) such that both the
construction and the index access cost O(1) space and O(1) time. For each t, we use iters[t] to denote the
ConditionalIterator for the t-th conditional ranking πt (j|w).

10

Algorithm 2 Query-dependent pre-processing procedure in Greedy-MIPS.
• Input: query w ∈ Rk
• For t = 1, . . . , k
–
–
–
–

iters[t] ← ConditionalIterator(t, wt )
j ← iters[t].current()
z ← hjt wt
Q.push((z, t))

• Output:

– iters[t], t = 1, . . . , k: iterators
for conditional ranking πt (·|w).

– Q: a max-heap containing (z, t) | z = maxnj=1 zjt , t = 1, . . . , k .

Regarding the binary tree structure used in Greedy-MIPS, we consider a max-heap Q of (z, t) pairs. z ∈ R
is the compared key used to maintain the heap property of Q, and t ∈ {1, . . . , k} is an integer to denote the
index to a entry group. Each (z, t) ∈ Q denotes the (j, t) entry of Z where
j = iters[t].current()

and z = zjt = hjt wt .

Note that there are most k elements in the max-heap at any time. Thus, we can implement Q by a binary
heap such that it supports
• Q.top(): returns the maximum pair (z, t) of Q in O(1) time,
• Q.pop(): deletes the maximum pair of Q in O(log k) time, and
• Q.push((z, t)): inserts a new pair in O(log k) time.
Note that the entire Greedy-MIPS can also be implemented using a selection tree among the k entries pointed
by the k iterators. For the simplicity of presentation, we use a max-heap to describe the idea of Greedy-MIPS
first and describe the details of Greedy-MIPS with a selection tree in the end of Section 4.2.2.
In the query-dependent pre-processing phase of Greedy-MIPS, we need to construct iters[t], t = 1, . . . , k,
one for each conditional ranking πt (j|w), and a max-heap Q which is initialized to contain


n
(z, t) | z = max zjt , t = 1, . . . , k .
j=1

A detailed procedure is described in Algorithm 2, which costs O(k log k) time and O(k) space.
4.2.2

Candidate Screening

Recall the requirements for a viable candidate screening procedure to support budgeted MIPS: 1) the flexibility to control the size |C(w)| ≤ B; and 2) an efficient procedure runs in O(Bk). The core idea of Greedy-MIPS
is to iteratively traverse (j, t) entries of Z in a greedy sequence and collect newly observed indices j into C(w)
until |C(w)| = B. In particular, if r = π(j, t|w), then (j, t) entry is visited at the r-th iterate. Utilizing the
max-heap Q and the k iterators: iters[t], we can design an iterator, called JointIterator, which iterates
(j, t) pairs one by one in the desired greedy sequence induced by joint ranking π(j, t|w). Following the k-way
merge algorithm, in Algorithm 3, we describe a detailed pseudo code for such an iterator. JointIterator
costs O(k log k) time to run Algorithm 2 to construct and initialize Q and iters[t], and costs O(log k) time
to advance to the next entry. In Algorithm 4, we describe our first candidate screening procedure with a
budget B for Greedy-MIPS, which is a simple while-loop to iterate (j, t) entries using the JointIterator
with w until |C(w)| = B.
To analyze the time complexity of Algorithm 4, we need to know the number of the iterations of the
while-loop before the stop condition is satisfied. The following Theorem 2 gives an upper bound on this
number of iterations.

11

Algorithm 3 JointIterator: an iterator generates (j, t) pairs one by one based on the joint ranking
π(j, t|w). The constructor costs O(k log k) time to build a max-heap Q. The time complexity to generate a
pair is O(log k).
class JointIterator:
def constructor(w):
Run Algorithm 2 with w to initialize Q and iters[t], t = 1, . . . , k
ptr ← 1.
def current():
(z, t) ← Q.top()
j ← iters[t].current()
return (j, t)
def hasNext(): return (ptr < nk)
def getNext():
(z, t) ← Q.pop()
if iters[t].hasNext():
j ← iters[t].getNext()
z ← hjt wt
Q.push((z, t))
ptr ← ptr + 1
return current()

Algorithm 4 Candidate screening procedure in Greedy-MIPS.
• Input: w and an empty C(w)
• jointIter ← JointIterator(w)
• (j, t) ← jointIter.current()
• while |C(w)| < B:
– if j ∈
/ C(w): append j to C(w)
– (j, t) ← jointIter.getNext()

· · · O(k log k)
· · · O(1)

· · · O(1)
· · · O(log k)
· · · O(log k)

· · · O(log k)

· · · O(k log k)

· · · O(log k)

• Output: C(w) = {j | π̄(j|w) ≤ B}

12

Algorithm 5 An improved candidate screening procedure in Greedy-MIPS. The overall time complexity is
O(Bk).
• Input:
–
–
–
–

H, w, and the computational budget B
Q and iters[t]: output of Algorithm 2
C(w): an empty list
visited[j] = 0, j = 1, . . . , n: a zero-initialized array of length n

• while |C(w)| < B:

– (z, t) ← Q.pop()
– j ← iters[t].current()
– if visited[j] = 0:
∗ append j into C(w)
∗ visited[j] ← 1
– while iters[t].hasNext():
∗ j ← iters[t].getNext()
∗ if visited[j] = 0:
· z ← hjt wt
· Q.push((z, t))
· break

· · · O(log k)

· · · O(log k)

• visited[j] ← 0, ∀j ∈ C(w)
• Output: C(w) = {j | π̄(j|w) ≤ B}

· · · O(B)

Theorem 2. There are at least B distinct indices j in the first Bk entries (j, t) in terms of the joint ranking
π(j, t|w) for any w; that is,
|{j | ∀(j, t) such that π(j, t|w) ≤ Bk}| ≥ B.

(9)

Proof. By grouping these first Bk entries by the index t and applying the pigeonhole principle, we know
that there exists a group G such that it contains at least B entries. Because each entry in the same group
has a distinct j index, we know that the group G contains at least B distinct indices j.
Theorem 1 guarantees the correctness of Algorithm 4 to generate C(w) based on π̄(j|w) defined in (6).
By Theorem 2, the overall time complexity of Algorithm 4 is O(Bk log k) as each iteration of the while-loop
costs O(log k) time.
The O(Bk log k) time complexity of Algorithm 4 does not satisfy the efficiency requirement of a viable
budgeted MIPS approach. Here we propose an improved candidate screening procedure which
 reduces the
overall time complexity to O(Bk). Observe that the log k term comes from the Q.push zjt , t and Q.pop()
operations of the max-heap for each visited (j,
t) entry. As the goal of the screening procedure is to identify
j indices only, we can skip the Q.push zjt , t for an entry (j, t) with the j having been included in C(w).
As a result, Q.pop() is executed at most B + k − 1 times when |C(w)| = B. The extra k − 1 times occurs in
the situation that
iters[1].current() = iters[2].current() = · · · = iters[k].current()
at the beginning of the entire screening procedure.
In Algorithm 5, we give a detailed description for this improved candidate screening procedure for GreedyMIPS. See Figure 3 for a detailed illustration of this algorithm on a toy example. Note that in Algorithm 5,
we use an auxiliary zero-initialized array of length n: visited[j], j = 1, . . . , n to denote whether an index
j has been included in C(w) or not. As C(w) contains at most B indices, only B elements of this auxiliary
array will be modified during the screening procedure. Furthermore, the auxiliary array can be reset to zero
13

w1

4
−1

w1

5
−2

6
−3

7
−4

1
−5

2
−6

3
−7

7
6

1
5

2
4

3
3

4
2

5
1

4
−1

w2

7

6
7

6.9

1
69

7
−4

1
−5

2
−6

3
−7

6
7

7
6

1
5

2
4

3
3

4
2

5
1

2
59

3
49

4
39

5
29

6
19

7
9

w3

2
59

3
49

4
39

5
29

6
19

7
9

6

−1

(a) At the beginning : C(w) = []

1
69

(b) End of iteration-1: C(w) = [6]

w1

4
−1

6
−3

w2

6.9

w3

−1

5
−2

w1

5
−2

6
−3

7
−4

1
−5

2
−6

3
−7

4
−1

5
−2

6
−3

w2

6

6
7

7
6

5.9

1
69

2
59

1
−5

2
−6

3
−7

w2

1
5

2
4

3
3

4
2

5
1

3
49

4
39

5
29

6
19

7
9

5.9

6
7

w3

−1

7
−4

7
6

1
5

2
4

3
3

4
2

5
1

3
49

4
39

5
29

6
19

7
9

w3

−1

(c) End of iteration-2: C(w) = [6, 1]

4

1
69

2
59

(d) End of iteration-3: C(w) = [6, 1, 7]

Figure 3: Illustration of Algorithm 5 with w = [1, 1, 0.1]> and B = 3. The left plot for each sub-figure shows
the heap structure in the max-heap Q: the value in each rectangle denotes z, and each index t is shown in
a different color (red for 1, green for 2, and blue for 3). The sorted index arrays are shown in the upper
part of circles on the right plot for each sub-figure; for example, s1 [4] = 7, s2 [1] = 6, and s3 [5] = 5. The
value in lower part of circles is the corresponding hjt ; for example, h71 = −4, h62 = 7, and h53 = 29. Three
downward triangles denote the current position of iters[t], t = 1, 2, 3. Figure 3(a) shows the status for
each data data structure at the beginning of Algorithm 5. Three pairs are pushed into Q: (−1 = h41 w1 , 1),
(7 = h71 w2 , 2), and (6.9 = h13 w3 , 3). Figures 3(b)-3(c) show the status in the end of the first and the second
iterations of the outer while-loop in Algorithm 5. In Figure 3(c), we show that at the third iteration, after
(z, t) = (6, 2) ← Q.pop() is executed and 7 = iters[2].current() is appended into C(w), we need to advance
iters[2] twice because the index j = 1 has been included in C(w). Note that for this example h1 is the
candidate with the largest inner product value with w.
using O(B) time in the end of Algorithm 5, so this auxiliary array can be utilized again for a different query
vector w.
Notice that Algorithm 5 still iterates Bk entries of Z but at most B + k − 1 entries will be pushed into
or pop from the max-heap. Thus, the overall time complexity of Algorithm 5 is O(Bk + B log k) = O(Bk),
which satisfies the efficiency requirement for a viable approach for budgeted MIPS.
Greedy-MIPS with a Selection Tree. As there are at most k pairs in the max-heap Q, one from each
iters[t], the max-heap can be replaced by a selection tree to achieve a slightly faster implementation as
suggested in [8, Chapter 5.4.1]. In Algorithm 6, we give a pseudo code for the selection tree with a O(k)
time constructor, a O(1) time maximum element look-up, and a O(log k) time updater. To apply the section
tree for our Greedy-MIPS, we only need to the following modifications:
• In Algorithm 2, remove Q.push((z, t)) from the for-loop and construct Q by Q ← SelectionTree(w, k, iters).
• In Algorithm 3 and Algorithm 5, replace Q.pop() by Q.top() and replace Q.push((z, t)) by Q.updateValue(t, z).
4.2.3

Connection to Sampling-based MIPS Approaches

Sample-MSIPS, as mentioned earlier, is essentially a sampling algorithm with replacement scheme to draw
entries of Z such that (j, t) is sampled with the probability proportional to zjt . Thus, Sample-MSIPS can be
thought as a traversal of (j, t) entries using in a stratified random sequence determined by a distribution of
the values of {zjt }, while the core idea of Greedy-MIPS is to iterate (j, t) entries of Z in a greedy sequence
induced by the ordering of {zjt }. Next, we discuss the differences between Greedy-MIPS and Sample-MSIPS
in a few perspectives:

14

Algorithm 6 A pseudo code of a selection tree used for Greedy-MIPS.
class SelectionTree:
def constructor(w, k, iters) :

K̄ ← min 2i | 2i ≥ k
for i = 1, . . . , 2K̄:
buf[i] ← (−∞, 0)
for t = 1, . . . , k:
j ← iters[t].current()
buf[K̄ + t] ← (hjt wt , t)
for i = K̄, . . . , 1:
if buf[2i].first > buf[2i + 1].first:
buf[i] ← buf[2i]
else:
buf[i] ← buf[2i + 1]
def top(): return buf[1]
def updateValue(t, z):
i ← K̄ + t
buf[i] ← (z, t)
while i > 1:
i ← bi/2c
if buf[2i].first > buf[2i + 1].first:
buf[i] ← buf[2i]
else:
buf[i] ← buf[2i + 1]

· · · O(k)

· · · O(1)
· · · O(log k)

Applicability: Sample-MSIPS can be applied to the situation where both H and w are nonnegative because
of the nature of sampling scheme. In contrast, Greedy-MIPS can work on any MIPS problems as only the
ordering of {zjt } matters in Greedy-MIPS. Instead of h>
j w, Diamond-MSIPS is designed for the MSIPS
2
>
problem which is to identify candidates with largest hj w or h>
j w values [3]. In fact, for nonnegative
MIPS problems, the diamond sampling is equivalent to Sample-MSIPS. Moreover, for MSIPS problems with
negative entries, when the number of samples is set to be the budget B,2 the Diamond-MSIPS is equivalent
to apply Sample-MSIPS to sample (j, t) entries with the probability p(j, t) ∝ |zjt |. Thus, the applicability of
the existing sampling-based approaches is still very limited for general MIPS problems.
Flexibility to Control |C(w)|: By Theorem 2, we know that Greedy-MIPS can guarantee both the time
complexity of the candidate screening procedure and the size of output |C(w)| for any H, w, and B. For
a sampling-based approach, one can easily control either the time complexity of the sampling procedure or
the size of C(w), but not both. Because all the existing sampling-based approaches are a sampling scheme
with replacement, the same entry (j, t) could be sampled repeatedly. Thus, the time complexity to guarantee
that C(w) = B depends on the distribution of values of w and H. Hence, Greedy-MIPS is more flexible than
sampling-based approaches in terms of the controllability of C(w).

5

Experimental Results

In this section, we perform extensive empirical comparisons to compare Greedy-MIPS with other state-ofthe-art fast MIPS approaches on both real-world and synthetic datasets.
2 This

setting is used in the experiments in [3]

15

Figure 4: Comparison of variants of Greedy-MIPS.
• We use netflix and yahoo-music as our real-world recommender system datasets. There are 17, 770 and
624, 961 items in netflix and yahoo-music, respectively. In particular, we obtain the low rank model
(W, H) by the standard low-rank matrix factorization:


m
n
X
X
X

Ω̄
|Ωi |
2
j
2
2
min
Aij − wi> hj + λ
kwi k +
khj k ,
W,H
n
m
i=1
j=1
(i,j)∈Ω

where Aij is the rating of the j-th item given by the i-th user, Ω is the set of observed ratings,
Ωi = {j | (i, j) ∈ Ω}, and Ω̄j = {i | (i, j) ∈ Ω}, and λ is a regularization parameter. We use the
CCD++ [16] algorithm implemented in LIBPMF3 to solve the above optimization problem and obtain
the user embeddings {wi } and item embeddings {hj }. We use the same λ used in [4]. We also obtain
(W, H) with a different k: 50, 100, and k = 200.
• We also generate synthetic datasets with various n = 2{17,18,19,20} and k = 2{2,5,7,10} . For each
synthetic dataset, both candidate vector hj and query w vector are drawn from the normal distribution.

3 http://www.cs.utexas.edu/

~rofuyu/libpmf

16

Figure 5: MIPS Comparison on netflix and yahoo-music.

5.1

Experimental Settings and Evaluation Criteria

All the experiments are performed on a Linux machine with 20 cores and 256 GB memory. We ensure that
only single core/thread is used for our experiments. To have a fair comparison, all the compared approaches
are implemented in C++:
• Greedy-MIPS: our proposed approach in Section 4. We compare the following variants in Section 5.2:
17

Figure 6: MIPS Comparison on synthetic datasets with n ∈ 2{17,18,19,20} and k = 128. The datasets used to
generate results are created with each entry drawn from a normal distribution.
– The improved Greedy-MIPS in Algorithm 5 with the selection tree in Algorithm 6.
– The improved Greedy-MIPS in Algorithm 5 with a max-heap.
– The original Greedy-MIPS in Algorithm 4 with the selection tree in Algorithm 6.
• NNS-based MIPS approaches:

– PCA-MIPS: the approach proposed in [2], which is shown to be the state-of-the-art among treebased approaches [2]. We implement a complete PCA-Tree with the neighborhood boosting
techniques described in [2]. We vary the depth of PCA tree to control the trade-off between the
search quality and the search efficiency.
– LSH-MIPS: the approach proposed in [11, 13]. We use the nearest neighbor transform function
proposed in [2, 11] and use the random projection scheme as the LSH function as suggested in
[11]. We also implement the standard amplification procedure with an OR-construction of b hyper
LSH hash functions. Each hyper LSH function is a result of an AND-construction of a random
projections. We vary the values (a, b) to control the trade-off between the search quality and the
search efficiency.

• Diamond-MSIPS: the sampling scheme proposed in [3] for the maximum squared inner product search.
As it shows better performance than LSH-MIPS in [3] in terms of MIPS problems, we also include
Diamond-MSIPS into our comparison. F+Tree [17] is implemented as the multinomial sampling procedure.
• Naive-MIPS: the baseline approach which applies a linear search to identify the exact top-K candidates.
18

Evaluation Criteria. For each dataset, the actual top-20 items for each query are regarded as the
ground truth. We report the average performance on a randomly selected 2,000 query vectors. To evaluate
the search quality, we use the precision on the top-K prediction (prec@K), is obtained by selecting top-K
items from C(w) returned by the candidate screening procedure of a compared MIPS approach. K = 5 and
K = 10 are used in our experiments. To evaluate the search efficiency, we report the relative speedups over
the Naive-MIPS approach as follows:
speedup =

prediction time required by Naive-MIPS
.
prediction time by a compared approach

Remarks on Budgeted MIPS versus Non-Budgeted MIPS. As mentioned in Section 3, PCA-MIPS
and LSH-MIPS cannot handle MIPS with a budget. Both the search computation cost and the search quality
are fixed when the corresponding data structure is constructed. As a result, to understand the trade-off
between search efficiency and search quality for these two approaches, we can only try various values for
its parameters (such as the depth for PCA tree and the amplification parameters (a, b) for LSH). For each
combination of parameters, we need to re-run the entire query-independent pre-processing procedure to
construct a new data structure.

Figure 7: MIPS Comparison on synthetic datasets with n = 218 and k ∈ 2{2,5,7,10} . The datasets used to
generate results on are created with each entry drawn from a normal distribution.

5.2

Experimental Results

Results on Variants of Greedy-MIPS. In Figure 4, we shows the comparison between the three variants of
Greedy-MIPS on netflix and yahoo-music. We can see that the difference between the use of a selection-tree
19

and a max-heap is small, while the different between the use of Algorithm 4 and the use of Algorithm 5 is
more significant. For the comparison to other MIPS approaches, we use Greedy-MIPS to denote the results
obtained from the version with the combination of Algorithm 5 and Algorithm 6.
Results on Real-World Data sets. Comparison results for netflix and yahoo-music are shown in
Figure 5. The first, second, and third columns present the results with k = 50, k = 100, and k = 200,
respectively. It is clearly observed that given a fixed speedup, Greedy-MIPS yields predictions with much
higher search quality. In particular, on the yahoo-music data set with k = 200, Greedy-MIPS runs 200x
faster than Naive-MIPS and yields search results with p5 = 70%, while none of PCA-MIPS, LSH-MIPS, and
Diamond-MSIPS can achieve a p5 > 10% while maintaining the similar 200x speedups.
Results on Synthetic Data Sets. We also perform comparisons on synthetic datasets. The comparison
with various n ∈ 2{17,18,19,20} is shown in Figure 6, while the comparison with various k ∈ 2{2,5,7,10} is shown
in Figure 7. We observe that the performance gap between Greedy-MIPS over other approaches remains when
n increases, while the gap becomes smaller when k increases. However, Greedy-MIPS still outperforms other
approaches significantly.

6

Conclusions

In this paper, we study the computational issue in the prediction phase for many MF-based models: a
maximum inner product search problem (MIPS) with a very large number of candidate embeddings. By
carefully studying the problem structure of MIPS, we develop a novel Greedy-MIPS algorithm, which can
handle budgeted MIPS by design. While simple and intuitive, Greedy-MIPS yields surprisingly superior
performance compared to state-of-the-art approaches. As a specific example, on a candidate set containing
half a million vectors of dimension 200, Greedy-MIPS runs 200x faster than the naive approach while yielding
search results with the top-5 precision greater than 75%.

References
[1] Alex Auvolat, Sarath Chandar, Pascal Vincent, Hugo Larochelle, and Yoshua Bengio. Clustering is efficient for
approximate maximum inner product search, 2016. arXiv preprint arXiv:1507.05910.
[2] Yoram Bachrach, Yehuda Finkelstein, Ran Gilad-Bachrach, Liran Katzir, Noam Koenigstein, Nir Nice, and
Ulrich Paquet. Speeding up the xbox recommender system using a euclidean transformation for inner-product
spaces. In Proceedings of the 8th ACM Conference on Recommender Systems, pages 257–264, 2014.
[3] Grey Ballard, Seshadhri Comandur, Tamara Kolda, and Ali Pinar. Diamond sampling for approximate maximum
all-pairs dot-product (MAD) search. In Proceedings of the IEEE International Conference on Data Mining, 2015.
[4] Wei-Sheng Chin, Yong Zhuang, Yu-Chin Juan, and Chih-Jen Lin. A learning-rate schedule for stochastic gradient
methods to matrix factorization. In Proceedings of the Pacific-Asia Conference on Knowledge Discovery and
Data Mining (PAKDD), 2015.
[5] Edith Cohen and David D. Lewis. Approximating matrix multiplication for pattern recognition tasks. In
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 682–691, 1997.
[6] Thomas H. Cormen, Charles E. Leiserson, and Ronald L Rivest. Introduction to Algorithms. MIT Press,
Cambridge, MA, 1990.
[7] Gideon Dror, Noam Koenigstein, Yehuda Koren, and Markus Weimer. The Yahoo! music dataset and KDDCup’11. In JMLR Workshop and Conference Proceedings: Proceedings of KDD Cup 2011 Competition, volume 18,
pages 3–18, 2012.
[8] Donald E. Knuth. The Art of Cmoputer Programming, Volumne 3: Sorting and Searching. Addison-Wesley, 2nd
edition, 1998.

20

[9] Noam Koenigstein, Parikshit Ram, and Yuval Shavitt. Efficient retrieval of recommendations in a matrix factorization framework. In Proceedings of the 21st ACM International Conference on Information and Knowledge
Management, CIKM ’12, pages 535–544, 2012.
[10] Yehuda Koren, Robert M. Bell, and Chris Volinsky. Matrix factorization techniques for recommender systems.
IEEE Computer, 42:30–37, 2009.
[11] Behnam Neyshabur and Nathan Srebro. On symmetric and asymmetric lshs for inner product search. In
Proceedings of the International Conference on Machine Learning, pages 1926–1934, 2015.
[12] Parikshit Ram and Alexander G. Gray. Maximum inner-product search using cone trees. In Proceedings of the
18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 931–939, 2012.
[13] Anshumali Shrivastava and Ping Li. Asymmetric lsh (ALSH) for sublinear time maximum inner product search
(MIPS). In Z. Ghahramani, M. Welling, C. Cortes, N.D. Lawrence, and K.Q. Weinberger, editors, Advances in
Neural Information Processing Systems 27, pages 2321–2329, 2014.
[14] Anshumali Shrivastava and Ping Li. Improved asymmetric locality senstive hashing lsh (ALSH) for maximum
inner product search (MIPS). In Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence (UAI), pages 812–821, 2015.
[15] Jason Weston, Samy Bengio, and Nicolas Usunier. Large scale image annotation: learning to rank with joint
word-image embeddings. Mach. Learn., 81(1):21–35, October 2010.
[16] Hsiang-Fu Yu, Cho-Jui Hsieh, Si Si, and Inderjit S. Dhillon. Parallel matrix factorization for recommender
systems. Knowledge and Information Systems, 41(3):793–819, 2014.
[17] Hsiang-Fu Yu, Cho-Jui Hsieh, Hyokun Yun, S.V.N. Vishwanathan, and Inderjit S. Dhillon. A scalable asynchronous distributed algorithm for topic modeling. In Proceedings of the International World Wide Web Conference, pages 1340–1350, may 2015.
[18] Hsiang-Fu Yu, Prateek Jain, Purushottam Kar, and Inderjit S. Dhillon. Large-scale multi-label learning with
missing labels. In Proceedings of the International Conference on Machine Learning, pages 593–601, 2014.

21

