slides: https://bit.ly/2P0KuW1

Reconfigurable Inverted Index
Yusuke Matsui1 Ryota Hinami2 Shin’ichi Satoh1
1National Institute of Informatics

2The University of Tokyo

Approximate nearest neighbor search
0.23
3.15
0.65
1.43𝒒 ∈ ℝ𝐷Query

ANN systemhash-table, trees,
inverted-index, etc

Add

Database vectors
5.22
0.54
1.66
0.74

4.63
6.21
0.72
0.31

𝒙1 𝒙2…

0.86
3.44
1.12
0.04𝒙𝑁slides: https://bit.ly/2P0KuW1

Approximate NN search

Resultargmin 𝒒 − 𝒙𝑛 22

0.20
3.25
0.72
1.68𝑛∈ 1,…,𝑁𝒙74

Approximate nearest neighbor search
0.23
3.15
0.65
1.43

𝒒 ∈ ℝ𝐷Query

ANN systemhash-table, trees,
inverted-index, etc

Add

Database vectors
5.22
0.54
1.66
0.74

4.63
6.21
0.72
0.31

𝒙1 𝒙2…

0.86
3.44
1.12
0.04

𝒙𝑁

slides: https://bit.ly/2P0KuW1

Approximate NN search

Resultargmin 𝒒 − 𝒙𝑛 22

0.20
3.25
0.72
1.68

𝑛∈ 1,…,𝑁𝒙74

Approximate nearest neighbor search
0.23
3.15
0.65
1.43

𝒒 ∈ ℝ𝐷Query

ANN systemhash-table, trees,
inverted-index, etc

Add

Database vectors
5.22
0.54
1.66
0.744.63
6.21
0.72
0.31

𝒙1 𝒙2…

0.86
3.44
1.12
0.04𝒙𝑁slides: https://bit.ly/2P0KuW1

Approximate NN search

Resultargmin 𝒒 − 𝒙𝑛 22

0.20
3.25
0.72
1.68

𝑛∈ 1,…,𝑁𝒙74

Related work

slides: https://bit.ly/2P0KuW1➢ Locality-sensitive-hashing (LSH)- FALCONN [Andoni+, 15] [Razenshteyn+, 18]➢ Project/tree-based- FLANN [Muja+, 14]- Annoy [Bernhardsson, 18]➢ Graph traversal- NSW/HNSW on NMSLIB [Malkov+, 16][Boytsov+, 13]➢ Product quantization (PQ)
- IVFPQ on Faiss [Jégou+, 11][Johnson+, 17] etc.
- Our Reconfigurable Inverted Index

slides: https://bit.ly/2P0KuW1
0.23
3.15
0.65
1.43

QueryApproximate NN Search

Resultargmin 𝒒 − 𝒙𝑛 22

0.20
3.25
0.72
1.68

ANN system𝑛∈𝒮𝒒 ∈ ℝ𝐷

Subset search problem➢ Existing ANN systems are fast for the all vectors- Search is over 𝒮 = 1, … , 𝑁➢ However, it is hard to run the search for a subset- Search is over 𝒮 ⊆ 1, … , 𝑁- e.g., searching from 𝒙1000 , … , 𝒙2000- Why? Systems are usually optimized for 𝒮 = 1, … , 𝑁

𝒙74

There is a demand for subset search!

slides: https://bit.ly/2P0KuW1

There is a demand for subset search!

slides: https://bit.ly/2P0KuW1

Propose: Reconfigurable inverted index (Rii)✓ Subset search✓ A comparative performance with IVFPQ (Faiss)✓ 10 ms for billion-scale dataslides: https://bit.ly/2P0KuW1

Reconfigurable inverted index (Rii)
RuntimeFast if |𝒮|is small
𝒮Runtime

Fast if |𝒮|is large
𝒮Cherry pick!
Always fastRuntime➢Preliminary- PQ linear scan- IVFPQ➢Data structure➢Search𝒮

slides: https://bit.ly/2P0KuW1

Reconfigurable inverted index (Rii)
RuntimeFast if |𝒮|is small
𝒮Runtime

Fast if |𝒮|is large
𝒮Cherry pick!
Always fastRuntime➢Preliminary- PQ linear scan
- IVFPQ➢Data structure➢Search𝒮

slides: https://bit.ly/2P0KuW1

Preliminary: Product quantization (PQ) [Jégou+, TPAMI 11]
PQ: Compress a vector
into a short code

All database vectors are PQ-encoded beforehand

𝒙1 𝒙2,,…

PQ

ℝ →2

4.63
6.21
0.72
0.31
PQ45.220.54
1.66
0.74
PQ

5.22
0.54
1.66
0.74

𝒙𝑁

12N…

…

0.86
3.44
1.120.04

slides: https://bit.ly/2P0KuW1

Preliminary: Product quantization (PQ) [Jégou+, TPAMI 11]➢The subset search is possible with a linear cost of 𝒮𝑛argmin 𝑑 𝒒,e.g., 𝒮 = 2, 4, 5, 8𝑛∈𝒮

✔
1

0.23
3.15
0.65
1.43

23✔

✔

456N

…

Linearly compared➢The search is efficient
only if 𝒮 is small

Runtime𝒒 ∈ ℝ𝐷𝒮𝑁

slides: https://bit.ly/2P0KuW1

Reconfigurable inverted index (Rii)
RuntimeFast if |𝒮|is small𝒮

RuntimeFast if |𝒮|is large
𝒮Cherry pick!
Always fastRuntime➢Preliminary- PQ linear scan
- IVFPQ➢Data structure➢Search➢Evaluation𝒮slides: https://bit.ly/2P0KuW1

Preliminary: Inverted Index + PQ (IVFPQ) [Jégou+, TPAMI 11]➢Current basic data structure for a large-scale search➢Subset-search is possible only if 𝒮 is large
126

225

1392

𝒄1
𝒄13

𝒄2

𝒄5

…

Space partitioning188

slides: https://bit.ly/2P0KuW1

Preliminary: Inverted Index + PQ (IVFPQ) [Jégou+, TPAMI 11]➢Current basic data structure for a large-scale search➢Subset-search is possible only if 𝒮 is large e.g., 𝒮 = 13, 92, 105, …
126

0.23
3.15
0.65
1.43𝒒 ∈ ℝ𝐷225𝑛 ∈ 𝒮 or not𝒄1
𝒄13𝒄2

✔

✔
1392

𝒄5

…

Space partitioning

188

Re-rank via
PQ-linear scan

1.Find the closest space: 𝑘 ∗ = argmin𝑘 𝒒 − 𝒄𝑘 22
2.Focus the 𝑘 ∗ th space, accept items ∈ 𝒮
3.Re-rank the items via PQ-linear scan

92

slides: https://bit.ly/2P0KuW1

Preliminary: Inverted Index + PQ (IVFPQ) [Jégou+, TPAMI 11]➢Current basic data structure for a large-scale search➢Subset-search is possible only if 𝒮 is large e.g., 𝒮 = 13, 92, 105, …
126

0.23
3.15
0.65
1.43

𝑛 ∈ 𝒮 or not

𝒄1
𝒄13

𝒄2

✔

✔
1392

𝒄5…

Space
partitioning
Why
is it slow for small 𝒮 ?

188

Re-rank via
PQ-linear scan

92

Runtime𝒒 ∈ ℝ𝐷225∗ they are far away from 2
if 𝒮 space:is small 𝑘and1.Find thee.g.,closest= argmin𝑘 𝒒 − 𝒄𝑘 2
the𝑘query,
we might
needitemsto scan∗
2.Focus theth space,accept∈ all𝒮 items
3.Re-rank the items via PQ-linear scan𝒮𝑁slides: https://bit.ly/2P0KuW1

Reconfigurable inverted index (Rii)
RuntimeFast if |𝒮|is small𝒮

RuntimeFast if |𝒮|is large
𝒮

Cherry pick!
Always fast

Runtime➢Preliminary- PQ linear scan
- IVFPQ➢Data structure➢Search𝒮

slides: https://bit.ly/2P0KuW1

Data structure➢Store (1) PQ-codes linearly, and (2) IDs as an inverted index➢Can run either PQ-linear-scan or IVFPQ with a single data structure
1213…

N…

Key: store codes linearly

cf. IVFPQ126 225

𝒄1𝒄292 188

…

𝒄513

➢ PQ-codes are also chunked. Natural➢ Slight, but critical change 126
225
𝒄1𝒄2

𝒄51392188

slides: https://bit.ly/2P0KuW1

Reconfigurable inverted index (Rii)
RuntimeFast if |𝒮|is small𝒮

RuntimeFast if |𝒮|is large
𝒮

Cherry pick!
Always fast

Runtime➢Preliminary- PQ linear scan
- IVFPQ➢Data structure➢Search𝒮

slides: https://bit.ly/2P0KuW1Search

2

13…
0.23
3.150.65
1.43𝒒 ∈ ℝ𝐷…

𝒮𝑁

𝒮

𝑁

126 225𝒄1
𝒄21392 188…

𝒄5N

Runtime

1Runtime➢If 𝒮 is small, run PQ-linear scan
➢If 𝒮 is large, run IVFPQ

slides: https://bit.ly/2P0KuW1

Search

213…
0.23
3.15
0.65
1.43𝒒 ∈ ℝ𝐷…

𝒮𝑁

𝒮

𝑁

126 225𝒄1
𝒄21392 188…

𝒄5N

Runtime

1Runtime➢If 𝒮 is small, run PQ-linear scan
➢If 𝒮 is large, run IVFPQ

slides: https://bit.ly/2P0KuW1

Search

213…
0.23
3.15
0.65
1.43𝒒 ∈ ℝ𝐷…

𝒮𝑁𝒮𝑁126 225

𝒄1

fetch
𝒄2

1392 188…

𝒄5N

Runtime

1Runtime➢If 𝒮 is small, run PQ-linear scan
➢If 𝒮 is large, run IVFPQ

slides: https://bit.ly/2P0KuW1

Search

213…
0.23
3.15
0.65
1.43𝒒 ∈ ℝ𝐷…

𝒮𝑁𝒮

𝑁

126 225

𝒄1

fetch
𝒄2

1392 188…

𝒄5N

Runtime

1Runtime➢If 𝒮 is small, run PQ-linear scan
➢If 𝒮 is large, run IVFPQ

slides: https://bit.ly/2P0KuW1

Search➢Set a threshold 𝜃➢Key: Switch two methods
based on 𝒮 ≶ 𝜃➢If 𝒮 is small, run PQ-linear scan
➢If 𝒮 is large, run IVFPQ
213…
0.23
3.15
0.65
1.43

𝒒 ∈ ℝ𝐷…
126 225

𝒄1fetch𝒄2

1392 188…

𝒄5N

Runtime1𝑁𝜃

𝒮
Use PQ-linear-scan

Use IVFPQ

slides: https://bit.ly/2P0KuW1

Search➢Set a threshold 𝜃➢Key: Switch two methods
based on 𝒮 ≶ 𝜃➢If 𝒮 is small, run PQ-linear scan
➢If 𝒮 is large, run IVFPQ
213…
0.23
3.15
0.65
1.43

𝒒 ∈ ℝ𝐷…
126 225

𝒄1fetch𝒄2

1392 188…

𝒄5N

Runtime1𝑁𝜃

𝒮
Use PQ-linear-scanUse IVFPQEvaluation

slides: https://bit.ly/2P0KuW1➢SIFT1M (𝑁 = 106 , 𝐷 = 128). Results for top-R searchEvaluation

slides: https://bit.ly/2P0KuW1➢ Existing system: Annoy➢ Force to search a subset➢SIFT1M (𝑁 = 106 , 𝐷 = 128). Results for top-R search
The existing system is slow,
especially when 𝒮 is small

Proposed Rii is always fast
regardless of 𝒮 and 𝑅

slides: https://bit.ly/2P0KuW1$ pip install rii

https://github.com/matsui528/rii

import rii
import nanopq# Prepare a PQ/OPQ codec with M=32 sub spaces
codec = nanopq.PQ(M=32).fit(vecs=Xt) # Trained using Xt# Instantiate a Rii class with the codec
e = rii.Rii(fine_quantizer=codec)# Add vectors
e.add_configure(vecs=X)# Searchids, dists = e.query(q=q, topk=3, target_ids=S)
print(ids, dists) # e.g., [7484 8173 1556] [15.062 15.385 16.169]

slides: https://bit.ly/2P0KuW1

Summary
0.23
3.15
0.65
1.43

Approximate NN Search

QueryANN system

Reconfigurable inverted index:➢Store PQ-codes linearly➢Switch method based on 𝒮argmin 𝒒 − 𝒙𝑛 22𝑛∈𝒮

Result➢PyPI:$ pip install rii

Runtime➢One thing I couldn’t mention:
Reconfiguration: the system remains fasteven after many new items are added𝑁𝜃𝒮
Use PQ-linear-scan

Use IVFPQ➢See our paper, or come to our poster:✓ Poster session 5 (15:30 – 16:30)

slides: https://bit.ly/2P0KuW1

Example: Image search
0.23
3.15
0.65
1.43

Query

ANN system𝒒 ∈ ℝ𝐷

Approximate NN search

Resultargmin 𝒒 − 𝒙𝑛 22

0.20
3.25
0.72
1.68𝑛∈ 1,…,𝑁𝒙74

Extract aVGG feature

Queryimage

74th image
𝑁 database images

slides: https://bit.ly/2P0KuW1

Example of subset search for image
0.23
3.15
0.65
1.43

Query

ANN system

Approximate NN search

Resultargmin 𝒒 − 𝒙𝑛 22

0.20
3.25
0.72
1.68

𝑛∈𝒮𝒒 ∈ ℝ𝐷𝒙92
Filtering by shooting-date:- Taken in 2018
- 𝒮 = 34, 56, 92, … , 663

Extract a
VGG feature

Queryimage

92nd image
𝑁 database images

Evaluation

slides: https://bit.ly/2P0KuW1➢Extensive comparison against existing methods➢For a fixed accuracy (Recall@1), check runtime and its disk space

Evaluation

slides: https://bit.ly/2P0KuW1➢Extensive comparison against existing methods➢For a fixed accuracy (Recall@1), check runtime and its disk spaceNMSLIB is extremely fast, but consume
relatively large disk space (∼memory)

Evaluation

slides: https://bit.ly/2P0KuW1➢Extensive comparison against existing methods➢For a fixed accuracy (Recall@1), check runtime and its disk spaceNMSLIB is extremely fast, but consume
relatively large disk space (∼memory)
Proposed Rii achieved a comparative
performance with Faiss