PQTable: Fast Exact Asymmetric Distance Neighbor Search
for Product Quantization using Hash Tables
Yusuke Matsui Toshihiko Yamasaki Kiyoharu Aizawa
The University of Tokyo, Japan{matsui, yamasaki, aizawa}@hal.t.u-tokyo.ac.jp

handle large (e.g., N = 109 ) databases, short-code-based
inverted indexing systems [1, 23, 7, 15, 3, 4] have been proposed, which are currently state-of-the-art ANN methods(see Fig. 1b). Such systems operate in two stages: (1) coarse
quantization and (2) reranking via short codes. A database
vector is first assigned to a bucket using a coarse quantizer(e.g., k-means [13], multiple k-means [23], or Cartesian
products [1, 12]), then compressed to a short code using
PQ [13] or its extensions [17, 7] and finally stored as a posting list 1 . In the retrieval phase, a query vector is assigned
to the nearest buckets by the coarse quantizer, then associated items in corresponding posting lists are traversed, with
the nearest one being reranked via ADC 2 . These systems
have been reported as being fast, accurate, and memory efficient, by being capable of holding one billion data points
in memory and conducting a retrieval in milliseconds.
However, such inverted indexing systems are built by
a process of carefully designed manual parameter tuning.
The processing time and recall rates strongly depend on
the number of space partitions in the coarse quantizer, andits optimal size needs to be decided manually, as shownin Fig. 2. For example, this simple example shows thatk = 1024 is the fastest setting for N = 107 , but the slowest
for N = 108 . These relationships do not become clear until several parameter combinations for the coarse quantizers
are examined. However, training and testing coarse quantizers is computationally expensive. For example, we foundthat, to plot a single dot of Fig. 2 for N = 109 , the training
took around a day and building the inverted index structure
took around three days, using 16-core machines. This isparticularly critical for a recent per-cell training ANN system [3, 15], which requires even more computation to build
the system. It should be pointed out that achieving stateof-the-art performances by ANN systems depends largely
on special tuning for the testbed dataset, e.g., SIFT1B [14].
There is no guarantee that we can always achieve the best
performance by such systems. In real-world applications,

Abstract
We propose the product quantization table (PQTable), a
product quantization-based hash table that is fast and requires neither parameter tuning nor training steps. The
PQTable produces exactly the same results as a linear PQ
search, and is 102 to 105 times faster when tested on the
SIFT1B data. In addition, although state-of-the-art performance can be achieved by previous inverted-indexing-based
approaches, such methods do require manually designed
parameter setting and much training, whereas our method
is free from them. Therefore, PQTable offers a practical anduseful solution for real-world problems.

1. Introduction
With the explosive growth of multimedia data, compressing high-dimensional vectors and performing approximate nearest neighbor (ANN) searches in the compressed
domain is becoming a fundamental problem in handlinglarge databases. Product quantization (PQ) [13], and its
extensions [17, 7, 2, 24, 21, 11, 5, 25], are popular and successful methods for quantizing a vector into a short code.
PQ has three attractive properties: (1) PQ can compress
an input vector into an extremely short code (e.g., 32 bit)that enables it to handle typically one billion data points
in memory at once; (2) the approximate distance between
a raw vector and a compressed PQ code can be computed
efficiently (the so-called asymmetric distance computation(ADC) [13]), which is a good estimate of the original Euclidean distance; and (3) the data structure and coding algorithms are surprisingly simple. By quantizing database vectors into short codes in advance, vectors similar to a given
query can be found from the database codes by a linear comparison of the query with each code using ADC (see thelinear ADC scan in Fig. 1a).
Although a linear ADC scan is simple and easy to use,
ANN search by linear ADC scanning is efficient only forsmall datasets because the search is exhaustive, i.e., thecomputational cost is at least O(N ) for N PQ codes. To

1 In practice, the residual difference between the query vector and thecodeword is encoded.
2 There are smarter versions of this computation [3].

1

...

Database codes
1

34 76

2
204
187
52

103

3

...

13

...
43

2

13

5

Query vector

Identifiers + PQ codes

199

Reranking

202
23

Query vector

Identifiers0
1

76 160 202 23

PQ code255 255 255 255

Identifiers + PQ codes(a) Linear ADC scan

Entry
0 0
0 0

(b) Short-code-based inverted indexing system

413 352
87

...

2
49

Coarsequantizer

Encode 160 Hash

101

...

Query vector

33

76

0
0

...

67

Linearscan

Bucket123

Hash table(c) Proposed PQTable

Figure 1: Data structures of ANN systems: linear ADC scan, short-code-based inverted indexing systems, and PQTable.

1.5

0.2

Recall@1

0.18
0.16

time [ms]k=1024k=2048k=4096k=81920.14

1k=1024k=2048k=4096k=8192

0.5

0.12
0.1
10 6

10 7
N

(a) Recall@1

10 8

0
10 6

10 7
N

10 8

(b) Runtime per query

Figure 2: Performance of a short-code-based inverted indexing system (IVFADC [13]), showing the relationship between the database size, N , and Recall@1 or runtime per
query for various k, which is the number of space partitions
for the coarse quantizer. The search range w is set to one.
Note that the search range is also an important parameter,
which has been chosen manually.
it often happens that cumbersome trial-and-error-based parameter tuning is required, which might well turn ordinary
users away from these systems.
To achieve an ANN system that would be suitable forpractical applications, we propose the PQTable, an exact, nonexhaustive, NN search method for PQ codes (seeFig. 1c). We do not employ an inverted index data structure, but find similar PQ codes directly from the database.
This achieves exactly the same accuracy as a linear ADC
scan, but requires a significantly shorter time (10.3 ms, instead of 18 s, for the SIFT1B data using 64-bit codes). In
other words, this paper proposes an efficient ANN search
scheme to replace a linear ADC scan when N is sufficiently
large. As discussed in Section 4, the parameter values required to build the PQTable can be calculated automatically.
Note that, as discussed in Section 5, PQTable requires larger
memory footprints than storing PQ codes linearly.
The main idea of the PQTable is the use of a hash table,
where the PQ code itself is used directly as an entry in thehash table (see Fig. 1c). That is, identifiers of PQ codes inthe database are directly associated with the hash table byusing the PQ code itself as an entry. Given any new query
vector, it can be PQ coded and identifiers associated withthe entry are retrieved.
There are advantages and disadvantages in the use of inverted indexing systems as well as for our proposed method.

Inverted indexing systems are accurate and fast, but they dorequire manual parameter tuning and time-consuming training. The PQTable can achieve the same recall rates as a linear ADC, but its performance (accuracy, runtime, and memory usage) may lag the latest inverted indexing systems withthe best parameters. The PQTable does not require any parameter tuning or training steps for the coarse quantizers,
which are important aspects of real-world applications.

Relationship with previous methods
Hamming-based ANN systems: As an alternative to
PQ-based methods, another major approach to ANN are theHamming-based methods [22, 8, 20], in which two vectors
are converted to bit strings whose Hamming distance approximates their Euclidean distance. Comparing bit strings
is faster than comparing PQ codes, but is usually less accurate for a given code length [10].
In Hamming-based approaches, bit strings can be linearly scanned by computing their Hamming distance, which
is similar to linear ADC scanning in PQ. In addition, a multitable algorithm has been proposed to facilitate fast ANN
search [18], which computes exactly the same result as alinear Hamming scan but is much faster. However, a similar
querying algorithm and data structure for fast computing
have not been proposed for the PQ-based method to date.
Our work therefore extends the idea of such a multitable algorithm [18, 9] to PQ codes, where a Hamming-based formulation cannot be applied directly.
Extensions to PQ: Recent reports [24, 2, 5, 25] haveproposed a new encoding scheme that is regarded as a generalized version of PQ. Because the data structure used inthese approaches is similar to PQ, our proposed method canalso be applied to such approaches. In this paper, we discuss
only the core of the PQ process for simplicity.

2. Background: Product Quantization
In this section, we briefly review PQ [13].
Product quantizer: Let us denote any x ∈ RD as aconcatenation of M subvectors: x = [x1 , . . . , xM ], where
we assume that the subvectors have an equal number of dimensions D/M , for simplicity. A product quantizer q(·) is(1)xm 7→ q m (xm ) = arg min kxm − cm k .
cm ∈C m(2)

mwhere each subquantizer q (·) is defined as

Each subcodebook C m comprises K D/M -dim centroids
learned by k-means [16]. Therefore, q(x) maps an input x
to a codeword c = [c1 , . . . , cM ] ∈ C = C 1 × · · · × C M .
Because c is encoded as a tuple (i1 , . . . , iM ) of M subcentroid indices, where each im ∈ {0, . . . , K − 1}, it canbe represented by M log2 K bits. Typically, K is set as a
power of 2, making log2 K an integer. In this paper, we set
K as 256 (this is the typical setting used in many papers,
for which cm is represented by 8 bits), and M is set as 1, 2,
4, or 8, which yields a length for the code of 8, 16, 32, or 64
bits, respectively.
ADC: Distances between encoded vectors and a raw
vector can be computed efficiently.
Suppose that thereare N data points Y = y j ∈ RD j = 1, . . . , N thathave been encoded and stored. Given a new query vectorx ∈ RD , the squared Euclidean distance from x to a point
y is approximated by asymmetric distance (AD):dAD (x, y)2 =MX2d (xm , q m (y m )) .

(3)

m=1

This can be computed as follows. First, xm is encoded byits corresponding subcodebook, C m , thereby generating a
distance table whose size is M × K, where each (m, k)
entry denotes the squared Euclidean distance between xm
and the k-th subcentroid in C m , namely cm
k . Suppose that asubvector y m of each y is encoded in advance as cm
k , i.e.,q m (y m ) = cm
k . It follows that an (m, k) in the distance ta2
mm
m 2
ble means d (xm , cmk ) = d (x , q (y )) . We can thencompute Eq. (3) by simply looking up the distance table M
times and summing the distances. The computational costof the whole process is O(KD + N M ), which is fast forsmall N but still linear in N .

3. PQTable
As shown in Fig. 1c, the proposed system involves a hashtable within which the PQ code itself is used as an entry. In
the retrieval phase, a query vector is PQ coded and identifiers associated with the entry are retrieved. This is verystraightforward, but there are two problems to be solved.
The empty-entries problem: Suppose that a new query
is PQ coded and hashed. If the identifiers associated withthe entry of the query are not present in the table, the hashing fails. To continue the retrieval, we would need to findcandidates for the query by some other means.

Probability

10 0

defined as a concatenation of subquantizers:
x 7→ q (x) = q 1 x1 , . . . , q M xM ,

10 -5

10 6

b=16
b=32
b=64

10 7

10 8

10 9

N

Figure 3: The probability of finding the first nonempty entry (the first identifier). Plots are computed over 50 queries
from the SIFT1B data for various code lengths b.
The long-code problem: Even if we can find the candidates and continue querying, the retrieval is not efficient if
the length of the codes is very long compared to the size ofthe database, e.g., 64-bit codes for 109 vectors. Fig. 3 shows
the relationship between the number of database vectors andthe probability of finding the first nonempty entry. If thelength of the codes b is 16 or 32 bits, there is a high probability that the first identifiers can be found by the first hashing. However, for the case where b = 64, candidate entries
need to be generated 105 times to find the first nonempty
entry. This is caused by the wide gap between the number of possible candidates, 2b , which measures the numberof entries in the table, and the number of database vectors.
This imbalance causes almost all entries to be empty3 .
To handle these two issues, we first present a candidate
generation scheme, which is mathematically equivalent toa multisequence algorithm [1], to solve the empty-entries
problem. Then we propose table division and merging tohandle the long-code problem.
We first show the data structure and a querying algorithm for a single table. To be able to use a single table, we need to handle the empty-entries problem, so we
present a candidate-generation scheme to solve it. Then,because a single table cannot handle large codes (the longcode problem), we propose table division and merging tohandle codes of any length.

3.1. Single Hash Table
The basic idea of the proposed method is to use a hashtable, as shown in Fig. 4a. We prepare a hash table comprising the PQ codes themselves, i.e., a table entry is a tupleof 8-bit integers. During offline processing in advance, thej-th database vector y j is compressed by PQ. The resultant
PQ code (i1j , . . . , iMj ) is used directly as an entry in the hashtable and its identifier j is associated with the entry. If several vectors are associated with the same entry, as shown for“413” and “352” in Fig. 4a, both of them are stored. Notethat the distances from the query to these vectors are thesame because they are quantized as the same code. In online processing, an input query vector x is compressed to3 This is a similar problem to that of designing a coarse quantizer for
an inverted indexing-based ANN system, but we found an optimal solution
empirically, as discussed later.

Hash table43

2. 13 192 322

13 192 3589

255 2552

456 223(iii) Find thesame identifier:43

76 160 202 23
255 255 255 255
Entry

Result(i) Querying for Table 1

87

Query vector

0
0

0
1

...

Generate candidate
entries413 352...

Query vector

0
1

...

... ...

8. 76 160 202 23

0
0

...

1. 13 192 3

0
0

0
1

...

0
0

0
0

123
Identifiers(a) Single table (M = 4). # entries is (28 )M = 232

Result255 255(ii) Querying for Table 2

24

456 242 134(iv) Find the nearest one
from the marked identifiers(b) Multitables (M = 4, T = 2). # entries for each table is (28 )M/T = 216

Figure 4: Overview of the proposed method.
(i1 , . . . , iM ) by PQ, and identifiers associated with the PQ
code of the query are searched.
If an identifier is found (∃ j, im = imj for all m), it is obviously the nearest entry in terms of AD because the codeword that is the nearest to the query is (i1 , . . . , iM ), by definition. A problem arises if there are no identifiers associatedwith the PQ code of the query, e.g., (13, 192, 3, 43) is the
PQ code of a query for which there is no associated identifier in the hash table in Fig. 4a. This is the empty-entries
problem described above. In such cases, we need to find a
candidate entry for the PQ code, which will be the second
nearest to the query in terms of AD. To find the top K nearest identifiers, the search continues for candidates until K
identifiers are found, giving a set of results that are sorted
automatically in terms of AD.
Given a query vector, how can candidate entries be generated? We present a candidate-generation scheme (the“Generate candidate entries” box in Fig. 4a). Given a query
vector, it produces candidate codes that are sorted in ascending order of AD. This scheme is mathematically equivalent
to the higher-order multisequence algorithm proposed byBabenko and Lempitsky [1]. They used this algorithm originally to divide the space into Cartesian products for coarse
quantization. We found that it can be used to enumerate all
possible PQ code combinations in ascending order of AD.
We give the pseudocode for the multisequence algorithm
used in our implementation in the supplementary materials.
Pseudocode for an algorithm that queries a single tableis shown in Alg. 1, where x denotes the input vector, table
is the PQTable filled with database PQ codes, and K is theuser-specified number of output identifiers. The output u[ ]is a sequence of identifiers ordered in terms of AD between
the query and the database vectors. cand is a priority queue
composed of PQ code, and used for the multisequence algorithm. The norm | · | of a sequence means the numberof elements of the sequence. Hash(·) fetches items using
the input code as an entry and returns a set of associatedidentifiers. Insert(·) simply adds items to the end of the ar-

Algorithm 1: Querying for a single table.
Input: x, table, K
Output: u[ ] : ranked identifiers
1 u[ ] ← ∅// array
2 cand ← Init(x)// priority queue
3 while |u| < K do
4code ← NextCode(cand)5{u′ } ← table.Hash(code)6
u.Insert({u′ })ray. We omit d table and returned cand from NextCode,for simplicity. Please refer to the implementation details forthe multisequence algorithm (Init and NextCode) [1] in the
supplementary materials.

3.2. Multiple Hash TableThe single-table version of PQTable may not work when
there are long PQ codes, such as 8 ≤ M (64 bits). Thisis the long-code problem described above, where the number of possible entries is too large for efficient processing.
The number of entries is (28 )M for an 8M bit code, andthe number of database vectors can be at most one billion.
Therefore, most of the entries will be empty if M is 8 orgreater ((28 )8 = 264 ∼ 1.8 × 1019 ≫ 109 ).
To solve this problem, we propose a table division andmerging method. The table is divided as shown in Fig. 4b.
If an 8M -bit code table is divided into two 4M -bit codetables, the number of the entry decreases, from (28 )M =256M for one table to (28 )M/2 = 16M for two tables. By
properly merging the results from each of the small tables,
we can obtain the correct result.
If we have b-bit PQ codes for the database vectors, weprepare T b/T -bit tables. During offline processing in advance, the j-th PQ code is divided by T and inserted in thecorresponding table. In online processing, we first computeranked identifiers from each table in the same way as for the
single table case (see Fig. 4b (i, ii)).

Denote the ranked identifiers from the t-th table as {utn },where t = 1, . . . , T , and n = 1, 2, . . . . We can then checkthe identifiers from the head (n = 1) until the same identifier u∗ is found from all of the tables, i.e., u1n∗1 = u2n∗2 =· · · = uTn∗ ≡ u∗ , where n∗t means u∗ is found in the n∗t -thTelement of the t-th ranked identifiers (see Fig. 4b (iii)). If
the same identifier is found, we pick up all of the checked
identifiers, i.e., ut1 , · · · , utn∗t −1 for all t, referred to as themarked identifiers (shaded gray in Fig. 4b) and compute
their AD to the query. It is guaranteed that all identifiers
whose AD is less than dAD (x, y u∗ ) will be included among
the marked identifiers (see the supplementary material for
proof). Therefore, by simply sorting the marked identifiersin terms of AD, we can find all of the nearest identifiers in
the database with AD less than dAD (x, y u∗ ) (see Fig. 4b(iv)). This process is repeated until the desired number of
output identifiers is obtained.
Pseudocode for querying multiple PQTables is shown in
Alg. 2. Unlike the single-table case, tables[ ] is an array oftables. u dist[ ] and marked[ ] are each an array of tuples,comprising an identifier and its AD to the query. u dist[ ] isthe final result and marked[ ] is used as a buffer. Split(·, T )divides the priority queues into T smaller priority queues.
Check(·) and UnCheck(·) are used to record how manytimes identifiers have appeared in the process. They are implemented by an associative array in our method. Because
each identifier is included once in each table, and therefore
can be checked at most T times. An identifier that has appeared in all tables can be detected by seeing if it has beenchecked T times or not. PartialSortByDist(·, K) sorts anarray of tuples in terms of distance, obtaining the top K results at a computational cost of O(N log K), where N is
the length of the array. The function array.Less(d) returns
those elements whose distances are less than d. Note thatdAD (i) is an abbreviation of dAD (x, y i ).

4. Empirical Analysis for Parameter Selection
In this section, we discuss how to determine the value ofthe parameter required to construct the PQTable. Supposethat we have N PQ-coded database vectors of code lengthb. To construct the proposed PQTable, we need to decide
one parameter value T , which is the number of dividing tables. If b = 32, for example, we need to select the data
structure as being either a single 32-bit table, two 16-bit tables, or four 8-bit tables, corresponding to T = 1, 2, and 4,
respectively. We first show that the statistics of the assigned
vectors are strongly influenced by the distribution of thedatabase vectors, and present an indicative value, b/ log2 N ,as proposed by previous work on multitable hashing [9, 18],that estimates the optimal T .
Because the proposed data structure is based on a hashtable, there is a strong relationship between N , the number of entry 2b , and the computational time. If N is small,

Algorithm 2: Querying for multitables.
Input: x, tables[ ], K
Output: u dist[ ] : ranked identifiers with distances
1 u dist[ ] ← ∅// array
2 T ← |tables|
3 cands[ ] ← Split(Init(x), T ) // priority queues
4 marked[ ] ← ∅// array
5 while |u dist| < K do
6
for t ← 1 to T do
7code ← NextCode(cands[t])8{ut } ← tables[t].Hash(code)9
for u ∈ {ut } do
10
Check(u)11
if u has been checked T times then12{i′ } ← Pick up checked identifiers
13
for i ∈ {i′ } ∪ u do
14
marked.Insert(tuple(i, dAD (i)))
15
UnCheck(i)PartialSortByDist(marked, K)u dist.Insert(marked.Less(dAD (u)))

1617almost all of the entries in the table will not be associatedwith identifiers, and generating candidates will take time. If
N is appropriate and the entries are well filled, the search isfast. If N is too large compared with the size of the entry,
all entries are filled and the number of identifiers associatedwith each entry is large, which can again cause slow fetching. We show the relationship between N and the computational time for 32-bit codes and T = 1, 2, and 4 in Fig. 5a,and for 64-bit codes and T = 2, 4, and 8 in Fig. 5b. Notethat these graphs are log–log plots. For example, the tablewith T = 1 computes 105 times faster than a linear ADC
scan when N = 109 in Fig. 5a. From these figures, eachtable has a “hot spot.” In Fig. 5a, for N = 102 to 103 , 104
to 105 , and 106 to 109 , T = 4, 2, and 1 are the fastest, respectively. Given N and b, we need to decide the optimal T
without actually constructing tables.
We can show that the statistics in the table are strongly
influenced by the distribution of the input vectors. Consider
the average number of candidates generated s in finding thenearest neighbor. For the case of a single table, this represents the number of iterations of the while loop in Alg. 1. If
all vectors are equally distributed among the entries, we canestimate the average number s̄ by a fill factor p ≡ N/2b ,which shows how well the entries are filled. Because theprobability of finding the identifiers for the first time in thes-th step is (1 − p)s−1 p when p < 1, the expected value ofs for finding the item for the first time is

s̄ =

 P∞

s=1 (1 − p)1

s−1

ps = p1(if p < 1)
(if p ≥ 1).

(4)

Table 1: Estimated and actual number of steps to find an
item for the first time, and actual number of retrieved items
for the first entry, for 32-bit codes from the SIFT1B data.

10 5time per query [ms]

10

4

10 3

ADC
T=1
T=2
T=4
T*

10 2

# steps# items

10 1

10 -1

b = 32
10 3

10 4

10 5

10 6

10 7

10 8

10 9

N

b = 64(a) 32-bit PQ codes from the SIFT1B data.

time per query [ms]

10 3

ADC
T=2
T=4
T=8
T*

106
1.7 × 102
4.3 × 103
12

107
25
4.3 × 102
1.2 × 102N
ActualT∗
Actual
T∗

102
4
4
8
8

103
4
4
8
8

104
2
2
8
4

105
2
2
4
4

106
1
2
4
4

T ∗ = 2Q(log2 (b/ log2 N )) ,

108
6.0
43
1.2 × 103

109
1.1
4.3
1.1 × 104

107
1
1
4
2

108
1
1
2
2

109
1
1
2
2

(5)

where Q(·) is the rounding operation. A comparison withthe actual number is shown in Table 2. In many cases, theestimated T ∗ is a good estimation of the actual number, andthe error was small even if the estimation failed, such as in
the case of b = 32 and N = 106 (see Fig. 5a). Selected T ∗values are plotted as gray dots in Fig. 5a and Fig. 5b.

10 2
10 1
10 0
10 -1
10 -2
10 2

105
2.5 × 103
4.3 × 1042.1

posed table, we quantize the indicative number into a powerof two, and the final optimal T ∗ is given as

10 5
10 4

104
2.8 × 104
4.3 × 105
1.1

Table 2: Estimated and actual T for the SIFT1B data.

10 0

10 -2
10 2

N
ActualEstimate(s̄)
Actual

10 3

10 4

10 5

10 6

10 7

10 8

10 9

N

(b) 64-bit PQ codes from the SIFT1B data.

Figure 5: Runtime per query of each table.
This estimated number and the actual number required tofind the identifiers, evaluated for the SIFT1B data, areshown in Table 1. There is a very large gap between theestimated and actual number (roughly 10 times) for all N .
In addition, the table gives the number of assigned items
for the entry when the nearest items are found, which corresponds to |{u′ }| in Alg. 1 when hashing returns identifiers
for the first time. This number is surprisingly large when N
is very large. For example, for the case of N = 109 , the firstcandidate usually has associated identifiers (s is actually1.1), with 1.1 × 104 identifiers being assigned to that entry.
This is surprising because, if the identifiers were distributed
equally, the estimated step s would be 4.3, and the numberof associated identifiers would be less than 1 for each entry.
This heavily biased behavior, caused by the distribution of
the input vectors, prevented us from theoretically analyzing
the relationship between the various parameters. Therefore,
we chose to employ an empirical estimation procedure fromthe previous literature, which was both simple and practical.
The literature on multitable hashing [18, 9] suggests thatan indicative number, b/ log2 N , can be used to divide thetable. Our method is different from those in previous studies because we are using PQ codes. However, this indicative
number can provide a good empirical estimate of the optimal T in our case. Because T is a power of two in the pro-

5. Experimental Results
We present our experimental results using the proposed
method. The evaluation was performed using the SIFT1B
data from the BIGANN dataset [14], which contain one billion 128-D SIFT features and provide learning and querying vectors, from which we used 10 million for learningand 1,000 for querying. The centers of the PQ codes weretrained using the learning data (this learning process is required for all PQ-based methods), and all database vectors
were converted to 32- or 64-bit PQ codes. Note that we selected T using Eq. (5). All experiments were performed ona notebook PC with a 2.8 GHz Intel Core i7 CPU and 32 GB
RAM. Results using another data, GIST1M, are presented
in the supplementary materials, which shows the same tendency as for SIFT1B.
Speed: Figure 6 shows the runtimes per query for the
proposed PQTable and a linear ADC scan. The results for
32-bit codes are presented in Fig. 6a and Fig. 6b. The ADC
runtime depends linearly on N and required 16.4 s to scan
N = 109 vectors, but the runtime for the PQTable was lessthan 1 ms for all cases. When the database size N was
small, the ADC was faster. Note that the time to encode thequery vector was more significant than the retrieval itself
for N ≤ 102 . The proposed method was faster for the casewhere N > 105 , and was approximately 105 times fasterthan the ADC for N = 109 , even for the 1-, 10-, and 100NN cases. Fig. 6c and Fig. 6d show the results for 64-bit
PQ codes. The speedup was less dramatic than for the 32bit cases, but was still 102 to 103 times faster than the ADC,

1.5
1
0.5
0

0

2

4

6

8

N

10
#10

(a) Plot of 32-bit PQ codes.

8

2

ADC
100-NN
10-NN
1-NN

10 4
10 3

time per query [ms]ADC
100-NN
10-NN
1-NN

10 2
10 1
10 0
10 -1
10 -2
10 2

10 3

10 4

10 5

10 6

10 7

10 8

10 9

10 5

#10 4
ADC
100-NN
10-NN
1-NN

1.5
1
0.5
0

0

2

4

6

8

N

N

(b) Log–log plot of 32-bit PQ codes.

time per query [ms]

10 5

#10 4

time per query [ms]time per query [ms]

2

10
#10

8

(c) Plot of 64-bit PQ codes.

ADC
100-NN
10-NN
1-NN

10 4
10 3
10 2
10 1
10 0
10 -1
10 -2
10 2

10 3

10 4

10 5

10 6

10 7

10 8

10 9

N

(d) Log–log plot of 64-bit PQ codes.

Figure 6: Runtimes per query for the proposed PQTable with 1-, 10-, and 100-NN, and a linear ADC scan (SIFT1B data).
10 11

Speed-up factors for k-NN vs. ADC
1-NN
10-NN
100-NN
1.0 × 105 9.7 × 104 9.5 × 104
1.7 × 103 8.4 × 102 3.1 × 102

10 10

8

9

ADC
16.4 s18.0 sparticularly for N = 10 to N = 10 , where the runtime
was 10.3 ms for N = 109 in the 1-NN case. We report the
speedup factors with respect to the linear ADC in Table 3.
Accuracy: Accuracy results for the proposed method
are: Recall@1=0.001, @10=0.019, and @100=0.071,
for 32-bit codes, with Recall@1=0.067, @10=0.249, and@100=0.569, for 64-bit codes, for N = 109 . Note that allvalues are the same as for the linear ADC scan case.
Memory usage: We show the estimated and actual
memory usage of the PQTable in Fig. 7. For the case ofa single table, the theoretical memory usage involves theidentifiers (4 bytes for each) in the table and the centroidsof the PQ codes, a total of 4N + 4KD bytes. For multitable cases, each table needs to hold the identifiers, and the
PQ codes are also required for computing dAD . Here, thefinal memory usage is (4T + b/8)N + 4KD bytes. These
are theoretical lower-bound estimates. As a reference, we
also show the cases when PQ codes are lineary stored forthe linear ADC scan (bN/8 + 4KD bytes) in Fig. 7.
For the N = 109 with b = 64 case, the theoretial memory usage is 16 GB, and the actual cost is 19.8 GB. Thisdifference comes from an overhead for the data structure ofhash tables. For example, for 32-bit codes in a single table, directly holding 232 entries in an array requires 32 GB
of memory, even if all of the elements are empty. This isbecause a NULL pointer requires 8 bytes with a 64-bit machine. To achieve more efficient data representation, we employed a sparse direct-address table [18] as the data structure, which enabled the storage of 109 data points with asmall overhead and provided a worst-case runtime of O(1).
When PQ codes are linearly stored, it requires only 8 GB
for N = 109 with b = 64. Therefore, we can say there is atrade-off among the proposed PQTable and the linear ADC
scan in terms of runtime and memory footprint (18.0 s with
8GB v.s. 10.3 ms with 19.8 GB).

Memory usage [byte]

b
32
64

Table 3: Speed-up factors for N = 109 .

10 9
10 8

b=64 Estimated boundb=64 Actual
b=64 Linear
b=32 Estimated bound
b=32 Actual
b=32 Linear

10 7
10 6
10 5
10 4

10 5

10 6

10 7

10 8

10 9

N

Figure 7: Memory usage for the tables using the SIFT1B
data. The dashed lines represent the theoretically estimatedlower bounds. The circles and boxes represent the actual
memory consumption for 32- and 64-bit tables. We also
show the linearly stored case for the ADC scan.
Distribution of each component of the vectors: We
investigated how the distribution of vector components affects the search performance, particularly for the multitable case. We prepared the SIFT1M data, using principalcomponent analysis (PCA), to have the same dimensionality (128). Then both the original SIFT data and the PCAaligned SIFT data were zero-centered and normalized to enable a fair comparison. Finally, the average and standard
deviation for all data were plotted, as shown in Fig. 8. In
both cases, a PQTable with T = 4 was constructed and dimensions associated with each table were plotted using thesame color. Note that the sum of the standard deviation foreach table is shown in the legends.
As shown in Fig. 8a, the values for each dimension are
distributed almost equally, which is the best case for our
PQTable. On the other hand, Fig. 8b shows a heavily biased distribution, which is not desirable because elements
in Tables 2, 3, and 4 have almost no meaning. In such asituation, however, the search is only two times slower thanfor the original SIFT. From this, we can say the PQTable remains robust for heavily biased element distributions. Notethat the recall value is lower for the PCA-aligned case because PQ is less effective for biased data [13].
Comparative study: A comparison with existing systems for the SIFT1B data with 64-bit codes is shown in Table 4. We compared the proposed PQTable with two short-Table 4: A performance comparison for different methods using the SIFT1B data with 64-bit codes. The bracketed values
are from [4]. We show recall values involving similar computational times to those for PQTable.
SystemPQTableIVFADC [13]OMulti-DOADC-Local [4]

#Cell
213

List len (L)8 million

R@1
0.067
0.104 (0.112)

R@10
0.249
0.379 (0.343)

R@100
0.569
0.758 (0.728)

Time [ms]10.3
111.6 (155)

Memory [Gb]
19.8
(12)

Required params
None#Cell, L

214 × 214

10000

(0.268)(0.644)(0.776)(6)(15)

table-order, k, L

0.2
Table1: 2.2733
Table2: 2.8543
Table3: 2.8486
Table4: 2.268

Value

0.15
0.1
0.05
0
-0.05
-0.1

0

20

40

60

80

100

120

Dimension(a) Original SIFT data. Runtime per query: 6.45 ms. Recall@1=0.25
0.6
Table1: 4.2305
Table2: 1.8686
Table3: 1.2227
Table4: 0.83026

Value

0.4
0.2
0
-0.2
-0.4
-0.6

0

20

40

60

80

100

120

Dimension(b) PCA-aligned SIFT data. Runtime per query: 12.94 ms. Recall@1=0.17

Figure 8: The average and standard deviation for the original SIFT vectors and the PCA-aligned vectors.
code-based inverted indexing systems, IVFADC [13] andOMulti-D-OADC-Local [4, 3, 15]. IVFADC is the simplest system, and can be regarded as the baseline, where
the coarse quantizer uses a k-means method. OMulti-DOADC-Local is a current state-of-the-art system, where thecoarse quantizer involves PQ [1], the space for both thecoarse quantizer and the short code is optimized [7], andthe quantizers are per-cell learned [3, 15]. Note that the T
for the PQTable is automatically set to two by using Eq. (5).
From the table, IVFADC has slightly better accuracy, but
is usually slower than PQTable. IVFADC requires two parameters to be tuned, namely the number of space partitions #Cell and the length of the returned list L. The bestperforming system, OMulti-D-OADC-Local, can produce
superior results. It can achieve better accuracy and memory
usage than PQTable. Regarding memory, as discussed in
the previous sebsection, the memory overhead of PQTabe
is not so small. As for computational cost, both are similar,
but OMulti-D-OADC-Local is better with the best parameters. However, it has three parameters to be tuned, namely
table-order, k, and L. All have to be tuned manually. In addition, several training steps are required, namely learning
the coarse quantizer and constructing local codebooks, bothof which are usually time-consuming.
From the comparative study, we can say there are advantages and disadvantages for both the inverted indexing

Required training step
None
Coarse quantizer
Coarse quantizer, local
codebooksystems and our proposed PQTable. Static vs. dynamic
database: For a large static database where users haveenough time and computational resources for tuning parameters and training quantizers, the previous inverted indexing
systems should be used. On the other hand, if the databasechanges dynamically, the distribution of vectors might varyover time and parameters might need to be updated often. In
such cases, the proposed PQTable would be the best choice.
Ease of use: The inverted indexing systems produce goodresults but are difficult to handle by novices because theyrequire several tuning and training steps. The proposed
PQTable is conceptually simple and much easier to use, because users do not need to decide on any parameters. This
would be useful if users were using an ANN method simply
as a tool for solving problems in some other domain, suchas fast SIFT matching using ANN for 3D reconstruction [6].
Limitations: The PQTable is no longer efficient for ≥128-bit codes with the SIFT1B data (T = 4, N = 109 ),taking 3.4 s per query, which is still ten times faster than for
the ADC, but slower than for the state-of-the-art system [4].
This is caused by the inefficiency of the “checking” process
for longer bit codes. Handling these longer codes is proposed for future work. Note that ≤ 128-bit codes are practical for many applications, such as the use of 80-bit codesfor state-of-the-art image-retrieval systems [19].
Another limitation is the heavy memory usage of
PQTable. Constructing a memory efficient data structurefor Hash tables remains a future work.

6. Conclusion
We propose the PQTable, a nonexhaustive search method
for finding the nearest PQ codes without need of parameter tuning. The PQTable is based on a multiindex hashtable, and includes candidate code generation and merging
of multiple tables. From an empirical analysis, we showedthat the required parameter value T can be estimated in advance. An experimental evaluation using the SIFT1B data
showed that, the PQTable could compute results 102 to 105
times faster than the ADC-scan method. The disadvantageof the PQTable is its heavier memory overhead compared tothe state-of-the-art systems.
Acknowledgements: This work was supported by theStrategic Information and Communications R&D Promotion Programme (SCOPE) and JSPS KAKENHI Grant
Number 257696 and 15K12025.

References[1] A. Babenko and V. Lempitsky. The inverted multi-index. In
Proc. CVPR. IEEE, 2012. 1, 3, 4, 8
[2] A. Babenko and V. Lempitsky. Additive quantization for extreme vector compression. In Proc. CVPR. IEEE, 2014. 1,
2[3] A. Babenko and V. Lempitsky. Improving bilayer productquantization for billion-scale approximate nearest neighbors
in high dimensions. CoRR, abs/1404.1831, 2014. 1, 8
[4] A. Babenko and V. Lempitsky. The inverted multi-index.
IEEE TPAMI, 2014. 1, 8
[5] A. Babenko and V. Lempitsky. Tree quantization for largescale similarity search and classification. In Proc. CVPR.
IEEE, 2015. 1, 2
[6] J. Cheng, C. Leng, J. Wu, H. Cui, and H. Lu. Fast and accurate image matching with cascade hashing for 3d reconstruction. In Proc. CVPR. IEEE, 2014. 8[7] T. Ge, K. He, Q. Ke, and J. Sun. Optimized product quantization. IEEE TPAMI, 36(4):744–755, 2014. 1, 8
[8] Y. Gong, S. Lazebnik, A. Gordo, and F. Perronnin. Iterative quantization: A procrustean approach to learning binary codes for large-scale image retrieval. IEEE TPAMI,
35(12):2916–2929, 2013. 2[9] D. Greene, M. Parnas, and F. Yao. Multi-index hashing for
information retrieval. In Proc. FOCS. IEEE, 1994. 2, 5, 6
[10] K. He, F. Wen, and J. Sun. K-means hashing: an affinitypreserving quantization method for learning binary compact
codes. In Proc. CVPR. IEEE, 2013. 2[11] J.-P. Heo, Z. Lin, and S.-E. Yoon. Distance encoded productquantization. In Proc. CVPR. IEEE, 2014. 1[12] M. Iwamura, T. Sato, and K. Kise. What is the most efficient
way to select nearest neighbor candidates for fast approximate nearest neighbor search? In Proc. ICCV. IEEE, 2013.
1[13] H. Jègou, M. Douze, and C. Schmid. Product quantization
for nearest neighbor search. IEEE TPAMI, 33(1):117–128,
2011. 1, 2, 7, 8
[14] H. Jègou, R. Tavenard, M. Douze, and L. Amsaleg. Searching in one billion vectors: Re-rank with souce coding. In
Proc. ICASSP. IEEE, 2011. 1, 6
[15] Y. Kalantidis and Y. Avrithis. Locally optimized productquantization for approximate nearest neighbor search. In
Proc. CVPR. IEEE, 2014. 1, 8
[16] S. P. Lloyd. Least squares quantization in pcm. IEEE TIT,
28(2):129–137, 1982. 3[17] M. Norouzi and D. J. Fleet. Cartesian k-means. In Proc.
CVPR. IEEE, 2013. 1[18] M. Norouzi, A. Punjani, and D. J. Fleet. Fast exact searchin hamming space with multi-index hashing. IEEE TPAMI,
36(6):1107–1119, 2014. 2, 5, 6, 7
[19] E. Spyromitros-Xioufis, S. Papadopoulos, I. Y. Kompatsiaris,
G. Tsoumakas, and I. Vlahavas. A comprehensive study overvlad and product quantization in large-scale image retrieval.
IEEE TMM, 16(6):1713–1728, 2014. 8[20] J. Wang, H. T. Shen, J. Song, and J. Ji. Hashing for similarity
search: A survey. CoRR, abs/1408.2927, 2014. 2[21] J. Wang, J. Wang, J. Song, X.-S. Xu, H. T. Shen, and S. Li.
Optimized cartesian k-means. IEEE TKDE, 2014. 1[22] Y. Weiss, A. Torralba, and R. Fergus. Spectral hashing. In
Proc. NIPS, 2008. 2[23] Y. Xia, K. He, F. Wen, and J. Sun. Joint inverted indexing.
In Proc. ICCV. IEEE, 2013. 1[24] T. Zhang, C. Du, and J. Wang. Composite quantization for
approximate nearest neighbor search. In Proc. ICML, 2014.
1, 2[25] T. Zhang, G.-J. Qi, J. Tang, and J. Wang. Sparse composite
quantization. In Proc. CVPR. IEEE, 2015. 1, 2