Name
Abstract | ||
|---|---|---|
We define a class of algorithms for constructing coresets of (geometric) data sets, and show that algorithms in this class can be dynamized eciently in the insertion- only (data stream) model. As a result, we show that for a set of points in fixed dimensions, additive and mul- tiplicative "-coresets for the k-center problem can be maintained in O(1) and O(k) time respectively, using a data structure whose size is independent of the size of the input. We also provide a faster streaming algorithm for maintaining "-coresets for fat extent-related prob- lems such as diameter and minimum enclosing ball. |
Year | Venue | Keywords |
|---|---|---|
2008 | CCCG | streaming algorithm,data structure |
Field | DocType | Citations |
Data structure,Data set,Combinatorics,Streaming algorithm,Multiplicative function,Data stream,Computer science,Algorithm | Conference | 2 |
PageRank | References | Authors |
0.38 | 15 | 1 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hamid Zarrabi-Zadeh | 1 | 111 | 13.63 |