在路网查询kNN即K个最近邻.pptx

Memory-Efficient Algorithms forSpatial Network Queries 1 Sarana Nutanong, Hanan Samet Center for Automation Research, Institute for Advanced Computer Studies Department of Computer Science, University of Maryland College Park, Maryland 20742 {nutanong, hjs}@cs.umd.edu 2013 ICDE 2 OutLine Traditional Solution Problem Statement Our Solution Summarize 3 Problem Statement KNN( k nearest neighbors) query: Given: a query point q a set D={a,b,c,d} of locations a number k Return :a set A(top k nearest ) NetWork Type n1 n2 n4 n5 n6 n7 n8 n3 a b c d q 4 A is better than B Euclidean distance : ||Q − B|| ||Q – A|| Network distance : Dist(Q,B) Dist(Q,A) Meaningful accurate metric Euclidean distance or Network distance ？ 5 OutLine Traditional Solution Problem Statement Our Solution Summarize 6 Existing algorithms INE : Incremental Network Expansion IER : Incremental Euclidean Restriction 7 INE (Incremental Network Expansion) Main idea : Dijkstra’s algorithm (n1,3) d(q,p5) = 7 MAX visit of nodes that cannot possibly lead to the k nearest neighbors 8 MAX terminate drawback: (n2,5) (n2,5) (n7,12) (n4,8) (n3,9) (n7,12) q n7 n2 n3 n4 p1 p2 n8 n1 p5 p3 p4 n6 n5 (n7,12) (n4,8) n10 n9 6 1 (n10,15) (n3,9) (n7,12) 8 p1 p4 p2 q P1 demax = dN(p1) P2 de2 demax , satisfy dN(p2) dN(p1) demax = dN(p2) P3 de3 demax ,satisfy dN(p3) dN(p2) terminate IER (Incremental Euclidean Restriction) repeated visits to nodes that appear on the shortest paths to different k nearest neighbors drawback: Main idea : Euclidean distance Network distance p3 P2 NN: P4 de4 demax P1 p5 p6 9 OutLine Traditional Solution Problem Statement Our Solution Summarize 10 n1 n5 n2 n6 n7 n3 n4 n8 a q b d (SWH) single-wavefront heuristic ||d-d|| = 0 ||n6-b|| ||n1-a|| How to