Efficient Indexing of Billion-Scale datasets of deep descriptors
Artem Babenko
YandexMoscow Institute of Physics and Technology

Victor Lempitsky
Skolkovo Institute of Science and Technology(Skoltech)artem.babenko@phystech.edu

lempitsky@skoltech.ru

Abstract
Existing billion-scale nearest neighbor search systems
have mostly been compared on a single dataset of a billion of SIFT vectors, where systems based on the Inverted
Multi-Index (IMI) have been performing very well, achieving state-of-the-art recall in several milliseconds. SIFT-likedescriptors, however, are quickly being replaced with descriptors based on deep neural networks (DNN) that provide better performance for many computer vision tasks.
In this paper, we introduce a new dataset of one billion
descriptors based on DNNs and reveal the relative inefficiency of IMI-based indexing for such descriptors compared
to SIFT data. We then introduce two new indexing structures, the Non-Orthogonal Inverted Multi-Index (NO-IMI)and the Generalized Non-Orthogonal Inverted Multi-Index(GNO-IMI). We show that due to additional flexibility, the
new structures are able to adapt to DNN descriptor distribution in a better way. In particular, extensive experimentson the new dataset demonstrate that these data structures
provide considerably better trade-off between the speed of
retrieval and recall, given similar amount of memory, as
compared to the standard Inverted Multi-Index.

1. Introduction
Modern image retrieval systems[19] have to searchthrough billion-scale databases in several milliseconds to
respond to user queries. This imposes strict demands onscalability and efficiency of the underlying nearest-neighborsearch algorithms. As exhaustive search is mostly infeasibleat this scale, approximate nearest neighbor (ANN) methods
that restrict the part of a dataset that is being considered in
response to a query have to be used.
State-of-the-art ANN algorithms of this kind [13, 2, 9,
14, 5] avoid exhaustive search by organizing dataset points
using an indexing structure. For a given query the indexing structure allows to retrieve a short-list of candidate
points that are likely to be close to this query. The candidate points are then reranked according to their distances

using such methods as Asymmetric Distance Computation(ADC) [12]. In general, the reranking runtime is approximately linear in the size of the short-list. Consequently, theability to obtain compact short-lists with high enough recall
leads to fast reranking and overall time efficiency.
One of the first billion-scale retrieval systems for billionscale datasets have been presented by Jegou et al. [13].
Their system called IVFADC divides data space into separate cells, corresponding to Voronoi regions obtained via
k-means clustering. Given a query, IVFADC returns theshort list with the points from the cells that are the closest to it. The Inverted Multi-Index (IMI)[2] generalizes
IVFADC by decomposing the dataspace into several subspaces and splitting each subspace into cells independently.
The system [14], based on the IMI indexing structure and
the Product Quantization (PQ) compression provides stateof-the-art performance on the SIFT1B dataset of one billion
SIFT descriptors [13], which invariably serves as the testbed
for such systems.
Recently, the focus in computer vision has shifted from
SIFT descriptors to descriptors produced by deep neuralnetworks (DNN). Several works [17, 7, 11, 18, 4] haveshown that DNN-based descriptors significantly improve
the state-of-the-art on common retrieval benchmarks. Furthermore, [7] have shown that deep descriptors can be compressed by PCA with almost no loss in performance.
Despite such shift to deep descriptors, to the best of ourknowledge, billion-scale ANN with deep descriptors has
not been investigated. One potential problem with relying
on the SIFT1B dataset is its particular suitability for IMIbased systems. This is because, the SIFT construction procedure uses different halves of a SIFT vector to describe
disjoint regions of an image patch. Thus, the correlations
between the two halves are likely to be small and the decomposition in the IMI is justified. Deep descriptors do notpossess such structure and therefore the good performanceof IMI might not be achieved.
This paper seeks to develop a good indexing structure
for deep descriptors. We begin with experiments illustrating that for this type of data the Inverted Multi-Index indeed
12055

2
1
0
1
2
2

1

1

0

2

3

2

1

IMI

1

0

2

3

2

NO-IMI

1

1

0

2

3

GNO-IMI

Figure 1. The cell centroids (red points) produced by different indexing structures for the same sample of two-dimensional data (bluepoints). For all structures parameter K was set to four, hence 16 centroids were produced. The left plot corresponds to the IMI structure
and large blue points on the axes denote the codewords of the underlying PQ decomposition. The middle and right plots correspond to the
NO-IMI and the GNO-IMI structures respectively. On the both plots green points correspond to the “first-order centroids” S1 , . . . , S4 . The
GNO-IMI centroids represent the actual data distribution more accurately than the other structures.

produces a particularly large number of redundant cells that
do not contain any points. This deficiency arises from thespace decomposition, implicitly performed in the IMI. We
conclude that for deep data the correlations between subspaces are significant and independent codebooks for eachsubspace cannot represent the global data distribution adequately.
We then introduce two new indexing structures, theNon-Orthogonal Inverted Multi-Index (NO-IMI) and theGeneralized Non-Orthogonal Inverted Multi-Index (GNOIMI). The NO-IMI forms index cells centroids as sumsof two vectors from two non-orthogonal codebooks, following the well-known residual vector quantization (RVQ)
scheme [8], thus avoiding any decomposition into orthogonal subspaces. As a result, the NO-IMI provides more reasonable index cells with the centroids representing actual
data distribution more accurately. The GNO-IMI pushes therepresentation accuracy even further by forming cell centroids as linear combinations of codewords. As the extra
linear coefficients are learned from the data, the GNO-IMI
exhibits higher efficiency while indexing complex data as
compared to the NO-IMI.
We demonstrate that better indexing by the (G)NO-IMI
results in more compact and precise short-lists and, therefore, more efficient retrieval. Overall, we show that forthe same time budget the new structures provide higher recall compared to the existing top-performing schemes. Ourevaluation is based on a new dataset of one billion deep descriptors with hold-out query and learning sets. The dataset
is the first publicly available billion-scale dataset of deep
descriptors.

2. Related work
We briefly describe several ideas from the previous workthat are essential to the description of the our structures.
Along the way, we introduce notation for this description.
Product quantization (PQ) is a lossy compression

scheme for high-dimensional vectors [12]. PQ encodes
each vector x ∈ RD as a concatenation of M codewords
Dfrom M M-dimensional codebooks C1 , . . . , CM , each containing K codewords. In other words, PQ decomposes avector into M separate subvectors and applies vector quantization (VQ) to each subvector, while using a separate
codebook. As a result each vector x is encoded by a tuple of codewords indices [i1 , . . . , iM ] and approximated byx ≈ [C1 (i1 ), . . . , CM (iM )]. Fast Euclidean distance computation becomes possible via efficient ADC procedure [12]using lookup tables:kq − xk2 ≈ kq − [C1 (i1 ), . . . , CM (iM )]k2 =MXkqm − Cm (im )k

(1)

2

m=1

where qm — mth subvector of a query q. This sum can becalculated in M additions and lookups given that distancesfrom query subvectors to codewords are precomputed.
From the geometry viewpoint, PQ effectively partitions
the original vector space into K M cells, each being a Cartesian product of M lower-dimensional cells. Such productD-dimensional
based approximation works better if the M
components of vectors have independent distributions. The
degree of dependence is affected by the choice of the splitting, and can be further improved by orthogonal transformation applied to vectors as preprocessing. Two recent works
have therefore looked into finding an optimal transformation [10, 16]. Following one of them, the modification of
PQ corresponding to such pre-processing transformation isreferred below as Optimized Product Quantization (OPQ).
Non-orthogonal quantizations. Several works [8, 3,
21, 6] have proposed modifications of PQ that do not decompose the dataspace into orthogonal subspaces. In fact,
they generalize the idea of Product Quantization by approximating each vector by a sum of M codewords instead ofconcatenation. In this case the ADC procedure is still efficient while the approximation accuracy is increased.
2056

The first approach, Residual Vector Quantization [8],quantizes original vectors, and then iteratively quantizes theapproximation residuals from the previous iteration. [8]also introduces the IVFRVQ system that allows to perform
non-exhaustive search. IVFRVQ prunes large portions of
database points based on the distances from a query to
the “coarse approximations”, produced by the first several
quantizers. Another approach, Additive Quantization (AQ)[3], is the most general as it does not impose any constraints
on the codewords from the different codebooks. Usually,
AQ provides the smallest compression errors, however, it
is much slower than other methods, especially for large
M . Composite Quantization (CQ) [21] learns codebookswith a fixed value of scalar product between the codewords
from different codebooks. Finally, Tree Quantization (TQ)[6] performs decomposition into subspaces while constraining the non-orthogonality relations between different codebooks to form a tree graph. Under this constraint, efficientencoding is possible.
Overall, non-orthogonal quantizations achieve higher
approximation accuracy than (O)PQ, especially for nonhistogram data. At the same time, they are slower and require more complex learning procedures.
IVFADC. One of the first systems capable of dealing
with billion-scale datasets efficiently was IVFADC introduced in [13]. This system combines the inverted index [19]as indexing structure and Product Quantization for database
compression. IVFADC first splits the space into K cells via
standard K-means and then encodes displacements of eachpoint from the centroid of a cell it belongs to. The encoding is performed via Product Quantization that uses global
codebooks shared by all cells.
The Inverted Multi-Index and Multi-D-ADC. The Inverted Multi-Index (IMI) [2] is an indexing algorithm forhigh-dimensional spaces and very large datasets. The IMI
generalizes the inverted index by using product codebooks
for cell centroids construction (typically, as few as two components in the product are considered). Thus the Inverted
Multi-Index has two D
2 -dimensional product codebooks fordifferent halves of the vector, each with K sub-codewords,
thus effectively producing K 2 cells, which would typicallybe orders of magnitude bigger than the number of cells
within the IVFADC system or other systems using inverted
indices. Large number of cells provides very dense partitioning of the space, which means that a small fraction ofdataset has to be traversed to achieve high recall (w.r.t. thetrue nearest neighbor). For dataset compression, [2] followed the IVFADC system and used Product Quantization
with global codebooks shared across all cells in order to encode the displacements of the vectors from centroids (thissystem is referred to as Multi-D-ADC).
Further improvements. [9] improved the performanceof Multi-D-ADC by replacing Product Quantization with

Optimized Product Quantization for both indexing andcompression (hence the name of their system OMulti-DOADC). OMulti-D-OADC gives the state-of-the-art performance in terms of the search accuracy on the SIFT1B
dataset with global codebooks for database compression.
Another system, called LOPQ [14], is a modificationof IVFADC which uses separate local OPQ codebooks fordatabase points compression in each cell. As local codebooks represent points distribution in the particular cellmore precisely, the accuracy of reranking in LOPQ is muchhigher than in IVFADC. Also, [14] introduces the MultiLOPQ system, which uses local codebooks with the Inverted Multi-Index structure. Currently, Multi-LOPQ system provides the highest recall on the SIFT1B dataset.

3. The Non-Orthogonal Inverted Multi-Index
In this section we introduce a new indexing structure, theNon-Orthogonal Inverted Multi-Index (NO-IMI). We firstdescribe the design of the NO-IMI and the intuition behind
it. We then provide a procedure of the NO-IMI codebooks
learning. Finally, we explain how candidate lists are extracted and are reranked using the NO-IMI.

3.1. The NO-IMI structure
Let us assume that a database P = {p1 , . . . , pN } of
D-dimensional points is given. As well as the existing
indexing structures the NO-IMI partitions the dataspace
into a large number of cells and distributes database points
over these cells. The cells in the NO-IMI are constructedbased on two codebooks S = {S1 , . . . , SK } and T ={T1 , . . . , TK }, each containing K codewords. The codewords in the codebooks are D-dimensional, S, T ⊂ RD .
The NO-IMI splits the data space into K 2 cells with centroids cji defined by the formula:cji = Si + Tj ,i, j = 1, . . . , K(2)Thus, the NO-IMI cells are the regions of the data space
defined by the following:
Cij = {x ∈ RD |i, j = arg min kx − (Sk + Tl ) k2 } (3)k,lThis construction is similar to how cells within the Inverted
Multi-Index are constructed. We however aim to avoid thespace decomposition, underlying the Inverted Multi-Index,
which is based on product quantization and which ignores
correlations between subspaces of the deep descriptors data.
Based on this consideration, it is reasonable to replace PQ
by some non-orthogonal quantization.
Among non-orthogonal approaches, we chose Residual
Vector Quantization (RVQ) as it allows to perform efficient
short-lists extraction, as will be discussed below. With the
RVQ method in mind, the NO-IMI codewords S1 , . . . , SK2057

can be interpreted as cluster centroids in the original dataspace and we refer to them as first-order centroids. Similarly, the codewords T1 , . . . , TK can be interpreted as centroids in the space of displacements of data points from thefirst-order centroids. We refer to them as second-order centroids. As a result, the indexing structure has K 2 centroids
in the form (Si + Tj ), i, j = 1, . . . , K and the same numberof cells, each assigned with the first-order index i and thesecond-order index j.
The construction (2) is also directly related to the wellknown Hierarchical K-Means (HKM) method [15]. Thismethod also clusters the original data space, producing
K first-order centroids. It then clusters the displacementsin each cluster separately, producing K second-order centroids in each cluster. For large K, the usage of HKM is
infeasible as it would require to keep K 2 D-dimensional
vectors in the main memory. Such enormous memory consumption can be avoided by using K second-order centroids that are shared by all clusters. Sharing the secondorder centroids makes Hierarchical K-Means equivalent to
the RVQ scheme, described in the previous paragraph.

3.2. The generalized NO-IMIThe NO-IMI assumes that the displacements distributions within first-order clusters are similar, as it uses sharedsecond-order centroids. However, this assumption may be
too strong, as e.g. the spatial extent and the shape of thecorresponding Voronoi cells can vary, especially when thedata distribution has dense and sparse regions. To alleviate
this assumption we augment the NO-IMI with an additional
α-matrix, which incorporates cluster-wise information. In
particular, an element α[i, j] is a factor for the j-th secondorder centroid Tj in the i-th first-order cluster. After theincorporation of these factors, the expression for the corresponding centroid becomes:
cji = Si + α[i, j]Tj ,i, j = 1, . . . , K(4)
The addition of α-matrix allows to represent data distribution adequately even with shared second-order centroids.
Below we refer to the version of the NO-IMI with the
α-matrix as Generalized Non-Orthogonal Inverted MultiIndex (GNO-IMI). We demonstrate an example of centroids
produced by the original IMI, the NO-IMI, and the GNOIMI on a toy 2D dataset in Figure 1.

3.3. Indexing
The parameters of (G)NO-IMI, namely S, T, α, can all
be learned from data as will be discussed below. Let us now
assume that S, T, α are given and describe the process that
distributes the dataset points p1 , . . . , pN assigning them todifferent (G)NO-IMI cells. More formally, for each point p
we have to find the closest centroid indices:i, j = arg min kp − (Sk + α[k, l]Tl ) k2
(5)k,lExhaustive minimization of this function would require
the evaluation of K 2 possible solutions, which is impractical. Instead, we use a simple heuristic to cut out most of the
suboptimal solutions. Let us rewrite the expression above:kp − (Sk + α[k, l]Tl ) k2 = kp − Sk k2 + α[k, l]2 kTl k2−2α[k, l]hp, Tl i + 2α[k, l]hSk , Tl i

(6)Note, that the first term kp − Sk k2 is a distance from p to
the first-order centroid Sk . The RVQ heuristic is to inspect
only r values k1 , . . . , kr corresponding to the indices ofcentroids Sk1 , . . . , Skr , which are the closest to p. With thispruning, only rK solutions have to be evaluated. Anotherspeed optimization is to precompute the terms kp − Sk k2
and hp, Tl i, which can be done in O(KD) operations. With
these terms precomputed, each solution can be evaluated inO(1) operations. After all rK possibilities are evaluated, p
is assigned to the cell, corresponding to the optimal index
pair.
The complexity of point assignment is therefore a sum ofcomplexities of precomputation and pairs evaluation steps,
which are O(DK) and O(rK) respectively. Hence, theoverall complexity is O(DK + rK), while the complexity in the Inverted Multi-Index equals O(DK). In our experiments r is several times smaller than D and the actual
timings of indexing for both the IMI and the (G)NO-IMI are
rather similar.

3.4. Codebooks learning
We now focus on the task of obtaining codebooks S, T
and the α-matrix that fit a given data distribution well. We
suppose that a training dataset P = {p1 , . . . , pN } is provided. The learning is performed by the minimization of
the reconstruction error for all training points:
NX
2pi − (Ski + α[k i , li ]Tli ) →
min
(7)
i=1

Sk ∈RD ,|S|=K,
Tk ∈RD ,|T |=K,
α∈RD×Dki ,li ∈{1,...,K}

Overall, the optimization is performed over four groupsof variables, where S, T and α variables are continuous,
while the assignment variables {k i , li } are discrete. We
minimize the function using block-coordinate descent by
optimizing over one variable group at a time with the otherthree groups fixed. Below we describe the optimization overeach variable group separately.
Optimization over assignments. At this step the optimization is performed over {k i , li } variables given codebooks S, T and α matrix. Thus, this problem is equivalent
to the indexing task and we discuss an efficient method forthat above in Section 3.3.
Optimization over α. We now fix the assignments{k i , li } and the codebooks S, T and minimize over the elements of the α matrix. Let us show that it is possible to2058

minimize over each matrix element α[k, l] independently.
For that we decompose the target function as follows:NX

pi − (Ski + α[k i , li ]Tli )

2

=

i=1

=

K
K X
X

2

X

kpi − Sk − α[k, l]Tl k(8)

k=1 l=1 i:ki =k,li =l2

PNote, that each termkpi − Sk − α[k, l]Tl k

i:ki =k,li =ldepends on the only element α[k, l]. Hence, the minimization of the whole function is equivalent to the independent
minimizations of each term:X2kpi − Sk − α[k, l]Tl k → min(9)
α[k,l]

i:ki =k,li =lThis subproblem can be solved analytically and its
closed-form solution is: P
hpi − Sk , Tl i
i:ki =k,li =lP(10)α[k, l] =kTl k2
i:ki =k,li =lOptimization over second-order codebook T . Similarly, we optimize over the second-order codewords Tl by
decomposing the target function again:NX

pi − (Ski + α[k i , li ]Tli )2clustering of the displacements from the database points tothe closest first-order codewords.
Comments. In practice we observed that the method requires quite a few iterations to converge and we used ten
iterations in our experiments. Parameter r was set to eight.
Also note, that for some index pairs k, l there could be no
points and then both the numerator and the denominator in
the expression (10) vanish. In this case we set α[k, l] = 1.

3.5. Short-list extraction
Here we describe the procedure that gets a query q andproduces an ordered sequence of cells that correspond tothe centroids that are the closest to q. The sequence canbe of any desired length L and the points assigned to thesecells form the short-list that is returned by the GNO-IMI in
response to the query. The procedure consists of three steps:
2

1. First, we compute the distances kq − Sk k between thequery and the first-order centroids. Let us denote by
k1 , . . . , kr indices of r first-order centroids that appeared
to be the closest to q.
2
distances[k] = kq − Sk k , k = 1, . . . , K
k1 , . . . , kr = distances.argsort()[1 : r]
We then discard all the cells with first-order indicesnot belonging to the set {k1 , . . . , kr }. The subsequent
search is performed among the remaining rK cells only.

=

i=1
K X
K
X

2

X

kpi − Sk − α[k, l]Tl k

(11)

P

2

cells = {(ki ; l)}ki ∈ {k1 , . . . , kr }, l = 1, . . . , K

l=1 k=1 i:ki =k,li =lThen each termKPkpi − Sk − α[k, l]Tl k is

k=1 i:ki =k,li =lminimized over Tl independently. This minimization also
can be solved analytically and the solution has the form:KPP(pi − Sk )α[k, l]Tl =i:ki =k,li =l

k=1

K
P

(12)

The complexity of this step is O(KD + K log K) withthe two terms corresponding to distances calculation andsorting.
2. Secondly, the procedure creates an array of the lengthrK and fills it with the distances to the centroids of thepromising cells selected in step one:for each cell = (ki ; l) in cells :α[k, l]2P

k=1 i:ki =k,li =lOptimization over first-order codebook S. This problem is also decomposable and the minimization is performed completely analogously to the previous step. The
solution to this step has the formKPP(pi − α[k, l]Tl )Sk =l=1 i:ki =k,li =l
K
P

(13)
P

1

l=1 i:ki =k,li =lInitialization. We initialize the iterations of the GNOIMI learning in the following way. The α-matrix is initialized by all ones and S is initialized by centroids obtained via
K-means clustering of the dataset P . Second-order codebook T is initialized by centroids obtained via K-means

cellDistances[(ki ; l)] = kq − Ski k2 + α[ki , l]2 kTl k2−2α[ki , l]hq, Tl i + 2α[ki , l]hSki ; Tl i
Note, that the terms hq, Tl i can be precomputed onceand reused for all ki and l. The terms hSki , Tl i and thenorms kTl k2 are precomputed before querying and are
kept in lookup-tables. Thus, the complexity of this stepis O(rK).
3. Finally, we apply partial sorting of distances array withlinear average complexity1 . For any input array thispartial sorting guarantees that the L smallest elements
will be placed in the first L position of the output array(possibly unordered), where L is the desired length of
1 std::nth element from the standard STL library

2059

NMI(I1 ,I2 )cells sequence. Then only L cells corresponding to thesmallest distances are sorted and the sorted sequence isyielded as a procedure result.
P artialSort(cellDistances[], L)

0.5

DEEP1B

Empty cells

SIFT1B
DEEP1B80

0.4

Output = Sort(cellDistances[1 : L])

60

0.3

The complexity of this step is O(rK + L log L).
The total complexity of the procedure is a sum of complexities for the three steps and equals O(KD + K log K +rK + L log L). In this sum the terms O(KD) andO(K log K) are common for existing indexing structures
as they also perform query quantization and sort distances
to centroids. The term O(rK + L log L) is a computational
overhead in the (G)NO-IMI but we show in the next sectionthat it is insignificant and has no influence on the scheme
applicability.
After forming the sorted sequence of cells as describedabove, the method starts to traverse the cells and collects
points from these cells into a candidate list.

100

SIFT1B

40

0.2

20

0.1

0.0

IMI

NO-IMI0

IMI

NO-IMI

Figure 3. Normalized mutual information between the indices of
the closest codewords in two codebooks (left) and the percent ofempty index cells (right) for the IMI and NO-IMI systems. The
high value of NMI in the case of DEEP1B and the IMI meansthat the implicit assumption of independent subspaces in the IMI
does not hold for DEEP1B. The large percent of empty cells also
indicates that cell centroids in the IMI represent DEEP1B data distribution poorly.

3.6. Reranking
After short-list extraction the (G)NO-IMI performs
reranking of candidate points in the same manner as it was
proposed in [2, 14]. During the indexing stage we calculate the displacement of each point from its cell centroid
and compress these displacements via Optimized Product
Quantization (OPQ). In the experiments, we used K setsof local PQ codebooks, and each set was shared by the cellswith the same first-order index. We used one global rotation
matrix for all database points.
When querying, each candidate point is reconstructedfrom its OPQ code and the distance between this reconstruction and the given query is evaluated. Finally, candidates are
sorted based on the calculated distances.

3.7. Connection to IVFRVQ
The proposed NO-IMI system is similar to the IVFRVQ
scheme proposed in [8]. Here we highlight the differences
between the NO-IMI and IVFRVQ:
1. IVFRVQ is based on RVQ only, while NO-IMI uses
OPQ to compress the data at the fine level. Not relying
on RVQ at all levels is important for high perfromance,since RVQ degrades when it is applied with large number of codebooks [8].
2. The NO-IMI does not need to keep the norms ofdataset points. IVFRVQ has to keep them, which needs
extra memory and also extra operations during search.
3. IVFRVQ evaluates distances to all cell centroids andthen explores only several inverted lists corresponding
to the closest cells. The NO-IMI does not evaluate distances to all centroids and performs more efficient nonexhaustive evaluation.

4. Experiments
In this section we provide results of experiments thatcompare the Non-Orthogonal Inverted Multi-Indices (NOIMI and GNO-IMI) with the standard Inverted Multi-Index.
The experiments were performed on two datasets:
1. SIFT1B dataset[13] that contains one billion of 128dimensional SIFT descriptors along with precomputed
groundtruth for 10, 000 queries. A hold-out learning set
of 100 million descriptors is also provided.
2. DEEP1B dataset. This is a new dataset that we introduce to the community2 . Descriptors for DEEP1B were
produced in a way similar to [7]. Specifically, we took
the outputs of the last fully-connected layer of a DNN
for a billion images on the Web. Our DNN had the
GoogLeNet[20] architecture and was trained on the ImageNet dataset[1]. The outputs were then compressed by
PCA to 96 dimensions and l2 -normalized. We also prepared hold-out sets containing 350 millions of descriptors for learning and 10, 000 for querying (with known
ground truth for nearest neighbors in the main set).
For both datasets we compare three indexing structures:
1. the inverted multi-index (IMI) with global rotation before dataspace decomposition [9]. The top-performing
systems [14, 5] use this indexing structure, so we use it
as a baseline. We used the authors’ implementation[5];2. the Non-Orthogonal Inverted Multi-Index (NO-IMI);
3. the Generalized Non-Orthogonal Inverted Multi-Index(GNO-IMI).
2 The
dataset and the project
http://sites.skoltech.ru/compvision/noimi/

2060

code

are

availableonRecall@R

1.0

1.0

0.8

0.8

0.6

0.6

0.4

0.4

GNO-IMINO-IMIIMIIVFADC

0.2
0.0
0

5

10
log2 R

0.2

NO-IMI
IMI
0.0
0

15

5

10

15

log2 R

DEEP1B

SIFT1B

Figure 2. Recall as a function of the candidate list length. On DEEP1B (left plot) we compare four systems: IVFADC with 217 codewords,
the IMI with K = 214 and preliminary orthogonal transformation, the NO-IMI and the GNO-IMI with K = 214 . For all recall levels the(G)NO-IMI provides much shorter candidate lists. For SIFT1B dataset (right plot) the advantage of the NO-IMI is negligible.

Dataset
IMI NO-IMI GNO-IMISIFT1B 35923 35207
34981
DEEP1B 0.321 0.272
0.255
Table 1. Average distances from data points to the closest centroid.
Smaller distances usually results in more precise short-lists.

For all the structures we used the same value of K = 214 ,hence all the indices have the same number of cells. All
the structures and the codebooks for database compression
were optimized on the hold-out learning sets.
Representation accuracy. We first check our intuition
that the subspaces corresponding to different halves of deep
data are more correlated for deep data compared to SIFT
descriptors. As described in section 2, the IMI centroids areconstructed using codewords from the two codebooks C1
and C2 , corresponding to orthogonal data subspaces. Let us
introduce two discrete random variables I1 , I2 corresponding to the indices of the closest codewords from C1 and C2
respectively for a certain point. We can measure the normalized mutual information between I1 and I2 using all the
points from the particular dataset. High values of mutual
information would then reveal the correlation between thehalves.
Figure 3 (left) shows values of the normalized mutual information (NMI) for both datasets. For DEEP1B
dataset N M I(I1 , I2 ) is two times higher than for SIFT1B.
This verifies the intuition that the decomposition for deep
data can lead to low performance, even when decorrelating
global rotation (as in OPQ) is fitted during preprocessing.
Figure 3 also shows NMI values for the NO-IMI scheme.
In this case we measure the mutual information between theindices of the closest codewords in codebooks S and T . For
both SIFT1B and DEEP1B the NMI is markedly smaller inthe case of the NO-IMI index, suggesting better adaptivityof the RVQ model over PQ. We additionally calculate thepercent of empty cells for both indexing structures, with theresults shown in Figure 3(right). This further reveals that

the NO-IMI significantly reduces a number of empty index
cells compared to IMI, especially for DEEP1B data.
We further demonstrate the advantage of the (G)NO-IMI
for deep data by measuring the average distance from thedata points to the centroids of cells they belong to. This isa reliable indicator of the indexing quality as smaller distances mean that cells represent the actual data distribution
better. Furthermore, the small distances mean that the displacements from the points to the closest centroids havesmall norms, hence they can be encoded more accurately,
which results in better reranking. The average distances fortwo datasets and three systems are shown in Table 1.
For the deep data the NO-IMI reduces average distanceby 15% compared to the IMI scheme with the same numberof cells. This means that the NO-IMI cell centroids represent data distribution better and we show below that it
results in much more precise short-lists. The more powerful Generalized NO-IMI scheme provides even greater
improvement by 21%. For SIFT1B, the usage of the NOIMI allows to reduce average distance by just three percent,which means that in this metric our approach gives verysmall improvement for this dataset.
Short-list quality. We now compare the retrieval performance of different schemes. In most of experiments we
use the commonly used measure Recall@R, which is calculated as a rate of queries for which true nearest neighboris present in a short-list of a length R.
We plot the values of Recall@R for different values of R
in Figure 2. For DEEP1B dataset (left), the NO-IMI and the
GNO-IMI provide a great improvement in short-list quality over the original IMI. For instance, for the recall level
0.5 the GNO-IMI provides short-lists that are eight time
more compact. For SIFT1B dataset (left), the benefit of
the NO-IMI is negligible as short-lists are improved only
by a very small margin. As the (G)NO-IMI has additional
computational overhead comparing to the IMI, such a small
improvement does not justify the usage of non-orthogonal
2061

0.28

0.55

0.26

0.50

0.65

0.60

0.22

R@10, 8 bytes

R@5, 8 bytes

R@1, 8 bytes

0.55
0.24

0.45

0.40

0.50

0.45

0.20

0.18
0

0.35

GNO-IMI

10

20

30

GNO-IMINO-IMINO-IMI

IMI

IMI

40

50

0.30
0

10

20

30

40

NO-IMI
IMI
50

0.35
0

20

30

40

50

0.8

0.70

0.35

0.30

20

ms

30

40

0.60
0.55
0.50

GNO-IMINO-IMI
IMI
10

0.65

R@10, 16 bytes

R@5, 16 bytes

0.40
R@1, 16 bytes

10

0.75

0.45

0.25
0

GNO-IMI

0.40

GNO-IMINO-IMI
IMI

0.45
50

0

10

20

ms

30

40

0.7

0.6

GNO-IMINO-IMI
IMI

0.5
50

0

10

20

ms

30

40

Figure 4. Comparison of the original IMI, NO-IMI and GNO-IMI in terms of recall after reranking, and runtime on the DEEP1B dataset.
For all systems we used OPQ with local codebooks to compress database points. With few exceptions, for any given time budget above 11
ms the (G)NO-IMI provides considerably higher recall compared to the IMI-based scheme.

multi-indices with SIFT data.
In this experiment we also compare with IVFADC. This
scheme was shown to be less accurate than the IMI on
SIFT1B, but it might potentially offer advantage on otherdata distributions, as it does not perform any space decomposition. For IVFADC we use a considerably larger codebook of size K = 217 , but it still produces noticeably lessaccurate short-lists compared to other schemes.
Reranking and runtime. Finally, we evaluate the(G)NO-IMI in combination with subsequent reranking ofcandidate lists. Our baseline here is the state-of-the-art
Multi-LOPQ system (IMI+reranking), which provides thestate-of-the-art on the SIFT1B dataset.
We perform experiments with M = 8 and 16 reranking codebooks, which corresponds to 8 and 16 bytes per
point respectively. The parameter r in the (G)NO-IMI was
set to 32 in all experiments. For both values of M we plot
Recall@1, Recall@5 and Recall@10 for different lengths
of candidate lists as functions of the corresponding searchruntime. The results are summarized in Figure 4. We highlight several observations based on it:• The timings for the (G)NO-IMI start from 11 milliseconds as this is the cost of the computational overhead.
This time Multi-LOPQ allows to extract and to rerank ashort-list of approximately 25 thousand points. Figure 2
demonstrates that such a small list for the IMI would contain a true nearest neighbor only for 70% queries, hencesuch small lists are quite unreliable.

• For any given time more than eleven milliseconds the(G)NO-IMI produces higher recall values comparing toMulti-OPQ. The margin is up to six absolute percent that
corresponds to 13% of relative improvement.
Memory consumption. We also provide the amount of
total memory consumption for all systems. The NO-IMI requires one additional gigabyte to keep the terms hSi , Tj i,
i, j = 1, . . . , K. The GNO-IMI also requires one gigabyte
to keep K 2 elements of α-matrix. Overall, the amount ofadditional memory is relatively small. For example, in thesetting with 16 bytes, memory consumption equals 23 gigabytes for Multi-LOPQ and 25 gigabytes for the GNO-IMI.

5. Conclusion
We investigated indexing structures for deep descriptors. We have shown that the original Inverted Multi-Index
is suboptimal for deep data and have introduced two systems for billion-scale indexing, the Non-Orthogonal Inverted Multi-Index and the Generalized Non-Orthogonal
Inverted Multi-Index, which provide more accurate indexing and more precise candidate lists. The advantages ofthe (G)NO-IMI come at a price of computational overhead,
which is small for typical settings.

Acknowledgements
We thank Konstantin Lakhman for his help with data collection. Victor Lempitsky is supported by the Russian Ministry of Science and Education grant RFMEFI57914X0071.
2062

50

References[20] C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed,
D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich.
[1] A Berg and J Deng and and L Fei-Fei.
Large
Going deeper with convolutions. In CVPR, 2015. 6
scalevisualrecognition
challenge(ILSVRC).
[21] T. Zhang, C. Du, and J. Wang. Composite quantization for
http://www.image-net.org/challenges/LSVRC/2010/,
approximate nearest neighbor search. In ICML, 2014. 2, 3
2010. 6[2] A. Babenko and V. Lempitsky. The inverted multi-index. In
CVPR, 2012. 1, 3, 6
[3] A. Babenko and V. S. Lempitsky. Additive quantization for
extreme vector compression. In CVPR, 2014. 2, 3
[4] A. Babenko and V. S. Lempitsky. Aggregating deep convolutional features for image retrieval. In International Conference on Computer Vision - ICCV, 2015. 1[5] A. Babenko and V. S. Lempitsky. The inverted multi-index.
IEEE Trans. Pattern Anal. Mach. Intell., 37(6):1247–1260,
2015. 1, 6
[6] A. Babenko and V. S. Lempitsky. Tree quantization for largescale similarity search and classification. In CVPR, 2015. 2,
3[7] A. Babenko, A. Slesarev, A. Chigorin, and V. S. Lempitsky.
Neural codes for image retrieval. In European Conference
on Computer Vision - ECCV, pages 584–599, 2014. 1, 6
[8] Y. Chen, T. Guan, and C. Wang. Approximate nearest neighbor search by residual vector quantization. In Sensors, 2010.
2, 3, 6[9] T. Ge, K. He, Q. Ke, and J. Sun. Optimized product quantization. Technical report, 2013. 1, 3, 6
[10] T. Ge, K. He, Q. Ke, and J. Sun. Optimized product quantization for approximate nearest neighbor search. In CVPR,
2013. 2[11] Y. Gong, L. Wang, R. Guo, and S. Lazebnik. Multi-scaleorderless pooling of deep convolutional activation features.
In 13th European Conference on Computer Vision (ECCV),
pages 392–407, 2014. 1[12] H. Jégou, M. Douze, and C. Schmid. Product quantization
for nearest neighbor search. TPAMI, 33(1), 2011. 1, 2
[13] H. Jegou, R. Tavenard, M. Douze, and L. Amsaleg. Searching in one billion vectors: Re-rank with source coding. In
ICASSP, 2011. 1, 3, 6
[14] Y. Kalantidis and Y. Avrithis. Locally optimized productquantization for approximate nearest neighbor search. In in
Proceedings of International Conference on Computer Vision and Pattern Recognition (CVPR 2014). IEEE, 2014. 1,3, 6[15] D. Nistér and H. Stewénius. Scalable recognition with a vocabulary tree. In CVPR, 2006. 4[16] M. Norouzi and D. J. Fleet. Cartesian k-means. In CVPR,
2013. 2[17] A. S. Razavian, H. Azizpour, J. Sullivan, and S. Carlsson. CNN features off-the-shelf: An astounding baseline
for recognition. In IEEE Conference on Computer Vision
and Pattern Recognition, CVPR Workshops, pages 512–519,
2014. 1[18] A. S. Razavian, J. Sullivan, A. Maki, and S. Carlsson. Visual
instance retrieval with deep convolutional networks. CoRR,
abs/1412.6574, 2014. 1[19] J. Sivic and A. Zisserman. Video google: A text retrieval
approach to object matching in videos. In ICCV, 2003. 1, 3

2063