TD 1 - Nearest Neighbor Search


Your opinion on today's lecture:

In this practical session we explore a variant of the Random-Projection trees (RP-trees) that has been designed to solve the quantization problem efficiently. The idea is to change the splitting rule at each node of the tree, so that the resulting quantization error grows with the intrinsic dimension of the data, as opposed to growing with its ambient dimension.

The paper under study can be found here:

Reading the paper

Let us first read the paper together. Our goal is to spot the important parts quickly, and to get a fairly precise idea of their content within a limited amount of time. Typically, we should ask ourselves the following questions about the context of the paper: And now about the contribution: Finally about the method itself:

Going beyond the paper

Pick one or more questions left open in the paper. These can be either of a theoretical nature, or of a practical nature, or both. In the present case you can for instance investigate:



Last modification: Sep. 28 2018