Distance-Sensitive Hashing
Martin Aumüller, Tobias Christiani, Rasmus Pagh, Francesco Silvestri
IT University of Copenhagen & University of Padova

June 11, 2018
PODS 18
Supported byM. Aumüller

Distance-Sensitive Hashing

1/22

Motivation: Recommender Systems

Data: Collection of newspaper
articles S
Query: User read article x,
recommend “interesting” otherarticles from S
What is interesting?
II

M. Aumüller

not too close to x
not too far away from x

Distance-Sensitive Hashing

2/22

General setting: Approximate Similarity Search Problems

M. Aumüller

Distance-Sensitive Hashing3/22

General setting: Approximate Similarity Search Problems

d-dimensional metric space (X , || · ||)M. Aumüller

Distance-Sensitive Hashing

3/22

(c, r)-approximate Annulus Problem

M. Aumüller

Distance-Sensitive Hashing

4/22

(c, r)-approximate Annulus Problem

F

M. Aumüller

Distance-Sensitive Hashing

4/22

(c, r)-approximate Annulus Problemr
F

M. Aumüller

Distance-Sensitive Hashing

4/22

(c, r)-approximate Annulus Problem

r
r/c
F

M. Aumüller

Distance-Sensitive Hashing

4/22

(c, r)-approximate Annulus Problem

rr/cF

M. Aumüller

Distance-Sensitive Hashing

cr

4/22

(c, r)-approximate Annulus Problem

XXXX

M. Aumüller

Xrr/cX X

FDistance-Sensitive Hashing

cr

4/22

•
•
•

•

•

•

•
•

•
•

•

•
•

F

•
•
•

•

•
•

•

M. Aumüller•

Distance-Sensitive Hashing

••

•

•

5/22

••
•

•

•

•

•
•

•
•

•

•
•

F
Randomly choose pair (h, g) of hash functions••

•

•

•
•

•

M. Aumüller•

Distance-Sensitive Hashing••

•

•

5/22

h(•)
h(•)
h(•) h(•)h(•)h(•)h(•)g(F)
h(•)

h(•)

h(•)

h(•)
h(•)h(•)
Randomly choose pair (h, g) of hash functions

h(•)
h(•)
h(•)

h(•)

h(•)
h(•)

h(•)

M. Aumüllerh(•)

Distance-Sensitive Hashingh(•)h(•) h(•) h(•)

5/22

h(•)
h(•)
h(•) h(•)h(•)h(•)h(•)g(F)
h(•)

h(•)

h(•)

h(•)
h(•)h(•)

h(•)
h(•)
h(•)

h(•)

h(•)
h(•)

h(•)

M. Aumüllerh(•)

Distance-Sensitive Hashingh(•)h(•) h(•) h(•)

5/22h(•)h(•)h(•) h(•)h(•)h(•)h(•)g(F)
h(•)

h(•)

h(•)

h(•)
h(•)h(•)

h(•) P(h,g) (h(•) = g(F))?
h(•)
h(•)
h(•)

h(•)
h(•)

h(•)

M. Aumüllerh(•)

Distance-Sensitive Hashingh(•)h(•) h(•) h(•)

5/22

Bitsampling for {0, 1}d (IM98)
space: {0, 1}d – length-d bitstrings
dist(x, y) = (#positions where x and y differ)/d(relative Hamming distance)
Bitsampling: Project to random subset of dimensions.
x00101001010

y10101100010

h(x)011g(y)011

M. Aumüller

Distance-Sensitive Hashing

6/22

Collision Probability

Bit sampling collision probablity
1

k=1
k=3

0.5

00

0.2

0.4
0.6
0.8
Relative Hamming distance1

If dist(x, y) = r/d and we sample k positions, thenP(h(x) = g(y)) = (1 − r/d)k .

M. Aumüller

Distance-Sensitive Hashing

7/22

Collision Probability

Bit sampling collision probablity
1r

k=1
k=3

0.5

00

0.2

0.4
0.6
0.8
Relative Hamming distance1

If dist(x, y) = r/d and we sample k positions, thenP(h(x) = g(y)) = (1 − r/d)k .

M. Aumüller

Distance-Sensitive Hashing

7/22

Collision Probability

Bit sampling collision probablity
1crr

k=1
k=3

0.5

00

0.2

0.4
0.6
0.8
Relative Hamming distance

1If dist(x, y) = r/d and we sample k positions, thenP(h(x) = g(y)) = (1 − r/d)k .

M. Aumüller

Distance-Sensitive Hashing

7/22

Collision Probability

Bit sampling collision probablity
1crr

k=1
k=3

0.5

00

0.2

0.4
0.6
0.8Relative Hamming distance1

If dist(x, y) = r/d and we sample k positions, thenP(h(x) = g(y)) = (1 − r/d)k .

M. Aumüller

Distance-Sensitive Hashing

7/22

c·rr
XXXX

M. Aumüller

Distance-Sensitive Hashing

8/22

“Anti Bitsampling” for {0, 1}dAnti Bitsampling: Project to random subset of dimensions, flip all queryhash code bits.
x00101001010

y10101100010

h(x)

011

g(y)

100

M. Aumüller

Distance-Sensitive Hashing

9/22

Collision Probability

Anti Bitsampling collision probablity
1k=1k=30.5

000.2

0.4
0.6
0.8
Relative Hamming distance1

If dist(x, y) = r/d and we sample k positions, thenP(h(x) = g(y)) = (r/d)k .

M. Aumüller

Distance-Sensitive Hashing

10/22

Collision Probability

Anti Bitsampling collision probablity
1

r/c

k=1
k=3

0.5

00

0.2

0.4
0.6
0.8
Relative Hamming distance1

If dist(x, y) = r/d and we sample k positions, thenP(h(x) = g(y)) = (r/d)k .

M. Aumüller

Distance-Sensitive Hashing

10/22

Collision ProbabilityAnti Bitsampling collision probablity
1r/cr

k=1
k=30.5

000.2

0.4
0.6
0.8
Relative Hamming distance1

If dist(x, y) = r/d and we sample k positions, thenP(h(x) = g(y)) = (r/d)k .

M. Aumüller

Distance-Sensitive Hashing

10/22

Collision Probability

Anti Bitsampling collision probablity
1r/cr

k=1
k=3

0.5

00

0.2

0.4
0.6
0.8
Relative Hamming distance1

If dist(x, y) = r/d and we sample k positions, thenP(h(x) = g(y)) = (r/d)k .

M. Aumüller

Distance-Sensitive Hashing

10/22

X
X

X

X

r

X

X

r/cX

X
X

X
X
X
X

M. Aumüller

Distance-Sensitive Hashing

X

X
X

X
X
X

X

X

11/22

X
X

X

r

X
r/c

X

crX

M. Aumüller

Distance-Sensitive Hashing

12/22

Bitsampling + Anti Bitsampling for {0, 1}d

Bit + Anti Bitsampling: Project to random subset of dimensions, flip
some query hash code bits. (Ex: last two flipped)x00101001010

y10101100010

h(x)

011

g(y)

000

M. Aumüller

Distance-Sensitive Hashing

13/22

Collision Probability

Bit + Anti Bitsampling collision probablity
3 Bits (flip last two)
0.2

0.1

00

0.2

0.4
0.6
0.8
Relative Hamming distance

1If dist(x, y) = r/d, we sample k positions and flip the last `, thenP(h(x) = g(y)) = (1 − r/d)k−` (r/d)` .

M. Aumüller

Distance-Sensitive Hashing

14/22

Collision Probability

Bit + Anti Bitsampling collision probablity
3 Bits (flip last two)

r/c

0.2

0.1

00

0.2

0.4
0.6
0.8
Relative Hamming distance

1If dist(x, y) = r/d, we sample k positions and flip the last `, thenP(h(x) = g(y)) = (1 − r/d)k−` (r/d)` .

M. Aumüller

Distance-Sensitive Hashing

14/22

Collision Probability

Bit + Anti Bitsampling collision probablity
r

r/c

0.2

3 Bits (flip last two)

0.1

00

0.2

0.4
0.6
0.8
Relative Hamming distance

1If dist(x, y) = r/d, we sample k positions and flip the last `, thenP(h(x) = g(y)) = (1 − r/d)k−` (r/d)` .

M. Aumüller

Distance-Sensitive Hashing

14/22

Collision Probability

Bit + Anti Bitsampling collision probablity
3 Bits (flip last two)rr/c0.2

cr

0.1

00

0.2

0.4
0.6
0.8
Relative Hamming distance1

If dist(x, y) = r/d, we sample k positions and flip the last `, thenP(h(x) = g(y)) = (1 − r/d)k−` (r/d)` .

M. Aumüller

Distance-Sensitive Hashing

14/22

Collision Probability

Bit + Anti Bitsampling collision probablity
3 Bits (flip last two)

r

r/c

0.2

cr

0.1

00

0.2

0.4
0.6
0.8
Relative Hamming distance1

If dist(x, y) = r/d, we sample k positions and flip the last `, thenP(h(x) = g(y)) = (1 − r/d)k−` (r/d)` .

M. Aumüller

Distance-Sensitive Hashing

14/22

Distance-sensitive Hashing
Assume space X with distance measure dist : X × X → R.

Definition
A distribution D over pairs of functions h, g : X → R is called
distance-sensitive with collision probability function (CPF) f : R → [0, 1] if
for each pair x, y ∈ XP(h,g)∼D [h(x) = g(y)] = f (dist(x, y)).

LSH: f is monotonically decreasing
Anti-LSH: f is monotonically increasing
Annulus-LSH: f is unimodal and peaks in [r/c, cr].

M. Aumüller

Distance-Sensitive Hashing

15/22

Performance for Annulus Querieslog(f (r))ρ− = log(f(r/c))log(f (r))ρ+ = log(f (cr))

Space: O(n1+ρ− +ρ+ )Query time: O(nρ− +ρ+ )Collision Probability

Bit + Anti Bitsampling collision probablity

cr

0.1

0

M. Aumüller

3 Bits (flip last two)

rr/c

0.2

00.2

0.4
0.6
0.8
Relative Hamming distance

Distance-Sensitive Hashing

116/22Performance of Annulus Queries
Anti Bitsampling

Bitsampling“optimal” as LSH for{0, 1}d under Hamming
distance
ρ+ = O(1/c)ρ− = O(1/ log c)
Bad at distinguishing“close” and “very close”
points.

Query time: nO(1/ log c) , worse than LSH for near-neighbor queries.

Can we do better?

M. Aumüller

Distance-Sensitive Hashing

17/22

Performance of Annulus Queries
Anti Bitsampling

Bitsampling“optimal” as LSH for{0, 1}d under Hamming
distance
ρ+ = O(1/c)ρ− = O(1/ log c)
Bad at distinguishing“close” and “very close”
points.

Query time: nO(1/ log c) , worse than LSH for near-neighbor queries.

Can we do better?
10011010 7→ √ (−1, −1, +1, +1, −1, +1, −1)
dM. Aumüller

Distance-Sensitive Hashing

17/22

Filter construction (Unit sphere)(Becker et al. 2016, Christiani 2017, Andoni et al. 2017)

Fix t > 0. Sample a ∼ N d (0, 1), andStore Ua,t = {x ∈ S | ha, xi ≥ t}

M. Aumüller

Distance-Sensitive Hashing

18/22

Filter construction (Unit sphere)(Becker et al. 2016, Christiani 2017, Andoni et al. 2017)

Fix t > 0. Sample a ∼ N d (0, 1), andStore Ua,t = {x ∈ S | ha, xi ≥ t}
1−1
1−1

M. Aumüller

Distance-Sensitive Hashing

18/22

Filter construction (Unit sphere)(Becker et al. 2016, Christiani 2017, Andoni et al. 2017)

Fix t > 0. Sample a ∼ N d (0, 1), andStore Ua,t = {x ∈ S | ha, xi ≥ t}
1−1
1−1

M. Aumüller

Distance-Sensitive Hashing

18/22

Filter construction (Unit sphere)(Becker et al. 2016, Christiani 2017, Andoni et al. 2017)

Fix t > 0. Sample a ∼ N d (0, 1), andStore Ua,t = {x ∈ S | ha, xi ≥ t}

Inspect Ua,t if ha, yi ≥ t

1−1
1−1

M. Aumüller

Distance-Sensitive Hashing

18/22

Filter construction (Unit sphere)(Becker et al. 2016, Christiani 2017, Andoni et al. 2017)

Fix t > 0. Sample a ∼ N d (0, 1), andStore Ua,t = {x ∈ S | ha, xi ≥ t}

Inspect Ua,t if ha, yi ≥ t

1−1
1−1

M. Aumüller

Distance-Sensitive Hashing

18/22

Filter construction (Unit sphere)(Becker et al. 2016, Christiani 2017, Andoni et al. 2017)

Fix t > 0. Sample a ∼ N d (0, 1), andStore Ua,t = {x ∈ S | ha, xi ≥ t}

Inspect Ua,t if ha, yi≤ −t

1−1
1−1

M. Aumüller

Distance-Sensitive Hashing

18/22

Filter construction (Unit sphere)(Becker et al. 2016, Christiani 2017, Andoni et al. 2017)

Fix t > 0. Sample a ∼ N d (0, 1), andStore Ua,t = {x ∈ S | ha, xi ≥ t}

Inspect Ua,t if ha, yi≤ −t

1

1−1−1
1−1

M. Aumüller

Distance-Sensitive Hashing

1−1

18/22

Filter construction (Unit sphere)(Becker et al. 2016, Christiani 2017, Andoni et al. 2017)

Fix t > 0. Sample a ∼ N d (0, 1), andStore Ua,t = {x ∈ S | ha, xi ≥ t}

Inspect Ua,t if ha, yi≤ −t

1

1−1−1
1−1

M. Aumüller

Distance-Sensitive Hashing

1−1

18/22

Filter construction (Unit sphere)(Becker et al. 2016, Christiani 2017, Andoni et al. 2017)

Fix t > 0. Sample a ∼ N d (0, 1), andStore Ua,t = {x ∈ S | ha, xi ≥ t}

Inspect Ua,t if ha, yi≤ −t

1

1−1−1
1−1

M. Aumüller

Distance-Sensitive Hashing

1−118/22

Filter construction (Unit sphere)(Becker et al. 2016, Christiani 2017, Andoni et al. 2017)

Fix t > 0. Sample a ∼ N d (0, 1), andStore Ua,t = {x ∈ S | ha, xi ≥ t}

Inspect Ua,t if ha, yi≤ −t

1

1−1−1
1−1

1−1

LSF:
ρ+ = O(1/c 2 )optimalM. Aumüller

Distance-Sensitive Hashing

18/22

Filter construction (Unit sphere)(Becker et al. 2016, Christiani 2017, Andoni et al. 2017)

Fix t > 0. Sample a ∼ N d (0, 1), andStore Ua,t = {x ∈ S | ha, xi ≥ t}

Inspect Ua,t if ha, yi≤ −t

1

1−1−1
1−1

1−1Anti-LSF:

LSF:
ρ+= O(1/c 2 )optimal?

optimalM. Aumüller

ρ− = O(1/c 2 )Distance-Sensitive Hashing

18/22

Filter construction (Unit sphere)(Becker et al. 2016, Christiani 2017, Andoni et al. 2017)

Fix t > 0. Sample a ∼ N d (0, 1), andStore Ua,t = {x ∈ S | ha, xi ≥ t}

Inspect Ua,t if ha, yi≤ −t

1

1−1−1
1

1−1
LSF:

−1Annulus-LSF:

ρ+= O(1/c 2 )optimalM. Aumüller

ρ+ + ρ−optimal?

Distance-Sensitive HashingAnti-LSF:= O(1/c 2 )ρ− = O(1/c 2 )optimal?
18/22

Filter construction (Unit sphere)(Becker et al. 2016, Christiani 2017, Andoni et al. 2017)

Fix t > 0. Sample a ∼ N d (0, 1), andStore Ua,t = {x ∈ S | ha, xi ≥ t}

LSF:

Inspect Ua,t if ha, yi≤ −tAnnulus-LSF:
ρ+= O(1/c 2 )optimalM. Aumüller

ρ+ + ρ−optimal?

Distance-Sensitive HashingAnti-LSF:= O(1/c 2 )ρ− = O(1/c 2 )optimal?
18/22

A Lower Bound on the Unit SphereSetting: distance√2 vs. distance√2/c (random vs. correlated).

Theorem
For every distance-sensitive family with CPF f we have√log(f ( 2))1√ρ− =≥ 2.
2c − 1log(f ( 2/c))(Matches LSH lower bounds, but is dual to them.)

M. Aumüller

Distance-Sensitive Hashing

19/22

Privacy-preserving distance estimation
Problem inspired by (Riazi et al. ’16)x→

dist(x, y) ≤ r?

←y

AliceBobGoals: Don’t reveal vectors, don’t reveal actual distance.
For an approximation factor c > 1, and parameters ε, δ > 0:dist(x, y) ≤ r, we say “Yes” with probability at least 1 − ε.
dist(x, y) ≥ cr, we say “No” with probability at least 1 − δ.

M. Aumüller

Distance-Sensitive Hashing

20/22

Solution via “step-function CPFs”

yx

Checked using “privacy-preserving set intersection”
M. Aumüller

Distance-Sensitive Hashing

21/22

Solution via “step-function CPFs”
0.10

0.08

0.06

0.04

0.02

510

15

20

yx

Checked using “privacy-preserving set intersection”
M. Aumüller

Distance-Sensitive Hashing21/22

Solution via “step-function CPFs”
0.10

0.08

0.06

0.04

0.02

5x

10

1520

Choose (h1 , g1 ), . . . , (ht , gt ) ∼ D

yChecked using “privacy-preserving set intersection”
M. Aumüller

Distance-Sensitive Hashing

21/22

Solution via “step-function CPFs”
0.10

0.08

0.06

0.04

0.02

5x

10

1520

Choose (h1 , g1 ), . . . , (ht , gt ) ∼ D.

y&

Checked using “privacy-preserving set intersection”
M. Aumüller

Distance-Sensitive Hashing

21/22

Solution via “step-function CPFs”
0.100.08

0.06

0.04

0.02

5x
⇓

10

15

20

Choose (h1 , g1 ), . . . , (ht , gt ) ∼ D.

&y⇓

Checked using “privacy-preserving set intersection”
M. Aumüller

Distance-Sensitive Hashing

21/22

Solution via “step-function CPFs”
0.10

0.08

0.06

0.04

0.02

5x
⇓

10

1520

Choose (h1 , g1 ), . . . , (ht , gt ) ∼ D.

A = {h1 (x), . . . , ht (x)}&y⇓B = {g1 (y), . . . , gt (y)}Checked using “privacy-preserving set intersection”
M. Aumüller

Distance-Sensitive Hashing

21/22

Solution via “step-function CPFs”
0.10

0.08

0.06

0.04

0.02

5x
⇓

1015

20

Choose (h1 , g1 ), . . . , (ht , gt ) ∼ D.

A = {h1 (x), . . . , ht (x)}&&y⇓B = {g1 (y), . . . , gt (y)}.

Checked using “privacy-preserving set intersection”
M. Aumüller

Distance-Sensitive Hashing

21/22

Solution via “step-function CPFs”
0.10

0.08

0.06

0.04

0.02

5x
⇓

101520Choose (h1 , g1 ), . . . , (ht , gt ) ∼ D.

&A = {h1 (x), . . . , ht (x)}&y⇓B = {g1 (y), . . . , gt (y)}.
“Yes” ⇔: A ∩ B 6= ∅Checked using “privacy-preserving set intersection”
M. Aumüller

Distance-Sensitive Hashing

21/22

Solution via “step-function CPFs”
0.10

0.08

0.06

0.04

0.02

5x
⇓

10

15

20

Choose (h1 , g1 ), . . . , (ht , gt ) ∼ D.

&

A = {h1 (x), . . . , ht (x)}&y⇓B = {g1 (y), . . . , gt (y)}.
“Yes” ⇔: A ∩ B 6= ∅Checked using “privacy-preserving set intersection”
M. Aumüller

Distance-Sensitive Hashing

21/22

Conclusion & Open Problems
Introduced notion of “distance-sensitive” hash families… generalization of locality-sensitive hashing
Applications:annulus queries
estimating a function
I privacy-preserving distance estimation
II

Provided some initial constructions and a lower bound on “anti-LSH”

M. Aumüller

Distance-Sensitive Hashing

22/22

Conclusion & Open Problems
Introduced notion of “distance-sensitive” hash families… generalization of locality-sensitive hashing
Applications:annulus queries
estimating a function
I privacy-preserving distance estimation
II

Provided some initial constructions and a lower bound on “anti-LSH”
Open:
Which functions f admit a distance-sensitive hash family?
Better solution to annulus queries than combining LSH + anti-LSH(which gives O(n2ρ ) query time)?

M. Aumüller

Distance-Sensitive Hashing

22/22

Conclusion & Open Problems
Introduced notion of “distance-sensitive” hash families… generalization of locality-sensitive hashing
Applications:annulus queries
estimating a function
I privacy-preserving distance estimation
II

Provided some initial constructions and a lower bound on “anti-LSH”
Open:
Which functions f admit a distance-sensitive hash family?
Better solution to annulus queries than combining LSH + anti-LSH(which gives O(n2ρ ) query time)?

Thank you!
M. Aumüller

Distance-Sensitive Hashing

22/22