10/23/20091Songhua Xing Cyrus Shahabi andBeiPanContinuous Monitoring of Nearest Neighbors on Land SurfaceSonghua Xing, Cyrus Shahabi and BeiPanInfoLabUniversity of Southern CaliforniaLos Angeles, CA 90089-0781http://infolab.usc.eduOutline Motivation Related Work PreliminariesSurface Index based Approach2Surface Index based Approach Performance Evaluation Conclusion and Future WorkMotivation3Yosemite National ParkMotivationHow to continuously monitor the animals over surface?4MotivationHow to continuously monitor the animals over surface? Problem To continuously monitor k Nearest MovingNeighbor based on the Surface Distance.5the Surface Distance. A variance of Static Surface k Nearest Neighbor Query Why is this problem challenging? Why is this problem important?Motivation Why is this problem challenging? Huge size of surface model Millions of terrain data for a region of 10km×10km Triangular Meshes610/23/20092 Why is this problem challenging? Huge size of surface model Millions of terrain data for a region of 10km×10km Costly surface distance computation Tens of minutes on a modern PC for a terrain of 10 000 triangular meshesMotivation10,000 triangular meshes7Chen-Han Algorithm: O(n2)* Shortest paths on a polyhedron: CHEN, J., HAN, Y., Computational Geometry 1990 Why is this problem challenging? Huge size of surface model Millions of terrain data for a region of 10km×10km Costly surface distance computation Tens of minutes on a modern PC for a terrain of 10 000 triangular meshesMotivation10,000 triangular meshes8Chen-Han Algorithm: O(n2)* Shortest paths on a polyhedron: CHEN, J., HAN, Y., Computational Geometry 1990 Why is this problem challenging? Huge size of surface model Millions of terrain data for a region of 10km×10km Costly surface distance computation Tens of minutes on a modern PC for a terrain of 10 000 triangular meshesMotivation10,000 triangular meshes9Chen-Han Algorithm: O(n2)AB1234AB1234CAB1234AB1234CUnfoldingCase 1Case 2Case 3Case 4……* Shortest paths on a polyhedron: CHEN, J., HAN, Y., Computational Geometry 1990 Why is this problem challenging? Huge size of surface model Millions of terrain data for a region of 10km×10km Costly surface distance computation Tens of minutes on a modern PC for a terrain of 10 000 triangular meshesMotivation10,000 triangular meshes No efficient surface index structure for moving objects Shortest Path Tree on road network can not apply Existing Surface index structures are designed for static environment10Online MapMotivation Why is this problem important? The availability of the data (imagery, elevation) of Earth surface at very high resolutionGeo-realistic GameBattlefield Simulator11resolution The quick geo-realistic rendering of terrain surface on the computer display (e.g., Google Earth™) The prevalence of GPS equipped sensorsJune 2009: the most complete terrain map of the Earth's surface has been published through the collaboration between NASA (USA) and the ASTER (Japan).99% Coverage1.3 Million Images30-Meter Resolution ApplicationsMotivation12Resource ExplorationMars Exploration10/23/20093Outline Motivation Related Work PreliminariesSurface Index based Approach13Surface Index based Approach Performance Evaluation Conclusion and Future WorkRelated WorkEuclidean Space Road Networks SurfaceSpatial DatabasekNN Query Processing14 Conventional kNN Reverse kNN Time-aware kNN Visible kNNRelated WorkEuclidean Space Road Networks SurfaceSpatial DatabasekNN Query Processing15 Conventional kNN Reverse kNN Time-aware kNN Visible kNN9 NN Query: Roussopoulos et al., SIMGOD 1995 9 Influences Set: Korn et al., SIMGOD 20009 Efficient Method for Maximizing Bichromatic Reverse Nearest Neighbor: Wong et al., VLDB 20099 Continuous NN Search: Tao et al,. VLDB 20029 Lazy Updates : Cheema et al,. VLDB 20099 VkNN Query: Nutanong et al., DASFAA 2007Related WorkEuclidean Space Road Networks SurfaceSpatial DatabasekNN Query Processing169 Query Processing in SNDB : Papadias et al., VLDB 20039 V-based kNN in SNDB: Shahabi et al., VLDB 20049 Scalable Network Distance Browsing in Spatial Databases: Samet et al., SIGMOD 20089 RNN in Large Graphs: Yiu et al., TKDE 20069 CNN Monitoring in RN: Mouratidis et al., VLDB 2006 Conventional kNN Reverse kNN Time-aware kNNRelated WorkEuclidean Space Road Networks SurfaceSpatial DatabasekNN Query Processing17 Conventional kNN9 SkNN Query : Deng, Zhou ..., ICDE 2006, VLDB J.Related WorkEuclidean Space Road Networks SurfaceSpatial DatabasekNN Query Processing18 Conventional kNN9 SkNN Query : Deng, Zhou ..., ICDE 2006, VLDB J.9 Indexing Land Surface: Shahabi et al., VLDB 200810/23/20094Outline Motivation Related Work PreliminariesSurface Index based Approach19Surface Index based Approach Performance Evaluation Conclusion and Future WorkPreliminaries Continuous nearest neighbor monitoring in road networks (Mouratidis et al, VLDB 06) Shortest Path Spanning Tree (Dijkstra Tree)20BOUNDARY Observation 1: SE Tree is fat and short. Observation 2: These shortest Preliminaries Surface Expansion Tree (SE Tree)surface paths rarely share common edges. Observation 3: These shortest surface paths do not cross each other.21sourcePreliminariespOld Result Boundary More incoming objects Original Result Boundary contains more than kobjectsNew Result Boundary Continuous Monitoring (k = 3)sp2p1p3p4p5p6j Identify the kthobject and shrink the result boundaryPreliminaries Continuous Monitoring (k = 3)p6Result BoundaryExpansion Boundary More outgoing objects Original Result Boundary contains less than kobjectsDRAWBACKS¾ Expansion is slow;¾ Search Area may be large;¾ SE Tree is fat and short.sp2p1p3p4p5p6j Compute the Expansion Boundary Expand SE tree to Expansion boundary and identify the kthobject inside the search areaSearch RegionOutline Motivation Related Work PreliminariesSurface Index based Approach24Surface Index based Approach Performance Evaluation Conclusion and Future Work10/23/20095Surface Index based Approach Intuition Motivated by Partitioning Shortest Paths on road networks Scalable Network Distance Browsing in Spatial Databases: Samet et al., SIGMOD 2008 (best paper award)Is there a way to partition paths on
View Full Document
Unlocking...