Name
Abstract | ||
|---|---|---|
We study the 2-center problem with outliers in high-dimensional data streams. Given a stream of points in arbitrary d dimensions, the goal is to find two congruent balls of minimum radius covering all but at most z points. We present a ( 1.8 + ε ) -approximation streaming algorithm, improving over the previous ( 4 + ε ) -approximation algorithm available for the problem. The space complexity and update time of our algorithm are poly ( d , z , 1 / ε ) , independent of the size of the stream. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.comgeo.2016.07.002 | Comput. Geom. |
Keywords | Field | DocType |
k-Center,Outlier,High dimensions,Data stream | Discrete mathematics,Approximation algorithm,Data stream mining,Data stream clustering,Streaming algorithm,Data stream,Ball (bearing),Outlier,Congruence (geometry),Mathematics | Journal |
Volume | Issue | ISSN |
60 | C | 0925-7721 |
Citations | PageRank | References |
1 | 0.35 | 10 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Behnam Hatami | 1 | 1 | 0.35 |
| Hamid Zarrabi-Zadeh | 2 | 111 | 13.63 |