Med tanke på ett mycket stort dataset med måttliga till höga dimensioner, hur skulle man kunna samla ihop sina punkter? För dataset som inte passar ens på en enda disk, parallellism är ett första klassens alternativ. I den här artikeln utforskar vi MapReduce för att samla in denna typ av data. De viktigaste frågorna är a) hur man minimerar I/O-kostnaden, med hänsyn till den redan befintliga datapartitionen (t.ex. på diskar), och b) hur man minimerar nätverkskostnaden bland processnoder. Var och en av dem kan vara en flaskhals. Således föreslår vi det bästa av båda världar -BoW metod, som automatiskt fläckar flaskhalsen och väljer en bra strategi. Våra viktigaste bidrag är: (1) Vi föreslår BoW och noggrant härleda sina kostnadsfunktioner, som dynamiskt väljer den bästa strategin; (2) Vi visar att BoW har många önskvärda funktioner: det kan arbeta med de flesta seriella kluster metoder som en pluggedin kluster subrutin, det balanserar kostnaden för diskåtkomster och nätverksåtkomster, uppnå en mycket bra kompromiss mellan de två, det använder inga användardefinierade parametrar (tack vare våra rimliga standardvärden), det matchar klusterkvaliteten på den seriella algoritmen, och det har nästan linjär uppskalning; och slutligen, (3) Vi rapporterar experiment på verkliga och syntetiska data med miljarder poäng, använder upp till 1, 024 kärnor parallellt. Så vitt vi vet, vår Yahoo! webben är den största verkliga dataset som någonsin rapporterats i databasen subspace clustering litteratur. Det tog bara 8 minuter att samla ihop 0,2 TB av flerdimensionella data, med 128 kärnor.
Cordeiro m.fl. REF presenterar en klusterlösning för att hitta subrymd för högdimensionella data med hjälp av Map/Reduce, men de fokuserar på kompromissproblemet mellan I/O-kostnaden och nätkostnaden och syftar till att dynamiskt välja den bästa strategin.
Clustering very large multi-dimensional datasets with MapReduce
{'venue': 'KDD', 'journal': None, 'mag_field_of_study': ['Computer Science']}