9/3/20091Nearest Neighbor QueriesLing [email protected] Roussopoulos, Stephen Kelly and Frédéric VincentOutline• Spatial Index –R‐Tree• NN query –Naïve solution• A better solution –Branch‐and‐bound• Can we do better?• Experiment Results223145RR--TreeTree6789101112323145RR--TreeTreeEF231456789101112GH4678910111223145EFRR--TreeTreeB231456789101112CGH56789101112623145ABEFRR--TreeTreeBCEFGHA:B:C:Pointer MBROne entry:6231456789101112CGHB:456123 101112789EFGH667891011129/3/20092Outline• Spatial Index –R‐Tree• NN query –Naïve solution• A better solution –Branch‐and‐bound• Can we do better?• Experiment Results7Nearest Neighbor Search• Retrieve the nearest neighbor of query point Q• Simple Strategy:– 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 til bj t fd8until an object found.– Compute distance d’ between Q and O – re‐execute the range query with the distance d’ around Q.– Compute distance of Q fr om each retrieved object. The object at minimum distance is the nearest neighbor!!!Naïve ApproachABEFBCEFGHA:B:C:456 1 2310 11 12EFG23145CGHQuery Point QIssues: how to guess range? The retrieval may be sub‐optimal if incorrect range guessed. Would be a problem in high dimensional spaces.789H67589101112Outline• Spatial Index –R‐Tree• NN query –Naïve solution• A better solution –Branch‐and‐bound• Can we do better?• Experiment Results10MINDIST Property• MINDIST is a lower bound of any k-NN distance(s1, s2)(t1, t2)(p1, p2)(p1, p2)(p1, p2)(p1, p2)(p1, p2)11A Better Strategy for KNN search• 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)12• k‐NN can be computed incrementally;I/O optimal9/3/20093Priority QueueBCEFGHA:B:C:456123 101112789EFGH23145ABEFAB CE FC6758911CGHQuery Point QC5 6 4 FH 5 G 6 4 F7 5 8 9G 6 4 F1NN131012Outline• Spatial Index –R‐Tree• NN query –Naïve solution• A better solution –Branch‐and‐bound• Can we do better?• Experiment Results14MBR Face Property• MBR is an n‐dimensional Minimal BoundingRectangle used in R trees, which is the minimalbounding n‐dimensional rectangle bounds itscorrespondingobjectscorrespondingobjects.• MBR face property: Every face of any MBR contains at least one point of some object in the database. 15MBR Face Property –2D16MBR Face Property –3DRectangle R17Improving the KNN Algorithm• While the MinDist based algorithm is I/O optimal, its performance may be further improved by pruning nodes from the priority queue18queue.9/3/20094Properties of MINMAXDIST• MINMAXDIST(P,R) is the minimum over all dimensionsdistances from P to the furthest point of the closest face ofR.• MINMAXDIST is the smallest possible upper bound ofdistances from the point P to the rectangle R.• MINMAXDIST guarantees there is an object within the Rat a distance to P less than or equal to it.• MINMAXDIST is an upper bound of the 1-NNdistance19MINDIST & MINMAXDISTMINDIST(P,R) <= NN(P) <= MINMAXDIST(P,R)20MinDist & MinMaxDist –3DQuery Point QRectangle RMinDist(Q,R)MinMaxDist(Q,R)21Pruning 1• Downward pruning:AnMBRRisdiscardedRR’If there exists another R’ such that MINDIST(P,R)> MINMAXDIST(P,R’)RMINDISTPMINMAXDIST22Pruning 2• Downward pruning: An object O is discardedOR’If there exists an R such that Actual_dist(P,O) > MINIMAXDIST(P,R)ORActual‐distPMINMAXDIST23Pruning 3• Upward pruning:AnMBRRisdiscardedRIf an object O is found such that MINDIST(P,R) > Actual_dist(P,O)ROMINDISTPActual_dist249/3/20095MINDIST vs MINMAXDIST Ordering• MINDIST: optimistic• MINMAXDIST: pessimistic25• Example: MINDIST ordering finds the 1‐NN firstMINDIST vs MINMAXDIST Ordering26• Example: MINMAXDIST ordering finds the 1‐NN firstGeneralize to k‐NN • Keep a sorted buffer of at most k current nearest neighbors• Pruning is done according to the distance of the furthest nearest neighbor in this buffer27• Example:RThe k‐th object in the bufferMINDISTPActual_distOutline• Spatial Index –R‐Tree• NN Query –Intuitive Solutions• Optimized NN Query –branch‐and‐bound• Experiment Results9/3/20096Key Insights• # of pages accessed grows when k grews;• The denser the dataset, the more page access;• MinDist v.s. MinMaxDist: same in shape, but iih /OMinMaxDisthas more I/O cost;• In Dense area, MinMaxDist is bad;Thanks & Questions
View Full Document
Unlocking...