USC CSCI 599 - Nearest Neighbor Queries Slides (6 pages)

Previewing pages 1, 2 of 6 page document View the full content.
View Full Document

Nearest Neighbor Queries Slides



Previewing pages 1, 2 of actual document.

View the full content.
View Full Document
View Full Document

Nearest Neighbor Queries Slides

133 views

Lecture Notes


Pages:
6
School:
University of Southern California
Course:
Csci 599 - Special Topics
Special Topics Documents

Unformatted text preview:

9 3 2009 Outline Nearest Neighbor Queries Nick Roussopoulos Stephen Kelly and Fr d ric Vincent Spatial Index R Tree NN query Na ve solution A better solution Branch and bound Can we do better Experiment Results Ling Hu lingh usc edu 2 R Tree R Tree 1 1 2 4 2 E 3 4 5 6 3 F 5 6 11 11 7 12 9 7 G 12 8 9 8 10 H 10 3 4 A R Tree 1 B 2 E 4 F 4 C 7 G 8 10 F A H 5 C 7 G 8 10 C 5 B 12 9 B 3 6 11 12 2 3 6 11 Pointer MBR E 5 R Tree One entry 1 B 9 E E 4 F 5 6 G C F 1 H G 2 3 10 11 12 H H 7 8 9 6 1 9 3 2009 Outline Nearest Neighbor Search Retrieve the nearest neighbor of query point Q Simple Strategy Spatial Index R Tree NN query Na ve solution A better solution Branch and bound Can we do better Experiment Results convert the nearest neighbor search to range search Guess a range around Q that contains at least one object say O if the current guess does not include any answers increase range size until til an object bj t found f d Compute distance d between Q and O re execute the range query with the distance d around Q Compute distance of Q from each retrieved object The object at minimum distance is the nearest neighbor 7 8 Na ve Approach A B A B Outline C 1 F 2 E B 3 E F 5 6 E 4 F 4 G C H G 1 2 3 5 10 11 12 H 7 8 9 6 Query Point Q C 12 11 10 G 7 8 9 H Issues how to guess range The retrieval may be sub optimal if incorrect range guessed Would be a problem in high dimensional spaces Spatial Index R Tree NN query Na ve solution A better solution Branch and bound Can we do better Experiment Results 10 A Better Strategy for KNN search MINDIST Property MINDIST is a lower bound of any k NN distance A sorted priority queue based on MINDIST Nodes traversed in order Stops when there is an object at the top of the queue 1 NN found k NN can be computed incrementally p1 p2 t1 t2 I O optimal p1 p2 p1 p2 s1 s2 p1 p2 p1 p2 11 12 2 9 3 2009 Priority Queue Outline A A B 1 F B E 2 E 5 Query Point Q C 11 10 G F 4 5 6 H G 1 2 3 10 11 12 H 7 8 9 A 6 12 C G F E 3 4 B C 7 8 9 H B C E C C 5 6 4 F H 5 G



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Nearest Neighbor Queries Slides and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Nearest Neighbor Queries Slides and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?