Abstrakt. Kluster är ett vanligt problem i analysen av stora datamängder. Streaming algoritmer, som gör ett enda pass över datauppsättningen med hjälp av små arbetsminnen och producera ett kluster som i kostnad kan jämföras med den optimala offline-lösningen, är särskilt användbara. Vi utvecklar de första streamingalgoritmer som uppnår en konstant faktor approximation till klusterradien för två variationer av k-centerklustret problem. Vi ger en streaming (4+ ) - approximation algoritm med hjälp av O( −1 kz) minne för problemet med avvikelser, där klustret tillåts släppa upp till z av inmatningspunkterna; tidigare arbete använde en slumpmässig provtagningsmetod som ger bara en bicriteria approximation. Vi ger också en streaming (6 + ) - approximation algoritm med hjälp av O( −1 ln( −1 )k + k 2 ) minne för en variation som motiveras av anonymitet överväganden där varje kluster måste innehålla minst ett visst antal inmatningspunkter.
En efterföljande streaming (4 + ) - approximation algoritm föreslogs av REF.
Streaming Algorithms for k-Center Clustering with Outliers and with Anonymity
{'venue': 'APPROX-RANDOM', 'journal': None, 'mag_field_of_study': ['Computer Science']}