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 Fold sammen
Læs mere
Foto: Kasper Green Larsen / Videnskab.dk
Lyt til artiklen

Vil du lytte videre?

Få et Digital Plus-abonnement og lyt videre med det samme.

Skift abonnement

Med Digital Plus kan du lytte til artikler. Du får adgang med det samme.

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.