Danskere står bag verdens bedste streaming algoritme – Københavns Universitet

Videresend til en ven Resize Print Bookmark and Share

Datalogisk Institut, DIKU > Nyheder > DIKU-nyheder 2017 > Danskere står bag verd...

31. oktober 2017

Danskere står bag verdens bedste streaming algoritme

algoritmer

DIKUs Mikkel Thorup og AUs Kasper Green Larsen er medforfattere på en artikel, der beskriver en streamingalgoritme, der giver andre baghjul på samtlige performance-metrikker.

Artiklen er hentet fra Version 2: Tirsdag, 31. oktober 2017

Streamingalgoritmer er de usynlige helte bag analyser af store mængder livedata. De giver indsigt i massive mængder data uden behov for at stoppe flowet, og de bruges både til at holde styr på packets hos AT&T og til at kortlægge Google-søgninger, mens de bliver gennemført. Et internationalt forskningshold med to danskere var med til at finde verdens bedste af slagsen sidste år.

Mikkel Thorup, DIKU

"Vi udviklede en algoritme, der simultant er bedst på alle performance dimensioner," siger Jelani Nelson til Quanta Magazine.

Han er datalogiforsker på Harvard og er sammen med Kasper Green Larsen fra Aarhus Universitet, Mikkel Thorup fra Københavns Universitet og Huy Nguyen fra Northeastern University algoritmens ophavsmand.

Deler store problemer op i små data

For at forstå algoritmen, skal man forestille sig, at man skal finde frem til hyppige søgeord i en søgemaskine. De fleste streamingalgoritmer hidtil har enten skullet give afkald på hastighed til fordel for præcision eller omvendt ifølge Quanta Magazine.

Det er fordi, de har været afhængige af et stort indeks. Så i vores søgeords eksempel skulle alle ord i ordbogen tildeles en numerisk værdi og parres med en anden værdi, der tæller hvor mange gange, der er blevet søgt på ordet. Et stort problem i denne fremgangsmåde er, at det tager en computer alt for længe at loope igennem de hundrede tusinde ord, der er i en ordbog i real time. Og det er her forskerne har opnået et gennembrud.

De fandt nemlig en metode til at dele ordbogen op i mindre bidder, og en smart måde at sætte ordbogen sammen på igen. Den fulde, matematisk tunge, forklaring kan findes på Quanta Magazines hjemmeside, og holdets forskning kan læses her.

Artiklen er hentet fra Version 2 tirsdag den 31. oktober 2017.

Det anerkendte uafhængige forskningsmagasin Wired.com har desuden bragt sin egen version af artiklen: https://www.wired.com/story/big-data-streaming/