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.
Vår konstruktion för universala outliers är något liknande konceptuellt till REF, där en strömmande algoritm för k-center kluster med outliers presenteras.
Streaming Algorithms for k-Center Clustering with Outliers and with Anonymity
{'venue': 'APPROX-RANDOM', 'journal': None, 'mag_field_of_study': ['Computer Science']}