Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases1VoronoiVoronoi--Based K Nearest Based K Nearest Neighbor Search for Spatial Neighbor Search for Spatial Network DatabasesNetwork Databases1Ugur DemiryurekMohammad R. Kolahdouzan & Cyrus ShahabiUniversity of Southern CaliforniaDept. of Computer ScienceLos Angeles, CA [email protected]://infolab.usc.eduAgenda Problem Definition Related WorkVoronoi Diagrams2Voronoi Diagrams Voronoi Based Network Nearest Neighbor (VN3) Experiments DiscussionProblem DefinitionkNN Problem:Given a set of objects Pand query point q, find h k bj i Ph 33the k objects in Pthat are closest to qqRelated WorkSpatial DatabasekNN Query Processing49 NN Query: Roussopoulos et al., SIMGOD 1995 9 K-NN for moving query point: Zong et al., SSTD 20019 Time-parameterized queries : Tao et al., SIMGOD 20029 Continuous NN Search: Tao et al,. VLDB 2002Euclidean Space Road NetworksObject BasedRelated WorkSpatial DatabasekNN Query Processing59 Sina-Continuous querying: Mokbel et al., SIGMOD 20049 Sea-CNN queries: Xiong et al., ICDE 2005 9 Monitoring kNN on moving objects: Yu et al., ICDE 20059 Conceptual partitioning: Mouratidis et al., SIGMOD 2005Euclidean Space Road NetworksSpace BasedExample 1:Finding the 3 closest shopping centers6Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases2Example 2:Finding the 3 closest restaurants to USC with Yahoo7Related WorkSpatial DatabasekNN Query Processing89 Query processing in SNDB : Papadias et al., VLDB 20039 Voronoi-based kNN in SNDB: Shahabi et al., VLDB 2004Euclidean Space Road NetworksRelated WorkQuery processing in SNDB : Papadias et al., VLDB 2003Incremental Network Expension (INE) • Blind expansion hence redundant node access9Related WorkQuery processing in SNDB : Papadias et al., VLDB 2003 Incremental Network Expansion 10Preliminaries: Voronoi Diagram Given set of sites (POI), a Voronoi diagram partitions the plane into disjoint Voronoi polygons (cells), one for each site The region including a site p includes all locations q is closer to the generator of the Voronoi Polygon than any other generator11ggpwhich are closer to p than to any other object p’.Site (Generator)Voronoi Polygonany other generatorpqPreliminaries: Voronoi PropertiespVoronoi Polygon12 Property 1: Voronoi diagram is unique Property 2: Voronoi edges are shared by two generators in equal distance to neighboring generators Property 3: Nearest generator of p is among the generators whose VP shares similar edges with p Property 4: Average number of Voronoi edges per VP is at most 6Vornoi EdgeVoronoi-Based K Nearest Neighbor Search for Spatial Network Databases3Network Voronoi DiagramNodeBorder Point: equal network distance to adjacent generatorsp2p113NodeNetwork EdgeNetwork Voronoi Polygonp3VN3 Approach Offline Index Generation1. Network Voronoi Construction2Index Generation (R-tree)142.Index Generation (Rtree)3. Distance Precomputation Online Query Processing1. Find 1stNN2. Find k NN-> Filter & RefineOffline Step Compute Network Voronoi Polygons (NVP) Index NVPs with R-Tree Precompute the intra (accross polygons) and inter (within polygons) network distances for each NVP1. Precompute the Shortest Path distance from each generator to its border point2. Precompute the Shortest Path between border points15P2P3P4P5P6P7P8P9P1b9P14P13P12P11P10b8b7b6b5b4b3b2b1b15b14b13b12b11b10b26b20b19b18b17b16b25b24b23b22b21b30b29b28b27b33b31b32b37b36b35b34b40b39b38n1n2n3b34P9dn (b34, P9)b35P9dn (b35, P9)b36P9dn (b36, P9)…………b1b2dn (b1, b2)b1b15dn (b1, b15)b1b13dn (b1, b13)…………Example: dn(q, P9) = min(dn(q,b34)+dn(b34,P9), dn(q,b35)+dn(b35,P9), dn(q,b36)+dn (b36,P9))qdn(q,b34)= min (dn(q,b1)+dn(b1,b34), dn(q,b2)+dn(b2,b34),..,dn(q,b8)+dn(b8,b34))Online Step Find 1stNN Search R-Tree to find the NVP that overlaps q Report the generator of the NVP as the 1stNN;Cost: O(logn)16P8P2P3P4P5P6P7P9P1b9P14P13P12P11P10b8b7b6b5b4b3b2b1b15b14b13b12b11b10b26b20b19b18b17b16b25b24b23b22b21b30b29b28b27b33b31b32b37b36b35b34b40b39b38n1n2n3qOnline Step Find k NN Æ Filter & Refine 1stNN = P1 2ndNN ∈ { Neighbors( P1) } (e.g., P3) 3rdNN ∈ { Neighbors( P1) ∪ Neighbors( P3) } (P)NOOOO! it is to much computation if you have many candidatesGOOD NEWS! In theory average # of neighbors= O(5k+1)=O(k)17P8P2P3P4P5P6P7P9P1P14P13P12P10b1q(e.g., P2)Performance of VN3 Data set: Road network in Los Angeles (from NavTeq) 110,000 streets, 79,800 intersections Different points of interest:18 restaurants, auto services, schools, parks, shopping centers, hospitals Measured: Query response time and CPU Comparison with INE [Papadias et al. (vldb03)] Size of candidate set of VN3filter Comparison with R-tree-based KNN [Seidl et al. (sigmod98) and Hjaltason et al. (tods99)]Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases4VN3vs INEVN3 finds the 1stNN using R-TreeINE needs to expand the network around qCPU Time: INE uses a queue which is incrementally updated 19VN3: Performance of Filter StepRatioofsizeofcandidatesettoKdecreasesasK20Ratio of size of candidate set to K decreases as K increasesSome of the new neighbors are already explored! VN3’s filter behaves independently from the density/distribution of points of interest As k increases ratio of number of candidate decreases Some of the new neighbors are already explored!Conclusion A novel approach for KNN queries in SNDB Based on: Pre-calculating the solution space (first order Voronoi diagrams)21ooodaga s) Pre-computing some distances (from borders to points inside each polygon) Outperforms the only other solution for SNDB Independent from object distribution Outperforms the solutions for Euclidean spacein “filtering” Discussion What if the edge weights are changing? What if the both query and data objects are moving?22are moving? What if you like to find the nearest hotel and gas station at the same
View Full Document
Unlocking...