Dansker afslører Googles begrænsning

Ung dansk forsker 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, ph.d.-studerende ved grundforskningscentret MADALGO, Aarhus Universitet
Kasper Green Larsen, ph.d.-studerende ved grundforskningscentret MADALGO, Aarhus Universitet
I samarbejde medVidenskab.dk

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.

Det skriver Videnskab.dk

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, til Videnskab.dk.

Læs også på Videnskab.dk: Studerende knækker årtier gammelt matematisk problem

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.

Læs også på Videnskab.dk: Bjarne Stroustrup vil løse verdens praktiske problemer

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.

Se formlen og læs om, hvad den talentfulde forsker nu kaster sig over, på Videnskab.dk.

Mest læste

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å b.dk skal du tillade visning af annoncer på b.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 du sidder og læser. Vi vil derfor sætte stor pris på, at du tilføjer b.dk til din adblocker's "whiteliste".

Tak for din forståelse.