Algorithms for dynamic geometric data streams / Gereon Frahling. [2006]
Content
- Acknowledgements
- Contents
- Introduction
- Preliminaries
- Sampling Data Streams
- The Unique Element (UE) Data Structure
- The Distinct Elements (DE) Data Structure
- A Sample Data Structure using Totally Random Hash Functions
- A Sample Data Structure using Random Number Generators
- A Sample Data Structure using Pairwise Independent Hash Functions
- Sampling Geometric Data Streams and Applications
- Sampling Geometric Data Streams
- -Nets and -Approximations in Data Streams
- Random Sampling with Neighborhood Information
- Estimating the Weight of a Euclidean Minimum Spanning Tree
- The Coreset Method
- Definitions
- Coresets for k-Median
- Coresets for k-Means
- Coresets for Oblivious Optimization Problems
- Constructing Solutions on the Coreset
- Coresets via Sampling
- Coresets in Data Streams
- A Kinetic Data Structure for MaxCut
- An Efficient k-Means Implementation using Coresets
- Counting Motifs in Data Streams
- Counting Triangles in Adjacency Streams
- Counting Triangles in Incidence Streams
- Counting Cliques of Arbitrary Size
- Counting K3,3 in Incidence Streams
- Conclusions
- Bibliography