Så effektive kan søgemaskiner blive

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.

»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

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.