Martin Aumüller
Tobias Christiani
Rasmus PaghMichael Vesterli

Credit: Richard Bartz

PUFFINN

Parameterless and Universally Fast FIndingof Nearest Neighbors

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

𝑞

✓

✓

Probabilistic variant: Each nearest neighbor isreported with probability at least 1 − 𝛿.
✓✓✓𝑞2

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.

3

GloVe Examples (100d, 1.2M vectors)“munich”• “bayern”• “cologne”• “stuttgart”• “berlin”• “hamburg”“germany”• “austria”• “switzerland”• “german”• “europe”• “poland”“algorithm”• “algorithms”• “optimization”• “approximation”• “iterative”• “computation”

4Our Results
TheoryPractice• A novel Locality-SensitiveHashing (LSH)-based algorithm
for probabilistic 𝑘-NN
• Avoids standard reduction
approach by[Har-Peled et al., 2012]• Theory + algorithm engineering
gives a fast implementation with
provable guarantees• in our experiments:• competitive with other state-of-theart approaches (w/o guarantees)• faster than state-of-the-art LSH(w/o guarantees)[FALCONN]
5

How does it work?

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

6

Standard LSH for Reporting Points at Distance ≤ 𝑟Dataset 𝑆;ℎ0=ℎ′ 0,0∘⋯′;∘ℎℎ2,0

∈𝑅

𝑞
ℎ3ℎ>

ℎ=ℎ?

…
𝑞𝑞

𝑞

𝑞

𝑞

𝑘-NN?
𝑞Query Algorithm: Collect all points that collide with 𝑞 under ℎ0 , … , ℎ? . Return all points at distance ≤ 𝑟.
7

Our Approach: Solving 𝑘-NN using LSH• Check buckets 𝑗 ∈ {1, … , 𝐿},
one-by-one• keep track of current 𝑘closest points• Goal:Report with prob. ≥ 1 − 𝛿;=ℎ0
Xℎ′ 0 ,0∘⋯X′;∘ℎℎ2,0ℎ3X

𝑆

∈𝑅X

ℎ=ℎ>

XXℎ?

…

X

Termination: If 1 − 𝑝 G ≤ 𝛿, report current top-𝑘.

• What if there is no such 𝑗?
• Try again with smaller 𝐾

probability of the current 𝑘-th nearest neighbor to collide.
Why does that work? Monotonicity of the LSH collision prob.
8

The Data Structure
Theoretical

Practical• LSH Forest: Each repetition is aTrie build from LSH hash values[Bawa et al., 2005]• Store indices of data set points
sorted by hash code• ”Traversing the Trie” by binarysearch• use lookup table for first levels

011000101 01101…
9

Works with any
kind of LSH

PUFFINN

Parameterless and Universally Fast FIndingof Nearest Neighbors“space parameter” +“quality parameter”
no internal parameters

Implicit Tries +Recycling LSH [Christiani, 2019]
values + ???
10

Sketching to avoid distance computations• Have to carry out (expensive)
distance computations oncandidates• Can be reduced by storing
compact sketch representations

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(𝑞, 𝑥)

No
skip

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

Overall System Design12

Experimental Evaluation• Design choices in the implementation• Which LSH family to use? Cross-Polytope LSH [Andoni et al., 2015]• Which evaluation strategy to use? Pooling• Use sketches? Yes• Influence of parameters? More space helps, but saturates quickly• Comparison to other existing 𝑘-NN implementations

13

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

14

3%

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

𝑚 query points

𝑥0 = 0% , 𝑦0 , 𝑧0
𝑞0 = 𝑣, 0% , 𝑟0⋮⋮𝑞b = (𝑣, 0% , 𝑟b )%𝑥XY0 = 0 , 𝑦XY0 , 𝑧XY0𝑥X = (𝑣, 𝑤, 0% )𝑦\ , 𝑧\ , 𝑣, 𝑤, 𝑟\ ∼ 𝒩%10,2𝑑15

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

16

Credit: Richard Bartz

Summary• Using LSH to solve exact 𝑘-NN
(with probabilistic guarantees)• Adaptive query algorithm• Engineering tricks to make it fast
(more in the paper!)• Can ideas be applied to othersettings?
• Similarity Joins

https://github.com/puffinn/puffinn
https://github.com/puffinn/esa-paper
17

A Bound on the Expected Running Time• knows for each query 𝒒
best stopping point in data structure• Lemma: In expectation, proposed algorithm takes time𝑂(𝑂𝑃𝑇 𝐿, 𝐾, 𝑘, 𝛿/𝑘 + 𝐿 𝐾 + 𝑘 )18

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)

19Our Approach: Solving 𝑘-NN using LSH;
• Check buckets 𝑗 ∈ {1, … , 𝐿}, one𝑅∈by-one0,′;∘ ℎX• keep track of closest 𝑘 points found ∘ ⋯0so farℎ′ 0 ,=𝟏 − 𝒑∗ 𝒋 ≤ 𝜹,Want:(𝒑∗ collision prob. of true 𝒌-NN)
Montonocity of LSH: 𝒑∗ ≥ 𝒑.

• What if there is no such 𝑗?
• Try again with smaller 𝐾

ℎ0

ℎ2

ℎ3

𝑆

ℎ=ℎ>

ℎ?

…
Termination: If 1 − 𝑝 G ≤ 𝛿, report top-𝑘.
probability of the current 𝑘-th nearest neighbor to collide.
Why does that work? Monotonicity of the LSH collision prob.
20

Influence of Index Size (Glove 100d, 1.2M, 10-NN)

21