USC CSCI 599  Nearest Neighbor Queries Slides (6 pages)
Previewing pages 1, 2 of 6 page document View the full content.Nearest Neighbor Queries Slides
Previewing pages 1, 2 of actual document.
View the full content.View Full Document
Nearest Neighbor Queries Slides
0 0 133 views
Lecture Notes
 Pages:
 6
 School:
 University of Southern California
 Course:
 Csci 599  Special Topics
Special Topics Documents

22 pages

34 pages

10 pages

20 pages

20 pages

28 pages

44 pages

15 pages

7 pages

20 pages

12 pages

4 pages

6 pages

8 pages

38 pages

5 pages

30 pages

35 pages

12 pages

5 pages

43 pages

20 pages

2 pages

12 pages

3 pages

4 pages

35 pages

20 pages

21 pages

16 pages

21 pages

20 pages

33 pages

7 pages

13 pages

18 pages

19 pages

4 pages

15 pages

28 pages

2 pages

11 pages

35 pages

DataCentric Storage in Sensornets with
16 pages

35 pages

24 pages

5 pages

9 pages

22 pages

37 pages

28 pages

46 pages

19 pages

19 pages

24 pages

16 pages

9 pages

6 pages

9 pages

10 pages

43 pages

15 pages

19 pages

29 pages

24 pages

21 pages

12 pages

7 pages

45 pages

2 pages

2 pages

22 pages

7 pages

23 pages

12 pages

16 pages

12 pages

37 pages

23 pages

17 pages

6 pages

5 pages

Maintaining variance and kmedians over data stream windows
10 pages

25 pages

32 pages

47 pages

9 pages

7 pages

15 pages

20 pages

21 pages

25 pages

2 pages

28 pages

3 pages

17 pages

32 pages

22 pages

12 pages

33 pages

36 pages

20 pages

17 pages

18 pages

28 pages

37 pages
Sign up for free to view:
 This document and 3 million+ documents and flashcards
 High quality study guides, lecture notes, practice exams
 Course Packets handpicked by editors offering a comprehensive review of your courses
 Better Grades Guaranteed
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