Streaming Algorithms for Extent Problems in High Dimensions

Pankaj K. Agarwal, R. SharathkumarSODA 2010 · OpenReview

Abstract

We develop (single-pass) streaming algorithms for maintaining extent measures of a stream S of n points in ℝd. We focus on designing streaming algorithms whose working space is polynomial in d (poly(d)) and sub-linear in n. For the problems of computing diameter, width and minimum enclosing ball of S, we obtain lower bounds on the worst-case approximation ratio of any streaming algorithm that uses poly(d) space. On the positive side, we introduce the notion of blurred ball cover and use it for answering approximate farthest-point queries and maintaining approximate minimum enclosing ball and diameter of S. We describe a streaming algorithm for maintaining a blurred ball cover whose working space is linear in d and independent of n.
BibTeX
@inproceedings{agarwal2010streaming,
  author = {Pankaj K. Agarwal and R. Sharathkumar},
  title = {{Streaming Algorithms for Extent Problems in High Dimensions}},
  booktitle = {SODA},
  year = {2010},
  url = {https://openreview.net/forum?id=oo1aHwclUDl},
}

Loading related content...

Figure