Queries (cont.)

Nearest-neighbor

• [Roussopoulus et al.]’s top-down algorithm
• [Hjaltson,Samet]’s priority-queue algorithm
  • optimal in number of nodes accessed
  • space-usage: O(n) for n data items
• Our approach: modification of HS algorithm
  • space-usage: O(n/fanout +k) for k-nn query

Previous slide

Next slide

Back to first slide

View graphic version