Du er logget ind

Din profil kan bruges på berlingske.dk, business.dk og bt.dk, der alle er en del af Berlingske Media. Du kan altid logge ud eller opdatere dine oplysninger ved at klikke på dit profilnavn.
Videnskab.dk

Opfindelse fra Danmark gør computere hurtigere

En prisvindende algoritme, der er skabt af en vietnamesisk forsker på IT-Universitetet i København, gør computere mere effektive til at foretage søgninger i store databaser.

I samarbejde medVidenskab.dk

Mens de fleste af os nok bare forventer, at vores computere fungerer af sig selv på magisk vis, når vi tænder dem, er der en særlig gruppe, der skal sørge for, at det rent faktisk sker: Datalogerne.

De står bare med en udfordring:

Mængden af data, der skabes og skal behandles, vokser hurtigere end computerkraften. Samtidig med at computere hele tiden bliver bedre, og den rå regnekraft større, bliver de altså (groft sagt) også langsommere og langsommere til at løse de opgaver, vi stiller dem - medmindre datalogi-forskerne opfinder nye algoritmer, der er hurtigere og bedre til at udnytte regnekraften end de gamle.

Her kommer den vietnamesiske datalogi-forsker Ninh Pham, der er postdoc på IT-Universitetet i København, med en prisvindende nyskabelse, skriver Videnskab.dk.

Han har netop forsvaret sin ph.d.-afhandling, der handler om algoritmer til at foretage 'similarity search', en søgemetode, der sammenligner datasæt – noget computere har afgørende brug for at kunne, for at finde ud af om to sæt data minder om hinanden eller ej.

Læs også hos Videnskab.dk: Se den boblende computer

»Problemet med 'similarity search' er på mange måder et helt centralt problem inden for datalogien. Hvis man bedre kan estimere, hvor ens to dokumenter er, kan man spare både meget tid og penge,« siger Ninh Pham.

Den ene af algoritmerne, som Ninh Pham har døbt 'Odd Sketch', vakte opmærksomhed tidligere på året, da Ninh Pham skrev en videnskabelig artikel om algoritmen sammen med den danske datalogi-professor Rasmus Pagh, også fra IT-Universitetet i København, og Harvard-professoren Michael Mitzenmacher.

»Vores algoritme er den hurtigste til at sammenligne dokumenter, hvis dokumenterne minder meget om hinanden, og den bruger mindre plads end den nuværende metode til at gøre det,« siger Ninh Pham.

Artiklen vandt 'best paper award' på den prestigefyldte WWW-konference i Seoul i april.

»Det er måske sådan noget, der sker én gang i en akademisk karriere,« siger Ninh Pham, »så selvfølgelig var det vigtigt for os. Det havde vi ikke regnet med.«

Læs også hos Videnskab.dk: Samtaler genskabt ud fra vibrationer i chipsposer og planter

Opgaven med at sammenligne sæt af data opstår næsten konstant for computere.

Når vi køber en bog på nettet, sammenligner netbutikken os med andre besøgende, for at finde de kunder der minder om os, så den kan anbefale os bøger, de også har købt.

Skal en underviser tjekke opgaver for plagiater, bliver opgaven sammenlignet med alle de opgaver, der er skrevet tidligere for at se, om dele af teksten er ens. Når vi søger på Google, sammenligner søgemaskinen vores søgeord med sin database.

»Sådan som mængden af data udvikler sig, skal Google indeksere milliarder af hjemmesider og får hver eneste måned milliarder af forespørgsler. Så spørgsmålet er, hvordan man kan nå at svare på forespørgslerne fra alle brugere,« siger Ninh Pham.

Når datamængderne er blevet så store og er stigende, er det nemlig ikke længere muligt for Google at sammenligne ens søgeord med alt, der nogensinde er lagt på nettet, eller for bognetbutikken at sammenligne den eksisterende kunde med alle tidligere kunder i databasen. Kunden ville være færdig med sit køb, og Google-søgeren ville have spurgt sin sidemand i stedet, før computeren var færdig med at finde svaret frem.

Læs også hos Videnskab.dk: Algoritmer er tikkende bombe under finansmarkedet

Derfor er forskerne nødt til at lave algoritmer, der kun søger i et udpluk af datahavet – samtidig med, at de skal være statistisk sikre på, at algoritmerne alligevel finder det, man leder efter.

»Fordi 'similarity search' er et så centralt problem, er der mange, der arbejder på at løse det. Hvis man forbedrer metoderne bare en lille smule, kan man spare mange ressourcer, når man skal bruge dem,« siger Ninh Pham.

Odd Sketch-metoden opstod i sammenarbejde mellem Ninh Pham og hans ph.d.-vejleder på IT-Universitetet i København, professor Rasmus Pagh. Sammen fik de algoritmen til at virke i praksis.

Men et udbredt problem blandt computerprogrammører i it-virksomhederne er, at de ikke har forskernes matematiske og statistiske beviser for, at en algoritme altid vil virke. Derfor benytter de sig ofte af algoritmer, der af og til fejler på kritiske tidspunkter.

Det teoretiske bevis var derfor vigtigt for Pham og Pagh, der kontaktede Harvard-datalogiprofessoren Michael Mitzenmacher.

»Han er verdenskendt inden for datalogien og arbejder meget tæt på vores felt, så vi involverede ham i at sikre, at algoritmen ikke kun virker godt i praksis, men at der også er teoretisk bevis for det,« fortæller Ninh Pham.

Læs om, hvordan Odd Sketch-algoritmen fungerer, i resten af artiklen på Videnskab.dk.

Vi kan se, at du har installeret en adblocker, så vi ikke kan vise dig annoncer.

Det er vi kede af, fordi indtægter fra annoncer er en helt afgørende årsag til, at vi dagligt kan tilbyde dig journalistik af høj kvalitet.

For få adgang til indhold på Berlingske.dk skal du tillade visning af annoncer på Berlingske.dk. Se hvordan du gør her..

Tak for din forståelse.

Hov! Hvor blev min artikel af..!?

Du er træt af reklamer. Vi ved det godt! Men de betaler for den artikel, du sidder og læser. Vi vil derfor sætte stor pris på, at du tilføjer Berlingske.dk til din adblocker's "whiteliste".

Tak for din forståelse.