Annonceinfo

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.

Tak for dit svar

Der er masser af dybde og viser, at du er en værdig modtager af prisen :-)

Kommer formlen bag på nogen?

Hej Carsten

Tak for dit spørgsmål vedr. resultatet. Vil meget gerne gå mere i detaljer om det.

Først vil jeg lige nævne at jeg synes det ville være ret sørgeligt for teoretisk datalogi hvis et resultat der viser at man skal lave to binære søgninger hvis man skal søge på 2 uafhængige kriterier ville få en pris som et af årets bedste resultater. Så heldigvis er det heller ikke det min formel siger. At lave 2 binære søgninger tager 2 * log(x) tid og ikke log(x)^2 = log(x)*log(x) tid, det er altså to helt forskellige formler. For 1 mia eksemplet er 2 * log(x) = 60.

For at få lidt intuition om hvad log(x)^2 er, så tænk på at lave en binær søgning, men hver gang man halverer størrelsen af den man ser på, er man nødt til at udføre en helt ny binær søgning i en anden mængde. Altså, for hvert af de log(x) halveringsskridt der er i en binær søgning, er du nødt til at lave en ny søgning i en anden liste som koster dig log(x) tid. I alt log(x)*log(x) tid.

Dog vil jeg stadig mene at hvis mit resultat var at man skal bruge log(x)^2 tid når man laver sammenligningsbaseret søgning, så ville det stadig være et ret sølle resultat.

Herfra vil mit svar nok kræve at man, som dig, har en programmeringsbaggrund. Artiklen ovenfor er jo selvfølgeligt skrevet så den er interessant for så mange mennesker som muligt. Det er jo altid en afvejelse af hvor mange detaljer man vil have med og hvor bredt et publikum der bliver fanget af historien.

Så for at starte, så kan computere jo heldigvis en del mere end at sammenligne tal. Faktisk har man vidst siden 70'erne at binær søgning IKKE er den hurtigste løsning når man ved at man søger iblandt heltal. Faktisk kan man søge i log(log(x)) tid i dette tilfælde. Denne løsning udnytter selvfølgeligt at det man søger efter er heltal. Et andet eksempel er hvis man blot vil afgøre om et bestemt element er i ens database. Sammenligningsbaseret skal man bruge mindst log(x) tid, men hvis man udnytter at det er heltal kan hashing gøre det med blot 2 opslag i databasen. Så hvis man udnytter alt hvad en computer kan, kan man typisk gøre tingene meget, meget hurtigere end sammenligningsbaseret. De store internet routere benytter faktisk sådanne tricks når de skal sende data pakker videre ud fra IP addresser.

Den formel jeg har vist gælder uanset hvilke instruktioner computeren kan lave, og afhænger på ingen måde af krav som at man skal lave sammenligningsbaserede søgninger. Om formlen så er overraskende er en anden ting. Den passer jo med de hurtigste løsninger der er, så man havde måske gættet på at det var sådan formlen skulle være. Problemet har været at bevise det. Rent faktisk er det ikke så meget det at formlen er den endelige løsning til problemet med at søge på 2 kriterier der har givet prisen. Det er blot den del af resultat som lyder vigtigst for folk udenfor feltet. Den største årsag til at artiklen fik prisen er at den nedregrænse på log(x)^2 er den højeste nedregrænse der nogensinde er vist, for et hvilketsomhelst database problem. Med højeste mener jeg her at formlen er den hurtigst voksende formel der er bevist. Alle tidligere teknikker til at vise nedregrænser ville aldrig kunne vise en formel der vokser hurtigere end log(x).

Mht. bil eksemplet er jeg nu ikke enig i at det er et dårligt eksempel. Det er klart at man kan lave praktiske optimeringer der udnytter at der er en sammenhæng imellem pris og alder. Husk igen at eksemplet jo er tænkt sådan at folk uden for datalogi bedst muligt kan relatere sig til hvad der er vi laver. En anden ting er at virksomheder som bilbasen formodentligt ikke har programmeret deres eget databasesystem der rent faktisk udnytter denne sammenhæng. Uden at vide det, går jeg ud fra at de bruger standard systemer som MySQL, Oracle eller Microsoft Access. De finder formodentligt frem til de biler man søger på ved at lave standard SQL queries. Selvfølgelig kan disse systemer selv forsøge at opdage sammenhænge, men der er en anden historie.

Pointen med cache-optimering er rigtig god. Min formel viser kun hvor mange gange man skal slå op i sit system. Tiden det tager at lave et opslag afhænger så af om man laver et cache-miss eller ej. Rent faktisk er formlen mere generel end der vises ovenfor, og fortæller f.eks. også at hvis man ser på antal cache-misses når ens cache kan gemme B bytes, så skal man lave mindst (log(x)/log(B))^2 cache-misses. Dette er præcist det antal cache-misses man får ved at kombinere eksisterende løsninger med blocking idéen som du refererer til. Hvis du er interesseret i sådanne optimeringer tror jeg du vil finde flg. link interessant:

http://www.madalgo.au.dk

MADALGO - Center for Massive Data Algorithmics, er det grundforskningscenter jeg er ph.d. studerende ved. Hovedformålet med centret er at finde algoritmiske løsninger til håndtering af kæmpe store datamængder. Dette handler om at blocke ting rigtigt så du ikke får for mange tilgange til harddisken. Det hele kan oversættes til hvad der foregår imellem cache og RAM.

Jeg håber du føler at ovenstående giver svar på dine spørgsmål og jeg håber ikke du sidder med en følelse af at det er noget helt trivielt der bliver lavet indenfor teoretisk datalogi. Det ville være synd, da jeg synes der bliver lavet utroligt meget spændende og vigtig forskning i vores felt. Du må endeligt gerne også se på linket til min artikel hvis du vil have et indblik i hvordan en sådan nedregrænse vises.

Mvh
Kasper

Kommer formlen bag på nogen?

Hej Kasper!

Så vidt jeg kan se, så er der tale om 2 gange binær søgning. 2^30 = 1 mia. og 30*30 = 900.

Er det ikke naturligt, at binær søgning er bedst, når der ingen forhåndsviden er til stede og der er tale om en sorteret blank database uden forespørgselshistorik.

Det er et dårligt eksempel med årgang og pris, da der der ikke er tale om uafhængige variable. Hvis bilen skal koste 50.000, så ved et menneske, at den enten er gammel eller trafikskadet. Jeg kan se, at du har skrevet om "orthogonal range reporting", så det må underforstået, at søgevariablerne er uafhængige.

Poul-Henning Kamp har f.eks. redegjort for praktisk optimering - se f.eks:
http://www.youtube.com/watch?v=37JNC-TKAis

Her er det vigtigt at cache data tæt på processoren og cache de mest hyppige forespørgsler.

I min praktiske verden er worst-case, at der skal indsættes et backup-bånd for at besvare en forespørgsel.

re: Sandsynlighed og udfaldsrum(meilghed... )

Tak Kasper, dit svar er så tilpas upræcist at jeg kan se værdien. 

Min interesse forgrener sig ud i fritekst søgning - hvor man fx kunne se på sandsynligheder for at en (oversat) tekst ville ramme målgruppens ”lix tal” - eller det der er værre! En seriøs translatør ville nok gå grædende hjem efter at have læst dette – men jeg mener seriøst at der er store muligheder i, at kunne være upræcis i sine oversættelser….. fx inspireret af hardcore forskning som din, og den der foregår inden for sprogforskningen - fx: http://www.amazon.co.uk/Linguistic-Supertypes-Cognitive-Semiotic-Communi... – sammenkobler man denne forskning med flere andre, er der nogle indlysende perspektiver, som ikke lige springer i øjnene hvis man er alt for præcis….

Vi er jo alle selv udstyret med en supercomputer – hjernen – som må være er underlagt de (samme?) fysiske søgegrænser. Inden for kognitions forskningen vil man helt sikkert kunne genfinde de grænser som du kommer frem til – om svaret er ”21” eller ”42”, det skal der måske regnes lidt mere på. Men det vi taler om er at der er en øvre grænse for hvor stor ”kapacitet” vi overhovedet ’har’ brug for… altså svarende til en grænse for hvilken ”videns vækst” vi hver i sær kan administrere på ’intelligent’ vis…. (Hvis ikke jeg tager helt fejl relatere dette sig altså til debatten om hvad intelligens ”er”; hvor jeg hælder til at spørge hvad er det intelligens kan.)

For at lukke denne cirkel - ville det altså give mening hvis en søgning ikke alene opfyldt mit oprindelige søgekriterier – men også at resultatet gav mig ’mere’ nemlig noget i retning af en intelligent udfordring… …

Hvad det betyder er slet ikke så kryptisk som det måske lyder - men det vil jeg tillade mig at tage med dig pr. mail.

Sandsynlighed og udfaldsrum(meilghed... )

Hej Per

Jeg håber jeg har forstået dine kommentarer rigtigt, så sig lige til hvis det ser ud som om jeg misforstår noget.

Du har helt ret i at den grænse jeg viser handler om det tilfælde hvor det er krævet at man finder præcist de ting der opfylder søgekriterierne. Det er derfor naturligt, som du siger, at se på hvor effektivt man kan søge hvis man tillader små fejl (approksimationer). Der er faktisk rigtigt meget forskning der omhandler at finde sådanne løsninger, og for mange naturlige søgeproblemer, inklusivt ovenstående, kan det faktisk godt lade sig gøre at lave hurtigere søgeprogrammer hvis man tillader fejl.

På den måde kan mit resultat også bruges til at sige at hvis vi ønsker hurtigere søgninger er vi simpelthen nødt til at ofre noget af korrektheden - der er ingen vej udenom dette.

Et andet spørgsmål er så hvad det bedst mulige er for søgninger med fejl. Her kan man igen forsøge at vise en "nedregrænse" for hvor effektivt man kan søge, hvis man sætter specifikke krav til hvor forkert svaret kan være. Det er bestemt et spørgsmål jeg vil bruge noget af min tid på at forsøge at finde svar på.

Mvh
Kasper

Sandsynlighed og udfaldsrum(meilghed... )

Tillykke – jeg er ikke selv nogen matematik ørn, men interesserer mig mere for sandsynligheder…. hvor min matematiske forståelse også begrænser sig en del …. MEN selv en blind høne kan finde korn.. ;-)

For mig at se må dine beregninger i det perspektiv omhandle ”hårde data” - hvor vi faktisk kan beskrive det vi ønsker at finde på en stringente måde. Altså forstået sådan at ’hvis det vi leder efter er der – så finder vi det også – inden for din ramme’… og den er er jo vældig interessant i et lukket data system…. (arbejder selv for Banker på IBM maskiner, hvor dette har stor betydning.)

Man kunne jo så ”stramme op”, ved at eliminere sandsynligheden for fejl - eller – dette er min ide/hypotese - man kan ”lukke op” og se på afgræsningerne for din søgning og vurdere ’sandsynligheden’ for at et mere upræcist resultat vil være af værdi for den der søger…

Altså ville jeg - der gerne vil se liste over biler, der er produceret efter 2006, og som koster under 100.000 kr. - sandsynligvis også være interesseret hvis de koster 107.000… og efter 2004 …. fx når antal af resultater er < 5 stk.

En anden mulighed er at det jeg faktisk søger efter er ”noget andet” som har de samme attributter, som jeg søger efter – altså at jeg også vil være interesseret i produkter/ting som koster omkring 100K, er ca. 8 år gamle, har fire hjul osv. osv. osv.

Min pointe er dog – og her er det at dine algoritmer igen bliver interessant - at noget sådant vil kræve to ting: A) at ”præindekseringen” af data må optimeres med henblik på dette. B) at selve søge kriteriet må kunne optimeres i forholdet til præindekseringen og det den ønskede præcision….

Vh Per

Tids Kompleksitet

Hej Jakob

Jeg går ud fra du mente "Hej Kasper". Det er egentligt to helt forskellige ting. Lad mig prøve at forklare forskellen:

En tids kompleksitets analyse er en analyse af hvor effektiv et/en konkret program/algoritme er. Dvs. når man har fundet på et nyt søgeprogram kan man analysere hvor effektivt dette program er.

En "nedregrænse" er et bevis for at ALLE søgeprogrammer i verden, selv dem der ikke engang er opfundet endnu(!), skal bruge mindst f(x) beregninger, hvor f(x) er den formel man når frem til.

En tids kompleksitets analyse handler altså om en bestemt løsning som man kan sætte sig ned og kigge på, hvor en nedregrænse på samme tid handler om alle tænkelige (og utænkelige) løsninger. Jeg håber det herudfra giver mening at det er noget helt andet, og væsentligt vanskelligere at vise en nedregrænse end det er at analysere en konkret løsning.

Sig endeligt til hvis ovenstående ikke er helt klart.

Mvh
Kasper

Tids Kompleksitet

Hej Kasper

Hvordan adskiller din formel sig fra en basal tids kompleksitets analyse?

http://en.wikipedia.org/wiki/Time_complexity

Mvh
Jakob

Re: Underlig formel

hej Søren,

mon ikke det er 2-tals logaritmen, svarende til antallet af binære cifre, der skal bruges? 2^30 ~ 10^9.

mvh Rasmus Møller

Underlig formel

Hej Søren

Tak for din interesse i mit resultat. Grunden til du får andre tal er at vi indenfor datalogi regner med 2-tals logaritmen (hvilket også er hvad formlen ovenfor hentyder til). Grunden hertil er vi typisk deler tingene over i 2 lige store halvdele og derefter kun kigger på den ene. Sådanne halveringer kan gøres 2-tals logaritmen gange før vi kun har et element tilbage. Da 2^10 = 1024 som ca er 10^3, bliver 2-tals logaritmen til 1 mia (10^9) til 30, og så når vi 30^2=900. Håber dette giver mening.

Mange hilsner
Kasper Green Larsen

Underlig formel

Det ser da underligt ud.
Når jeg udregner
(log(1000000000))^2
så får jeg det da til
9^2=81

Mon ikke der skal rettes lidt på formlen?

Søren Toft
Matematiklærer

Seneste fra Teknologi

Deltag i Unge Forskere 2015

Annonceinfo

Det læser andre lige nu

Annonceinfo

Annonceinfo

Abonner på vores nyhedsbrev

Når du tilmelder dig, deltager du i konkurrencen om lækre præmier.

Mest sete video

Annonceinfo

Seneste kommentarer

Seneste blogindlæg