< ^ >

Proposed Approach: CurveIx

Based on the method developed in [Megiddo and Shaft]

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

[Diagram:pic/c-curves]

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?


< ^ >