Deterministic Sampling and Range Counting in Geometric Data Streams

Details Deterministic Sampling and Range Counting in Geometric Data Streams Deterministic Sampling and Range Counting in Geometric Data Streams

2003-07-11

arxiv.org/abs/cs/0307027v1

ACM Trans. Algorithms 3(2):A16, 2007

Computer Science

Computational Geometry

12 pages, 1 figure

Scientific paper

10.1145/1240233.1240239

We present memory-efficient deterministic algorithms for constructing epsilon-nets and epsilon-approximations of streams of geometric data. Unlike probabilistic approaches, these deterministic samples provide guaranteed bounds on their approximation factors. We show how our deterministic samples can be used to answer approximate online iceberg geometric queries on data streams. We use these techniques to approximate several robust statistics of geometric data streams, including Tukey depth, simplicial depth, regression depth, the Thiel-Sen estimator, and the least median of squares. Our algorithms use only a polylogarithmic amount of memory, provided the desired approximation factors are inverse-polylogarithmic. We also include a lower bound for non-iceberg geometric queries.

Affiliated with

Also associated with

No associations

Rating

Deterministic Sampling and Range Counting in Geometric Data Streams does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Deterministic Sampling and Range Counting in Geometric Data Streams, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deterministic Sampling and Range Counting in Geometric Data Streams will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-629012