Paper Info
Title
An Almost Space-Optimal Streaming Algorithm for Coresets in Fixed Dimensions
Abstract
We present a new streaming algorithm for maintaining an ε-kernel of a point set in ℝ d using O((1/ε (d−1)/2)log (1/ε)) space. The space used by our algorithm is optimal up to a small logarithmic factor. This significantly improves (for any fixed dimension d ≥3) the best previous algorithm for this problem that uses O(1/ε d−(3/2)) space, presented by Agarwal and Yu. Our algorithm immediately improves the space complexity of the previous streaming algorithms for a number of fundamental geometric optimization problems in fixed dimensions, including width, minimum-volume bounding box, minimum-radius enclosing cylinder, minimum-width enclosing annulus, etc.
Year
DOI
Venue
2011
10.1007/s00453-010-9392-2
Algorithmica - Special Issue: European Symposium on Algorithms
Keywords
Field
DocType
approximation algorithms · data streams · geometric optimization problems · coresets,space complexity,streaming algorithm
Approximation algorithm,Discrete mathematics,Combinatorics,Data stream mining,Curve fitting,Streaming algorithm,Computational geometry,Cylinder,Logarithm,Optimization problem,Mathematics
Journal
Volume
Issue
ISSN
60
1
0178-4617
Citations 
PageRank 
References 
11
0.60
12
Authors
1
Name
Order
Citations
PageRank
Hamid Zarrabi-Zadeh111113.63