en
0.25
0.5
0.75
1.25
1.5
1.75
2
Geometric Computing over Uncertain Data
Published on Oct 02, 20123358 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
Chapter list
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