Rasmus Pagh var 9–10 år gammel da problemet med å søke første gang åpenbarte seg for ham. Gutten, som senere skulle bli professor ved IT-universitetet i København, hadde akkurat fått sin første datamaskin, med 48 KB ram. Bøker om programmering lånte han på biblioteket.

Han hadde et puslespill som han tenkte at datamaskinen kunne løse. Han skrev et program som gikk igjennom alle muligheter for hvordan brikkene kunne ligge.

– Programmet kjørte og kjørte, men ble aldri ferdig, forteller Pagh,

Han kaller episoden en «aha-opplevelse»: Den enorme mengden av mulige kombinasjoner viste ham at søk der man går gjennom alle dataene, blir altfor tunge. Det fikk ham til å tenke på smartere måter å gjøre det på.

Alternativet til å gjennomgå alle dataene er i dag ofte å bruke tilfeldige stikkprøver. De søkemetodene vi finner på Google, Facebook, i forsikringsselskapenes databaser og i bedriftenes markedsavdelinger, fungerer ikke så godt som mange tror. Det er nemlig ingen garantier for at man finner alt det man leter etter.

Det skal Pagh nå forsøke å gjøre noe med. Han forsker på såkalt Big data – de enorme datamengdene som forskere, bedrifter og myndigheter har samlet opp de siste årene – og de matematiske algoritmene man bruker til å søke gjennom dem.

Bedre metoder for «myke søk»

Han ble i januar tildelt et «Consolidator Grant» fra Det europeiske forskningsrådet. Pengene, 1,9 millioner euro, skal finansiere forskningen hans de neste fem årene.

– Vi tar en sjanse, for vi forsøker å gjøre noe en del andre smarte mennesker har prøvd før. Men vi tror vi har de ekstra ledetrådene som trengs, sier Pagh.

Prosjektet går ut på å finne nye og bedre metoder til såkalte myke søk, også kalt «similarity search». Altså når man står med én ting og gjerne vil finne noe som ligner.

Samtidig vil Pagh undersøke matematisk om de metodene som mange søkemotorer bruker i praksis, virker. Disse metodene er bygget på tommelfingerregler og ad hoc-løsninger, men er uten teoretisk grunnlag. Paghs teori er at de ikke alltid virker skikkelig.

Søk uten garantier

Et mykt søk kan for eksempel ta utgangspunkt i et bilde, forklarer Pagh. Man har et bilde av en løve og vil finne andre bilder som ligner, men uten å vite om fotosamlingen inneholder andre løver, andre kattedyr eller kanskje et løvemaleri.

Det er slett ikke sikkert man finner alle bilder som ligner, for metodene man bruker i dag, er basert på stikkprøver, hvor man ikke kjenner kvaliteten på svarene. Skal man ha sikre svar, krever det veldig store dataressurser.

– En løve er ikke det mest kritiske eksempelet. Det kan være en lege som søker på sykdomshistorier, og han går glipp av en behandling som reddet en pasient et annet sted. Det er ingen som vet hvordan dette gjøres på best mulig måte, sier Pagh.

Sannsynlig å være uheldig

Datamaskinen betrakter løvebildet som elektroniske 1-tall og 0-tall. Man tar en stikkprøve av forskjellige parametere: Er det en hatt? Nei. Er det et dyr? Ja.

Deretter finner datamaskinen andre bilder hvor man kan svare ja og nei på de samme spørsmålene. Men hvilke parametere man undersøker, er tilfeldig utvalgt, og det er derfor tilfeldig om datamaskinen leter etter andre bilder med dyr eller andre bilder uten hatter.

– Hvis man er heldig, blir de riktige parametrene. Men det er rimelig stor sannsynlighet for å være uheldig. Så gjentar man det noen hundre ganger med tilfeldige stikkprøver, og da er det rimelig stor sannsynlighet for å være heldig, sier Pagh.

– Det er de beste algoritmene som finnes i dag – og de er litt bedre enn å se gjennom alt, sier han.

Vanskeligere å bruke gode metoder

Men ettersom den metoden – locality sensitive hashing – også krever store dataressurser, bruker man ofte metoder hvor man ikke matematisk kjenner kvaliteten på søkeresultatet.

Og det vil i fremtiden bli vanskeligere og vanskeligere å bruke de gode metodene. Mengden av data eksploderer – annethvert år fordobles den, ifølge analyseinstituttet IDC. Selv om datakraften også vokser, er det ikke mulig å holde tritt.

– En del av motivasjonen for forskningsprosjektet er at man fortsatt skal kunne bruke myke søk i fremtiden. Det andre er å beskrive de nåværende systemene, som er basert på noen tommelfingerregler som ofte virker. Men noen ganger virker de ikke, og det er ikke alltid helt klart hvorfor, sier Pagh.

Søkemotorenes forbannelse

Det er ingen garanti for at Pagh og teamet hans vil lykkes.

– Man snakker om «the Curse of Dimensionality» – altså forbannelsen ved mange dimensjoner. Det er litt Indiana Jones over prosjektet. Vi skal forsøke å heve denne forbannelsen, men det er ikke sikkert det er mulig, sier Pagh.

Forskerne vil studere måter å organisere datanettverk som kommuniserer med hverandre om søket. De vil forsøke å bygge videre på en teori fra Stanford-forskeren Gregory Valiant, som er basert på å lete etter noe annet enn det man leter etter.

Harvard-professor: Forskningen er viktig

Michael Mitzenmacher er professor i informatikk ved Harvard University og forsker på algoritmer. I en e-post skriver han at Rasmus Pagh en «verdenskjent leder innen algoritmiske metoder til datauttrekning».

«Når vi øker antallet områder hvor vi vil ha myke søk til å fungere, er flere teknikker, analyser og bedre forståelse nødvendig. Dette forskningsprosjektet kan føre til bedre og mer kraftfulle metoder», skriver Mitzenmacher.

Også Gerth Stølting Brodal, førsteamanuensis ved Institut for Datalogi ved Aarhus Universitet, mener fremskritt på området er viktige. Han sier at søk med mange parametere – altså mange dimensjoner – er notorisk vanskelig.

– For tiden har vi noen metoder som virker i praksis, men vi har ikke bevis for hvorfor de virker. Det er viktig matematisk å finne ut hvorfor, sier han. Også Brodal påpeker at det er en stor utfordring.

– Han vil finne nye metoder, og det er et veldig ambisiøst mål. Ingen vet om det lykkes. Slik er det med grunnforskning, avslutter Brodal.

Referanse:

Georgi Valiant:Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem,Foundations of Computer Science, Stanford University (2013), DOI: 10.1109/FOCS.2012.27.

© Videnskab.dk. Oversatt av Lars Nygaard for forskning.no.