Algorithm Engineering for HighDimensional Similarity Search
Problems
Martin Aumüller
IT University of Copenhagen

Roadmap010203

Similarity Search inHigh-Dimensions:Setup/Experimental
Approach

Survey of state-ofthe-art Nearest
Neighbor Searchalgorithms

Similarity Search on
the GPU, in external
memory, and in
distributed settings
21. Similarity Search in HighDimensions: Setup/Experimental
Approach3

𝑘-Nearest Neighbor Problem• Preprocessing: Build DS for set 𝑆 of 𝑛 data points• Task: Given query point 𝑞, return 𝑘 closest points to 𝑞 in 𝑆✓✓✓✓✓✓
4

Nearest neighbor search on words• GloVe: learning algorithm to find vector representations for words• GloVe.twitter dataset: 1.2M words, vectors trained from 2B tweets,
100 dimensions• Semantically similar words: nearest neighbor search on vectors

https://nlp.stanford.edu/projects/glove/Jeffrey Pennington, Richard Socher, and Christopher D. Manning. 2014. GloVe: Global Vectors for Word Representation.

5

“sicily”• sardinia• tuscany• dubrovnik• liguria• naples“algorithm”

GloVe Examples• algorithms• optimization• approximation• iterative• computation“engineering”$ grep -n "sicily" glove.twitter.27B.100d.txt
118340:sicily -0.43731 -1.1003 0.93183 0.13311 0.17207 …

• engineer• accounting• research• science• development

6Basic Setup• Data is described by high-dimensionalfeature vectors• Exact similarity search is difficult inhigh dimensions• data structures and algorithms suffer• exponential dependence ondimensionality• in time, space, or both7

Why is Exact NN difficult?
• Choose 𝑛 random points from 𝑁 0, 1/𝑑 𝑑 , for large 𝑑• Choose a random query point

2 ± 1/√𝑑• nearest and furthest neighborbasically at same distance8Performanceon GloVe

9Difficulty measure for queries• Given query 𝑞 and distances 𝑟1 , … , 𝑟𝑘 to𝑘 nearest neighbors, define
1
𝐷 𝑞 =−
෍ ln 𝑟𝑖 /𝑟𝑘𝑘−1𝑞

Based on the concept of local intrinsic dimensionality [Houle, 2013] and its MLE estimator [Amsaleg et al., 2015]10

LID Distribution

11

Results (GloVe, 10-NN, 1.2M points)
EasyMiddle
Difficult

http://ann-benchmarks.com/sisap19/faiss-ivf.html

12

2. STATE-OF-THE-ART
NEAREST NEIGHBOR SEARCH

13

General Pipeline
Index generates candidates
Brute-force search oncandidates
14

Brute-force search
GloVe: 1.2 M points, inner product as distance measure

𝑝1𝑝𝑛

400 byte

400 byte• 100ms per scan
• 4.2 GB/s throughput• CPU-boundAutomatically SIMD vectorized with clang –O3: https://godbolt.org/z/TJX68s
15https://gist.github.com/maumueller/720d0f71664bef694bd56b2aeff80b17

Manual vectorization (256 bit registers)…

𝑥Parallel multiply…

𝑦• 25 ms per query• 16 GB/s• 16.5 GB/s singlethread max on mylaptop• Memory-boundParallel add to result register

00000000
Horizontal sum and cast to float
16Brute-force on bit vectors• Another popular distance measure is Hamming distance• Number of positions in which two bit strings differ• Can be nicely packed into 64-bit words• Hamming distance of two words is just bitcount of the XOR• 1.3 ms per query (128 bits)• 6 GB/s throughput

17[Christiani, 2019]

Sketching to avoid distance computations• Distance computations on bitvectors faster than Euclideandistance/inner product• Their number can be reduced bystoring compact sketch
representations𝑞Can distancecomputation beavoided?

SimHash [Charikar, 2002]
1-BitMinHash [König-Li, 2010]
Sketch representation
𝑞1011100101

𝑥0101110101

Easy to analyze:
Sum of Bernoulli trials ofPr(𝑋 = 1) = 𝑓(dist(𝑞, 𝑥))

At least 𝜏 collisions?
Yes
computedist(𝑞, 𝑥)

Noskip𝑥
Set 𝜏 such that with probability at least 1 − 𝜀 we don’t
disregard point that could be among NN.
18

General Pipeline
Index generates candidates
Brute-force search oncandidates19

PUFFINN
PARAMETERLESSAND UNIVERSALLYFAST FINDING OFNEAREST
NEIGHBORS[A., Christiani, Pagh, Vesterli, 2019]https://github.com/puffinn/puffinn
Credit: Richard Bartz

20

How does it work?

Locality-Sensitive Hashing (LSH) [Indyk-Motwani, 1998]ℎ 𝑝 = ℎ1 𝑝 ∘ ℎ2 𝑝 ∘ ℎ3 𝑝 ∈ 0,1 3=A family ℋ of hash functions is localitysensitive, if the collision probability of
two points is decreasing with theirdistance to each other.

21

Solving 𝑘-NN using LSH (with failure prob. 𝛿)
Dataset 𝑆ℎ2ℎ3ℎ4ℎ5ℎ𝐿…
Termination: If 1 − 𝑝 𝑗 ≤ 𝛿, report current top-𝑘.
Not terminated? Decrease 𝐾!

probability of the current 𝑘-th nearest neighbor to collide.
22

The Data Structure
TheoreticalPractical• LSH Forest: Each repetition is a
Trie build from LSH hash values[Bawa et al., 2005]• Store indices of data set points
sorted by hash code• ”Traversing the Trie” by binary
search• use lookup table for first levels

0

1

1000

10

1 01

101…
23

Overall System Design24

Running time (Glove 100d, 1.2M, 10-NN)

25

3𝑑A difficult (?) data set in ℝ
𝑛 data points

𝑚 query points

𝑥1 = 0𝑑 , 𝑦1 , 𝑧1
𝑞1 = 𝑣, 0𝑑 , 𝑟1⋮⋮
𝑞𝑚 = (𝑣, 0𝑑 , 𝑟𝑚 )𝑥𝑛−1 = 0𝑑 , 𝑦𝑛−1 , 𝑧𝑛−1
𝑥𝑛 = (𝑣, 𝑤, 0𝑑 )𝑦𝑖 , 𝑧𝑖 , 𝑣, 𝑤, 𝑟𝑖 ∼ 𝒩 𝑑 0,12𝑑
26

Running time (“Difficult”, 1M, 10-NN)

27

Graph-based Similarity Search

28

Building a Small World Graph29

Refining a Small World Graph
Goal: Keep out-degree as small as possible (while maintaining “large-enough” in-degree)!

HNSW/ONNG: [Malkov et al., 2020], [Iwasaki et al., 2018]
30

Running time (Glove 100d, 1.2M, 10-NN)

31

Open Problems Nearest Neighbor Search• Data-dependent LSH with guarantees?
• Theoretical sound Small-World Graphs?
• Multi-core implementations• Good? [Malkov et al., 2020]• Alternative ways of sketching data?

32

3. Similarity Search on theGPU, in External Memory,and in Distributed Settings
33

Nearest Neighbors on the GPU: FAISS[Johnson et al., 2017] https://github.com/facebookresearch/faiss• GPU setting• Data structure is held in GPU memory• Queries come in batches of say 10,000 queries per time

• Results:• http://ann-benchmarks.com/sift-128-euclidean_10_euclidean-batch.html

34

FAISS/2• Data structure• Run k-means with large number ofcentroids• Each data point is associated withclosest centroid• Query• Find 𝐿 closest centroids• Return 𝑘 closest points found inpoints associated with thesecentroids
https://scikit-learn.org/stable/auto_examples/cluster/plot_kmeans_digits.html

35

Nearest Neighbors on the GPU: GGNN
[Groh et al., 2019]36

Nearest Neighbors in External Memory[Subramanya et al., 2019]

RAMSSD𝑥ෞ1…
𝑥ෞ𝑛compressed vectors(32 byte per vector)

Product Quantization

𝑥1…

𝑥𝑛

Original vectors(~400 byte per vector)
37

Distributed Setting: Similarity Join
• Problem• given sets 𝑅 and 𝑆 of size 𝑛,• and similarity threshold 𝜆, compute𝑅 ⋈𝜆 𝑆 = { 𝑥, 𝑦 ∈ 𝑅 × 𝑆 ∣ 𝑠𝑖𝑚 𝑥, 𝑦 ≥ 𝜆}𝑅

• Similarity measures• Jaccard similarity• Cosine similarity

𝑆• Naive: 𝑂 𝑛2 distance computations
38

Scalability! But at what COST? [McSherry et al., 2015]

Map-Reduce-based Similarity Join
Single Core on Xeon E5-2630v2 (2.60 GHz)

[Mann et al., 2016]

Hadoop cluster (12 nodes, 24 HT per node)[Fier et al., 2018]

39

Solved almost-optimally in the MPC model[Hu et al., 2019]

𝑅Hashusing
LSH

Join onhash(𝑥, ℎ𝑖 (x))(𝑥, 𝑦, ℎ𝑖 (x))

Similarity
at leastEmit𝜆?
(𝑥, 𝑦)(𝑦, ℎ𝑖 (y))
𝑆𝑂(𝑛2 ) local work for distance computations!
40

Another approach: DANNY[A., Ceccarello, Pagh, 2020] In preparation, https://github.com/cecca/danny𝑅

Cartesian Product

LSH + Sketching,candidate verification
locallyEmit/Collect𝑆

Implementation in Rust using timely dataflow

https://github.com/TimelyDataflow/timely-dataflow
41

Results

42

Roadmap010203

Similarity Search inHigh-Dimensions:Setup/Experimental
Approach

Survey of state-ofthe-art Nearest
Neighbor Searchalgorithms

Similarity Search on
the GPU, in external
memory, and in
distributed settings
43References•[Amsaleg, Chelly, Furon, Girard, Houle, Kawarabayashi, Nett, 2015]: Estimating local intrinsic dimensionality. KDD 2015.

•[A., Bernhardsson, Faithfull, 2020]: ANN-Benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Inf. Syst. 87 (2020), see
https://arxiv.org/abs/1807.05614 for an open access version.

•[A., Ceccarello, 2019]: The role of local intrinsic dimensionality in benchmarking nearest neighbor search. In: SISAP 2019, see http://ann-benchmarks.com/sisap19/.

•[A., Christiani, Pagh, Vesterli, 2019]: PUFFINN: parameterless and universally fast finding of nearest neighbors. In: ESA 2019, see https://github.com/puffinn/puffinn•[Christiani, 2019]: Fast locality-sensitive hashing frameworks for approximate near neighbor search•[Fier, Augsten, Bouros, Leser, Freytag, 2018]: Set similarity joins on MapReduce: An experimental survey. VLDB 2018.

•[Groh, Ruppert, Wieschollek, Lensch, 2019]: GGNN: Graph-based GPU nearest neighbor search https://arxiv.org/abs/1912.01059•[Houle, 2013]: Dimensionality, discriminability, density and distance distributions. ICDMW 2013.

•[Hu, Yi, Tao, 2019]: Output-optimal massively parallel algorithms for similarity joins. ACM Transactions on Database Systems, 2019.

•[Iwasaki, Miyazaki, 2018]: Optimization of Indexing Based on k-Nearest Neighbor Graph for Proximity Search in High-dimensional Data, https://arxiv.org/abs/1810.07355•[Indyk, Motwani, 1998]: Approximate Nearest Neighbors: Towards removing the curse of dimensionality, STOC 1998.

•[Johnson, Douze, Jegou, 2017]: Billion-scale similarity search with GPUs, https://arxiv.org/abs/1702.08734.

•[Malkov, Yashunin, 2020]: Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE TPAM 2020.

•[Mann, Augsten, Bouros, 2016]: An empirical evaluation of set similarity join techniques. VLDB 2016.

•[McSherry, Isard, Murray, 2015], Scalability! But at what COST? USENIX HotOS 2015.

•[Subramanya, Devvrit, Kadekodi, Krishnaswamy, Simhadri, 2019]: DiskANN: Fast accurate billion-point nearest neighbor search on a single node. NeurIPS 201944

Extra slides

45

PUFFINN: Fast Hash Function Evaluation• Main Bottleneck: Computation of Hash Values• Adapt the “pooling” technique of [Dahlgaard et al., 2017]and [Christiani, 2019]
𝐾𝐾 ⋅ 𝑚 independent hash functions from LSH family, 𝑚 ≪ 𝐿.

Pick 𝐾 hash functions in repetition 𝑗 using universal hashfunctions in each column.
𝑚Analysis using Cantelli’s inequality →Requires different stopping criteria (factor 2 slowdown)

46