Streaming Algorithms for Extent Problems in High Dimensions


Journal Article

© 2013, Springer Science+Business Media New York. We present (single-pass) streaming algorithms for maintaining extent measures of a stream S of n points in $\mathbb{R} ^{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.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Sharathkumar, R

Published Date

  • May 1, 2015

Published In

Volume / Issue

  • 72 / 1

Start / End Page

  • 83 - 98

Electronic International Standard Serial Number (EISSN)

  • 1432-0541

International Standard Serial Number (ISSN)

  • 0178-4617

Digital Object Identifier (DOI)

  • 10.1007/s00453-013-9846-4

Citation Source

  • Scopus