en
0.25
0.5
0.75
1.25
1.5
1.75
2
Geometric Computing over Uncertain Data
Published on 2012-10-023368 Views
Geometric structures such as the convex hull, Delaunay triangulation, or minimum spanning tree (MST) are fundamental tools for reasoning about multi-dimensional data. What happens to these structure
Related categories
Presentation
Geometric Computing over Uncertain Data00:00
Geometric Computing (1)00:13
Geometric Computing (2)00:34
Geometric Computing (3)01:11
Geometric Computing and Uncertainty01:26
Uncertain Point Data: A simple model (1)03:18
Uncertain Point Data: A simple model (2)03:38
Uncertain Point Data: A simple model (3)04:33
Data-Driven Science05:20
Computing with Uncertain Data06:11
Related Work: Geometry (1)06:46
Related Work: Geometry (2)06:57
Related Work: Geometry (3)07:47
Related Work: Optimization08:41
Related Work: Databases09:52
Uncertain Minimum Spanning Tree (1)11:12
Uncertain Minimum Spanning Tree (2)11:25
Uncertain Minimum Spanning Tree (3)12:20
Uncertain Minimum Spanning Tree (4)13:01
Computational Geometry under Uncertainty13:16
Expectation for Proximity Graphs (1)15:07
Expectation for Proximity Graphs (2)15:10
Back to MST and Proximity Graphs (1)16:25
Back to MST and Proximity Graphs (2)16:27
MST and Proximity Graphs17:20
Results on Stochastic MST17:52
Hardness: Reduction from Network Reliability (1)18:40
Hardness: Reduction from Network Reliability (2)19:21
The Construction (1)19:43
The Construction (2)20:55
Network Reliability to MST21:51
Finishing the Proof (1)23:02
Finishing the Proof (2)23:22
Finishing the Proof (3)24:09
Approximation: E[MST] by Sampling (1)24:14
Approximation: E[MST] by Sampling (2)25:21
Approximation: E[MST] by Sampling (3)26:22
Approximation: E[MST] by Conditioning (1)26:25
Approximation: E[MST] by Conditioning (2)26:54
Approximation: E[MST] by Conditioning (3)27:40
Approximation: E[MST] by Conditioning (4)28:05
Approximation: E[MST] by Conditioning (5)28:13
Approximation: E[MST] by Conditioning (6)28:26
Approximation: E[MST] by Conditioning (7)28:38
Approximation: E[MST] by Conditioning (8)29:29
Approximation: E[MST] by Conditioning (9)30:25
Distribution of MST Length (1)30:28
Distribution of MST Length (2)30:48
Tail Bound for Probabilistic MST30:59
Deterministic Approximation of E[MST] in 2D31:51
Stochastic Closest Pair (1)33:01
Stochastic Closest Pair (2)34:17
Stochastic Closest Pair (3)34:30
Stochastic Closest Pair (4)34:38
Stochastic Closest Pair (5)34:45
Stochastic Closest Pair (6)34:59
Complexity of Stochastic Closest Pair35:02
Traveling Salesman Tour Through Uncertain Regions (1)36:27
Traveling Salesman Tour Through Uncertain Regions (2)37:11
Traveling Salesman Tour Through Uncertain Regions (3)37:25
Traveling Salesman Tour Through Uncertain Regions (4)39:32
Stochastic TSP: formal model40:20
The Main Idea (1)42:38
The Main Idea (2)43:06
The Main Idea (3)43:43
The Main Idea (4)44:50
Conclusions and Future Directions45:20