Så effektive kan søgemaskiner blive
Dansker har fundet svaret på, hvor effektiv en søgning i en database kan blive. Det har ført til fornemme priser i teoretisk datalogi.

Kasper Green Larsen har fundet svaret på, hvor effektiv en database teoretisk set kan blive. Det har ført til priser og international opmærksomhed på det unge forskningstalent. (Foto: Kasper Green Larsen)

Behovet for at søge og sortere i enorme datamængder vokser eksplosivt i den digitale tidsalder. Og effektive søgemetoder bliver mere og mere vigtige for at analysere og finde frem til de rigtige informationer så hurtigt som muligt.

Men hvor hurtig og effektiv kan en søgning i en database egentlig blive? Det spørgsmål har siden 1970’erne fået dataloger til at rive hår ud af hovedet, men nu har den 26-årige ph.d-studerende Kasper Green Larsen fundet svaret: 

»Kort forklaret, har jeg udviklet et matematisk værktøj, der kan måle, hvor mange gange en computer skal slå op i en database, før søgeprogrammet ikke længere kan forbedres.«

»Hvis en database er lige så effektiv som min formel, siger den kan være, er ingen database i hele verden i stand til at løse opgaven mere effektiv – heller ikke databaser, der ikke engang er udviklet endnu,« siger Kasper Green Larsen, ph.d.-studerende ved grundforskningscentret MADALGO, Aarhus Universitet.

Svaret er rundt regnet 900

I teoretisk datalogi har man de sidste årtier spekuleret i, at der må findes en nedre grænse for, hvor mange gange et system skal slå op i en database for at finde de relevante oplysninger, som eftersøges.

Det er denne teoretisk nedre grænse, den ph.d.-studerende har fundet et helt konkret svar på:

»Hvis man gemmer 1 mia. informationer i sin database – hvilket ikke er usædvanligt – så kan min formel bevise, at ethvert databasesystem skal bruge mindst 900 søgninger for at løse en søgning med to kriterier,« forklarer Kasper Green Larsen.

Hvis du er på udkig efter en bil, kan et konkret eksempel være, at du gerne vil se liste over biler, der er produceret efter 2006, og som koster under 100.000 kr,

Den nedre grænse er med andre ord en slags facitliste, der viser, hvor effektiv et søgeprogram teoretisk set kan blive.

Fakta

Kasper Green Larsens formel ser ganske simpel ud: (log(x))^2 (læses logaritmen til x, i anden). Det vil sige, at hvis man gemmer 1 mia. elementer i sin database (x=1.000.000.000), giver (log(x))^2 cirka 900. Formelen beviser, at ethvert databasesystem skal slå op mindst 900 gange, når det skal søge iblandt 1 mia. elementer.

»Metoden kan bruges som en slags facitliste for programmører, der hurtigt vil tjekke om deres søgeprogram kan forbedres eller ej.«

»Bruger en database omkring samme antal søgninger som min formel foreskriver, er det spildte kræfter at forsøge at optimere søgeprogrammet,« siger Kasper Green Larsen.

Prisregn over ung forsker

Kasper Green Larsens matematiske evner og arbejde med strukturering af databaser har nærmest fået det til at regne med priser ned over forskningstalentet.

Han kunne rejse hjem fra New York med to priser i favnen, sidst toppen af poppen inden for teoretisk datalogi var samlet til ’ACM Symposium on Theory of Computing’, også kaldet ’STOC’.

Ved konferencen, der er en af de mest ansete inden for teoretisk datalogi, uddeles feltets svar på filmverdenens Oscar.

Desuden høstede forskerspiren for nyligt hæder i form af en pris ved søsterkonferencen til STOC ’Symposium on Foundations of Computer Science’ eller bare ’FOCS’.

Matematisk metode kan indirekte føre til bedre databaser

Den ph.d.-studerendes matematiske værktøj kan umiddelbart lyde abstrakt. Men den nye viden om databaser betyder, at programmører nu kan fokusere kræfterne på ting, der rent faktisk kan forbedres.

»Uanset hvor dygtige programmører Google eller Microsoft hyrer, kan søgeprogrammer ikke blive bedre til denne type søgning.«

»Det betyder, at man i stedet kan bruge ressourcerne på andre områder i datastrukturering, og dermed udvikle bedre databaser,« siger Kasper Green Larsen.

Finpudsning og tilbage til udgangspunktet

Fakta

Kasper Green Larsens artikel ‘The Cell Probe Complexity of Dynamic Range Counting’ vandt STOC Best Student Paper Award (The Danny Lewin Award), STOC Best Paper Award. Desuden har han vundet FOCS Best Student Paper Award (The Machtey Award) for artiklen 'On Range Searching in the Group Model and Combinatorial Discrepancy'.

Forskerspiren ser det matematiske værktøj som et stort skridt på vejen til bedre databaser. Han påpeger dog, at der stadig findes masser af udfordringer inden for datastrukturering.

»Vi kender ikke det optimale svar på søgninger med 3 kriterier, eller den optimale metode til at finde den korteste vej mellem byer.«

»Der er så mange problemer, som hele tiden bliver løst i vores computere – så der er nok at kaste sig over,« siger Kasper Green Larsen.

Den p.hd.-studerende har flere bolde i luften med henblik på fremtiden. Noget af tiden skal han bruge på finpudsning af sin matematiske metode. Han vil dog også gerne tilbage til udgangspunktet for sin ph.d.

»Jeg startede egentlig med at skulle finde frem til nye søgeprogrammer, der er hurtigere end det, vi har haft, og det skal jeg helt klart tilbage og kigge på,« siger Kasper Green Larsen.

Kaster sig over streaming

På det seneste er Kasper Green Larsen begyndt at interesse sig for et nyt forskningsfelt. Han arbejder her på at finde metoder til at effektivisere de enorme datamænger, der flyttes rundt på nettet via streaming.

»Inden for streaming taler man ligeledes om, at der må være en nedre grænse for, hvor meget tid computeren skal bruge på at lave forskellige statistiske beregninger.«

»Jeg håber vores matematiske værktøjer fra datastrukturering kan overføres til streaming og hjælpe til med at øge vores forståelse for det område,« siger Kasper Green Larsen.

Forhåbentligt kommer det til at betyde, at det i fremtiden hakker knap så meget, når vi streamer video over internettet.

Talent tidligt bemærket

Det er ikke første gang Kasper Green Larsen gør sig bemærket for sit talent. I 2010 blev han den første dansker, som modtog Google European Fellowship-prisen.

Prisen forsødede ph.d.-studiet med 1,1 mio. kr., hvilket gav muligheden for at rejse til masser af konferencer og opbygge et netværk blandt de førende forskere inden for strukturering af databaser.

I 2011 modtog han endnu engang en pris. Her blev han belønnet med videnskabsministerens Eliteforsk-rejsestipendie. Det brugte Kasper Green Larsen til et seks måneders studieophold i USA, nærmere bestemt på det prestigefyldte Princeton University i New Jersey.

»Jeg valgte Princeton netop fordi, de har en af verdens stærkeste forskningsgrupper inden for datastrukturer og teoretisk datalogi i det hele taget,« siger Kasper Green Larsen.

Den ph.d.-studerende fortæller, at han specielt var vild efter at arbejde sammen med de to professorer Bernard Chazelle og Robert Tarjan.

»Bernard Chazelle udviklede i 70'erne og 80'erne mange af de søgeprogrammer, som jeg i dag har bevist er optimale. Og Robert Tarjan ses i manges øjne som verdens førende forsker i datastrukturer, hvilket har givet ham datalogiens svar på nobelprisen – Turing prisen,« siger Kasper Green Larsen.