[prev] 70 [next]

Approaches to kNN Retrieval

Partition-based
  • use auxiliary data structure to identify candidates
  • space/data-partitioning methods: e.g. k-d-B-tree, R-tree, ...
  • unfortunately, such methods "fail" when #dims > 10..20
  • absolute upper bound on d before linear scan is best d = 610
Approximation-based
  • use approximating data structure to identify candidates
  • signatures: VA-files
  • projections: iDistance, LSH, MedRank, CurveIX, Pyramid