Anzeige
Erschienen in:
2017 | OriginalPaper | Buchkapitel
Accurate Low-Space Approximation of Metric k-Median for Insertion-Only Streams
verfasst von : Vladimir Braverman, Harry Lang, Keith Levin
Erschienen in: Algorithms and Discrete Applied Mathematics
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
We present a low-constant approximation for metric k-median on an insertion-only stream of n points using \(O(\epsilon ^{-3} k \log n)\) space. In particular, we present a streaming \((O(\epsilon ^{-3} k \log n), 2 + \epsilon )\)-bicriterion solution that reports cluster weights. It is well-known that running an offline algorithm on this bicriterion solution yields a \((17.66 + \epsilon )\)-approximation.
Previously, there have been two lines of research that trade off between space and accuracy in the streaming k-median problem. To date, the best-known \((k,\epsilon )\)-coreset construction requires \(O(\epsilon ^{-2} k \log ^4 n)\) space [8], while the best-known \(O(k \log n)\)-space algorithm provides only a \((O(k \log n), 1063)\)-bicriterion [3]. Our work narrows this gap significantly, matching the best-known space while significantly improving the accuracy from 1063 to \(2+\epsilon \). We also provide a matching lower bound, showing that any \({\text {polylog}}(n)\)-space streaming algorithm that maintains an \((\alpha ,\beta )\)-bicriterion must have \(\beta \ge 2\).
Our technique breaks the stream into segments defined by jumps in the optimal clustering cost, which increases monotonically as the stream progresses. By a storing an accurate summary of recent segments and a lower-space summary of older segments, our algorithm maintains a \((O(\epsilon ^{-3} k \log n), 2 + \epsilon )\)-bicriterion solution for the entire input.