Randomized partition trees for exact nearest neighbor search thumbnail
Pause
Mute
Subtitles
Playback speed
0.25
0.5
0.75
1
1.25
1.5
1.75
2
Full screen

Randomized partition trees for exact nearest neighbor search

Published on Aug 09, 20134460 Views

The k-d tree was one of the first spatial data structures proposed for nearest neighbor search. Its efficacy is diminished in high-dimensional spaces, but several variants, with randomization and over

Related categories

Chapter list

Randomized partition trees for exact nearest neighbor search00:00
The complexity of nearest neighbor search - 100:05
The complexity of nearest neighbor search - 201:17
The complexity of nearest neighbor search - 302:42
Approximate nearest neighbor - 103:01
Approximate nearest neighbor - 203:24
Approximate nearest neighbor - 304:04
Low intrinsic dimension - 104:50
Low intrinsic dimension - 206:02
Low intrinsic dimension - 306:50
The k-d tree: a hierarchical partition of Rd - 107:43
The k-d tree: a hierarchical partition of Rd - 209:09
The k-d tree: a hierarchical partition of Rd - 309:42
Random projection tree09:56
Overlapping cells: spill trees - 110:38
Overlapping cells: spill trees - 211:36
Three trees12:10
Failure probability - 113:17
Failure probability - 214:55
Random projection of three points15:39
Random projection of a set of points16:44
A single cell of the spill tree - 117:59
A single cell of the spill tree - 218:00
A single cell of the spill tree - 318:01
Failure probability of NN search - 118:39
Failure probability of NN search - 218:58
Failure probability of NN search - 318:59
Failure probability of NN search - 418:59
Doubling measures - 119:11
Doubling measures - 219:25
Doubling measures - 319:59
A simple topic model - 120:15
A simple topic model - 220:30
A simple topic model - 320:31
Are random directions needed? - 120:55
Are random directions needed? - 220:57
Open problems - 120:57
Open problems - 220:59
Thanks21:43