Parameter-free Locality Sensitive Hashing forSpherical Range Reporting
Thomas D. Ahle, Martin Aumüller, Rasmus PaghIT University of Copenhagen

Jan 16, 2017
SODA 2017
Supported byM. Aumüller

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

1/15

r-Spherical Range Reporting

d-dimensional metric space (X , dist),
say Euclidean space (Rd , || · ||2 )M. Aumüller

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

2/15

r-Spherical Range Reporting

M. Aumüller

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

2/15

r-Spherical Range Reportingr

M. Aumüller

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

2/15

r-Spherical Range ReportingrXX

M. Aumüller

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

2/15

r-Spherical Range Reporting

M. Aumüller

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

2/15

r-Spherical Range Reportingr

M. Aumüller

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

2/15

r-Spherical Range Reporting
Xr

XX

M. Aumüller

X X

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

2/15

(c, r)-Spherical Range Reportingr

M. Aumüller

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

3/15

(c, r)-Spherical Range Reportingc·rr

M. Aumüller

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

3/15

(c, r)-Spherical Range Reporting

c·rr
X(X)

X(X)

M. Aumüller

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

3/15

Related Work & DifficultyCurse of dimensionality: Solving exact problem takes linear time(brute-force scan) or space/time exponential in dimension
small-medium dimensions:tree-based approaches (Arya et al., 2010)
I space and/or running time O((1/ε)d ) for 1 + ε approximationIhigh dimensions:“locality-sensitive hashing (LSH)”-based approaches for reporting(Indyk, 2000), (Andoni, 2009)I ρ parameter tied to the LSH family, e.g., 1/c 2 for Euclidean space
I Running time: O(nρ · t) for output size t
I Space: O(n1+ρ )IM. Aumüller

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

4/15

Adaptive LSH Algorithms
vsLSH Theory“You need nρ = 513 repetitions!”

LSH Practice“10 repetitions work just as fine!”

Wantalgorithm adapts to query
has theoretical guarantees
use available space best
Recent related work: (Har-Peled & Mahabadi, SODA 2017)
M. Aumüller

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

5/15

Our Results (in presentation)

1Oracle access to output size t→ can solve Spherical Range
Reporting using LSH in timeO(t(n/t)ρ )2No oracle?
→ “Multi-Level LSH” withadaptive query algorithm finds“best LSH parameters” with littleoverhead

M. Aumüller

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

6/15

Plot of Running Times
Query time W
n1.4
n1.2

Linear ScanO(tnρ )
O(t(n/t)ρ )O(t + nρ )

n1.0
n0.8
n0.6
nρ..
.
0

M. Aumüller

n0.2

n0.4

n0.6

n0.8

n

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

Output size t

7/15

Standard LSH Approach: LSH Function
random space partition

LSH Function

h:X →Z⇒Characteristics:
p1 : (lower bound on) collision probability of two points at distance ≤ r
I p : (upper bound on) collision probability of two points at distance ≥ cr2log(1/p1 )I strength of the LSH: ρ =log(1/p2 )I

M. Aumüller

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

8/15

Standard LSH Approach: LSH Data Structure
12

concatenate k ≥ 1 hash functions
repeat reps(k) := p1−k many times
Point set S

M. Aumüller

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

9/15

Standard LSH Approach: LSH Data Structure
12concatenate k ≥ 1 hash functions
repeat reps(k) := p1−k many times
Point set Shk,1 = h01 ◦ · · · ◦ h0k
Tk,1

M. Aumüller

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

9/15

Standard LSH Approach: LSH Data Structure
12

concatenate k ≥ 1 hash functions
repeat reps(k) := p1−k many times
Point set Shk,1 = h01 ◦ · · · ◦ h0k
Tk,1Tk,2

M. Aumüller

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

9/15

Standard LSH Approach: LSH Data Structure
12concatenate k ≥ 1 hash functions
repeat reps(k) := p1−k many times
Point set Shk,1 = h01 ◦ · · · ◦ h0k
Tk,1Tk,2

M. Aumüller

Tk,3Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

9/15

Standard LSH Approach: LSH Data Structure
12

concatenate k ≥ 1 hash functions
repeat reps(k) := p1−k many times
Point set Shk,1 = h01 ◦ · · · ◦ h0kTk,1Tk,2M. Aumüller

Tk,3Tk,4Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

9/15

Standard LSH Approach: LSH Data Structure
12concatenate k ≥ 1 hash functions
repeat reps(k) := p1−k many times
Point set Shk,1 = h01 ◦ · · · ◦ h0k
Tk,1Tk,2

M. Aumüller

Tk,3Tk,4Tk,5Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

9/15

Standard LSH Approach: LSH Data Structure
12concatenate k ≥ 1 hash functions
repeat reps(k) := p1−k many times
Point set Shk,1 = h01 ◦ · · · ◦ h0kTk,1Tk,2M. Aumüller

Tk,3Tk,4Tk,5···Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

9/15

Standard LSH Approach: LSH Data Structure
12concatenate k ≥ 1 hash functions
repeat reps(k) := p1−k many times
Point set Shk,1 = h01 ◦ · · · ◦ h0khk,iTk,1Tk,iTk,2

M. Aumüller

Tk,3Tk,4Tk,5···Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

9/15

Standard LSH Approach: LSH Data Structure
12concatenate k ≥ 1 hash functions
repeat reps(k) := p1−k many times
Point set Shk,1 = h01 ◦ · · · ◦ h0khk,iTk,1Tk,iTk,2M. Aumüller

Tk,3Tk,4Tk,5······

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

9/15

Standard LSH Approach: LSH Data Structure
12concatenate k ≥ 1 hash functions
repeat reps(k) := p1−k many times
Point set Shk,1 = h01 ◦ · · · ◦ h0khk,reps(K )hk,iTk,1Tk,iTk,2M. Aumüller

Tk,3Tk,4Tk,5······

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

Tk,reps(k)9/15Standard LSH Approach: LSH Data Structure
12concatenate k ≥ 1 hash functions
repeat reps(k) := p1−k many times
Point set Shk,1 = h01 ◦ · · · ◦ h0khk,reps(K )hk,iTk,1Tk,iTk,2Tk,3Tk,4Tk,5······

Tk,reps(k)Query algorithm: Collect all points that collide with the query over alltables, report the ones at distance at most r.
Expected running time?

M. Aumüller

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

9/15

Expected Time: Wk = p1−k (1 +Point set SPhk,ix∈S P(hk (q) = hk (x)))

Tk,1Tk,iTk,2Tk,3Tk,4Tk,5······

Tk,reps(k)Collision Probability

Bit sampling collision probablity
1k=1
k=4

0.5

00

M. Aumüller

0.2

0.4
0.6
0.8
Relative Hamming distanceParameter-free Locality Sensitive Hashing for Spherical Range Reporting

110/15

Expected Time: Wk = p1−k (1 +Point set SPhk,ix∈S P(hk (q) = hk (x)))

Tk,1Tk,iTk,2Tk,3Tk,4Tk,5······

Tk,reps(k)Collision Probability

Bit sampling collision probablity
1r

0.5

00

M. Aumüller

k=1
k=4

0.2

0.4
0.6
0.8
Relative Hamming distanceParameter-free Locality Sensitive Hashing for Spherical Range Reporting

110/15

Expected Time: Wk = p1−k (1 +Point set S

Phk,ix∈S P(hk (q) = hk (x)))

Tk,1Tk,iTk,2Tk,3Tk,4Tk,5······Tk,reps(k)Collision Probability

Bit sampling collision probablity
1r

k=1
k=40.500

M. Aumüller

cr

0.2

0.4
0.6
0.8
Relative Hamming distanceParameter-free Locality Sensitive Hashing for Spherical Range Reporting

110/15

Expected Time: Wk = p1−k (1 +Point set SPhk,ix∈S P(hk (q) = hk (x)))

Tk,1Tk,iTk,2Tk,3Tk,4Tk,5······

Tk,reps(k)Collision Probability

Bit sampling collision probablity
1r

k=1
k=40.500

M. Aumüller

cr0.20.4
0.6
0.8
Relative Hamming distanceParameter-free Locality Sensitive Hashing for Spherical Range Reporting

110/15

Expected Time: Wk = p1−k (1 +Point set SPhk,ix∈S P(hk (q) = hk (x)))

Tk,1

Tk,i
Tk,2Tk,3Tk,4Tk,5······

Tk,reps(k)Collision Probability

Bit sampling collision probablity
1r

Take-aways:– # repetitions grows with k– work per repetition shrinks with k– per query: a best choice of k

0.5

k=1
k=400M. Aumüller

cr0.2

0.40.60.8
Relative Hamming distanceParameter-free Locality Sensitive Hashing for Spherical Range Reporting

110/15

Expansion at the QueryExpansion cq∗ at query q: Largest c such that#points at distance cr ≤ 2 #points at distance r

M. Aumüller

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

11/15

Probing the Right Level
LemmaOutput size t & expansion cq∗ ⇒ there exists k such that

Wk = O t(n/t)ρ∗

,log(1/p1 )∗∗where ρ∗ = log(1/p(c∗ r)) with p(cq r) being prob. of collision at distance cq r.
qM. Aumüller

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

12/15

Probing the Right Level
LemmaOutput size t & expansion cq∗ ⇒ there exists k such that

Wk = O t(n/t)ρ∗

,log(1/p1 )∗∗where ρ∗ = log(1/p(c∗ r)) with p(cq r) being prob. of collision at distance cq r.
qIdea:
expected work:X
X
P(hk (q) = hk (x)) +p1−k 1 +P(hk (q) = hk (x))
x∈Sdist(x,q)≤cq∗ r|M. Aumüllerx∈S
dist(x,q)>cq∗ r{z≤2t by def. of expansion}

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

12/15

Probing the Right Level
Lemma
Output size t & expansion cq∗ ⇒ there exists k such that

Wk = O t(n/t)ρ∗

,log(1/p1 )∗∗where ρ∗ = log(1/p(c∗ r)) with p(cq r) being prob. of collision at distance cq r.
qIdea:
expected work:
XX
P(hk (q) = hk (x)) +p1−k 1 +P(hk (q) = hk (x))
x∈S
dist(x,q)≤cq∗ r|x∈S
dist(x,q)>cq∗ r{z≤2t by def. of expansion}

set k such that ≤ t expected collisions with far points
M. Aumüller

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

12/15

Adaptiveness: Multi-Level LSH + Adaptive Query
WorkLevel

Rep.

Point set S

020

121
p1 = 1/2
222..
.

2KK

M. Aumüller

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

13/15

Adaptiveness: Multi-Level LSH + Adaptive Query
Work

h0,1

Level
0Rep.

Point set S

T0,120211p1 = 1/2222..
.

2KK

M. Aumüller

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

13/15

Adaptiveness: Multi-Level LSH + Adaptive Query
Work

h0,1

Level
0Rep.

Point set S

h1,1T0,1

20

h1,2
1

T1,1 T1,221
p1 = 1/2
222..
.

2KK

M. Aumüller

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

13/15

Adaptiveness: Multi-Level LSH + Adaptive Query
Workh0,1

Level
0Rep.

Point set S

h1,1T0,120

h1,2
1T1,1 T1,221
p1 = 1/22T2,1 T2,2 T2,3 T2,422..
.

2KK

M. Aumüller

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

13/15

Adaptiveness: Multi-Level LSH + Adaptive Query
Work

h0,1Level
0Rep.

Point set S

h1,1T0,120

h1,21.
.
.

T1,1 T1,221
p1 = 1/2

2

T2,1 T2,2 T2,3 T2,422
hK ,i..
.

..
.

..

.
TK ,iK

M. Aumüller

TK ,1

TK ,2

TK ,3

TK ,4

TK ,5······

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

TK ,p−K

13/152K

Adaptiveness: Multi-Level LSH + Adaptive QueryWork

h0,1Level0

Rep.

Point set S

h1,1T0,120

h1,2.
.
.

1T1,1 T1,2

2

1
“bestlevel”
has
expectedwork
T2,1 T2,2 T2,3 T2,4
P−khK P(h(q)
Wbest = min0≤k≤K p1 (1 + x∈S= h(x))),i21p = 1/2

22

that level?
.. How can we .find
..
.

..
.

TK ,iK

M. Aumüller

TK ,1

TK ,2

TK ,3

TK ,4

TK ,5······

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

TK ,p−K

13/152K

Adaptiveness: Multi-Level LSH + Adaptive Query
Workh0,1Level
0Rep.

Point set S

h1,1T0,120h1,21.
.
.

T1,1 T1,221
p1 = 1/2

2T2,1 T2,2 T2,3 T2,4

22
hK ,i..
.

..
.

..

.
TK ,i

K

M. Aumüller

TK ,1

TK ,2

TK ,3

TK ,4

TK ,5······

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

TK ,p−K

13/152K

Adaptiveness: Multi-Level LSH + Adaptive Query
WorkLevel520h0,1Rep.

Point set S

h1,1T0,120

h1,21.
.
.

T1,1 T1,221
p1 = 1/2

2T2,1 T2,2 T2,3 T2,422
hK ,i..
.

..
.

..

.
TK ,iK

M. Aumüller

TK ,1

TK ,2

TK ,3

TK ,4

TK ,5······

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

TK ,p−K

13/15

2KAdaptiveness: Multi-Level LSH + Adaptive Query
WorkLevel520h0,1Rep.

Point set S

h1,1T0,120

h1,2371.
.
.

T1,1 T1,221
p1 = 1/2

2T2,1 T2,2 T2,3 T2,422hK ,i..
.

..
.

..

.
TK ,iK

M. Aumüller

TK ,1TK ,2TK ,3TK ,4TK ,5······

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

TK ,p−K

13/15

2KAdaptiveness: Multi-Level LSH + Adaptive Query
WorkLevel520h0,1Rep.

Point set S

h1,1T0,120

h1,2371.
.
.

T1,1 T1,2

21
p1 = 1/2

47

2T2,1 T2,2 T2,3 T2,4

22
hK ,i..
.

..
.

..

.
TK ,iK

M. Aumüller

TK ,1

TK ,2

TK ,3TK ,4TK ,5······

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

TK ,p−K

13/152K

Adaptiveness: Multi-Level LSH + Adaptive QueryWork

Level

520h0,1Rep.

Point set S

h1,1T0,120

h1,2371.
.
.

T1,1 T1,221
p1 = 1/2

47

2T2,1 T2,2 T2,3 T2,4

22
hK ,i..
.

..
.

..
.

..

.
TK ,iK

M. Aumüller

TK ,1TK ,2

TK ,3

TK ,4

TK ,5······

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

TK ,p−K

13/15

2K

Running Time of Adaptive Algorithm

Theorem
Best level has expected work Wbest ⇒ algorithm has expected running timeO(Wbest log log Wbest ).
algorithm is asymptotically only log log factor away from the best
possible work for the query
log log factor comes from needing ≈ log k more repetitions on level kthen standard LSH approach

M. Aumüller

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

14/15

Conclusion & Open Problems
query algorithm on a multi-level LSH data structure that adapts tobest possible work∗
spherical range reporting in time O(t(n/t)ρ ), where ρ∗ depends on
expansion around the queryin paper: multi-probing-aware variant of algorithm, slight
improvement in running time
Open questions:spherical range reporting in time O(nρ + t), adaptive to query?
usefulness of algorithm for finding k-nearest neighbors?
data-dependent methods?
can we make use of space/time-tradeoff LSH data structures?

M. Aumüller

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

15/15

Conclusion & Open Problems
query algorithm on a multi-level LSH data structure that adapts tobest possible work∗
spherical range reporting in time O(t(n/t)ρ ), where ρ∗ depends onexpansion around the queryin paper: multi-probing-aware variant of algorithm, slight
improvement in running time
Open questions:spherical range reporting in time O(nρ + t), adaptive to query?
usefulness of algorithm for finding k-nearest neighbors?
data-dependent methods?
can we make use of space/time-tradeoff LSH data structures?

Thank you!
M. Aumüller

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting

15/15