(And possibly earlier? ... the idea of space-filling curves has been around for a while)

The basic idea:

• project d-dimensional vector onto 1-d space-filling curve

• collect set of curve-neighbours (should contain some k-NN)

• repeat above for several curves with different paths through space

• union of neighbour sets from all curves gives candidates

• retrieve and compute distance only for candidates

We want candidate set to contain most/all of k-NN ...

• how many curves do we need?

• how many neighbours do we examine on each curve?