SAMPLING IN DYNAMIC DATA STREAMS AND APPLICATIONS

Abstract

A dynamic geometric data stream is a sequence of m ADD/REMOVE operations of points from a discrete geometric space {1,…, Δ} d ? . ADD (p) inserts a point p from {1,…, Δ} d into the current point set P , REMOVE(p) deletes p from P . We develop low-storage data structures to (i) maintain ε-nets and ε-approximations of range spaces of P with small VC-dimension and (ii) maintain a (1 + ε)-approximation of the weight of the Euclidean minimum spanning tree of P . Our data structure for ε-nets uses [Formula: see text] bits of memory and returns with probability 1 – δ a set of [Formula: see text] points that is an e-net for an arbitrary fixed finite range space with VC-dimension [Formula: see text]. Our data structure for ε-approximations uses [Formula: see text] bits of memory and returns with probability 1 – δ a set of [Formula: see text] points that is an ε-approximation for an arbitrary fixed finite range space with VC-dimension [Formula: see text]. The data structure for the approximation of the weight of a Euclidean minimum spanning tree uses O ( log (1/δ)( log Δ/ε) O ( d ) ) space and is correct with probability at least 1 – δ. Our results are based on a new data structure that maintains a set of elements chosen (almost) uniformly at random from P .