Vi presenterar algoritmer för snabb kvantil- och frekvensuppskattning i stora dataströmmar med grafikprocessorer (GPU). Vi utnyttjar grafikprocessorernas höga beräkningskraft och minnesbandbredd och presenterar en ny sorteringsalgoritm som utför rasterisering på GPU:erna. Vi använder sortering som den viktigaste beräkningskomponenten för histogram approximation och konstruktion av -ungefärliga kvantilika och frekvenssammanfattningar. Våra algoritmer för numerisk statistik beräkning av dataströmmar är deterministiska, tillämpliga på fasta eller rörliga skjutfönster och använder ett begränsat minnesavtryck. Vi använder GPU som medprocessor och minimerar dataöverföringen mellan CPU och GPU genom att ta hänsyn till den låga buss bandbredden. Vi implementerade våra algoritmer på en PC med en NVIDIA GeForce FX 6800 Ultra GPU och en 3,4 GHz Pentium IV CPU och tillämpade dem på stora dataströmmar bestående av mer än 100 miljoner värden. Vi jämförde också prestandan hos våra GPU-baserade algoritmer med optimerade implementationer av tidigare CPU-baserade algoritmer. Sammantaget visar våra resultat att de grafikprocessorer som finns på ett råvarudatorsystem är effektiva stream-processorer och användbara medprocessorer för gruvdataströmmar.
Ett annat arbete REF presenterar algoritmer för kvantil- och frekvensuppskattning i dataströmmar.
Fast and approximate stream mining of quantiles and frequencies using graphics processors
{'venue': "SIGMOD '05", 'journal': None, 'mag_field_of_study': ['Computer Science']}