Persbericht Centrum Wiskunde & Informatica
Amsterdam, 23 juni 2010
Nieuwe techniek database cracking versnelt zoekproces in grote databestanden
Digitale bestanden van bedrijven en organisaties worden steeds
omvangrijker. Ook in de wetenschap komen steeds grotere hoeveelheden
data beschikbaar uit bijvoorbeeld sterrenkundige waarnemingen en
DNA-analyses. Om in deze steeds groter wordende datasets de juiste
informatie te vinden zijn nieuwe eisen aan databasetechnologieën nodig.
In zijn proefschrift 'Database Cracking: Towards Auto-tuning Database
Kernels' ontwikkelde onderzoeker Stratos Idreos van het Centrum Wiskunde &
Informatica (CWI) in Amsterdam, een nieuwe techniek waarmee het
zoekproces kan worden versneld.
Of we nu online onze bankzaken regelen, een vliegticket boeken of een
digitaal bestand van de overheid raadplegen, dagelijks maken we op grote
schaal gebruik van databasetechnologie. Om de meest optimale manier te
vinden om een zoekopdracht uit te voeren worden index-structuren
gebruikt. Van te voren wordt hierin een zoekindex opgezet en vastgelegd
waar mensen naar zoeken. Het nadeel van index-structuren is dat het
aanmaken en onderhouden veel tijd en ruimte van de beheerder in beslag
nemen en daarmee een kostbaar proces zijn geworden. De door Idreos
ontwikkelde techniek, database cracking, is de eerste techniek waarbij
het databasesysteem de rol van de beheerder overneemt en zelf over een
aanpassend vermogen beschikt. Idreos verdedigt zijn proefschrift 24 juni
aan de Universiteit van Amsterdam.
Bij database cracking wordt niet alles vooraf precies geïndexeerd. Bij
elke nieuwe zoekopdracht wordt de data hergesorteerd. Het systeem
schrijft de data in een nieuwe volgorde terug waardoor automatisch een
steeds betere sortering ontstaat en bij elke volgende opdracht sneller
een antwoord wordt gevonden. Omdat vooraf geen zoekindex wordt
ontwikkeld bespaart de nieuwe techniek veel tijd en kosten. Idreos
licht het principe toe aan de hand van een stapel ongeordende
speelkaarten: "Als een gebruiker vraagt naar een harten twee, kan het
systeem ook wel meteen alle harten die het onderweg tegenkomt op een
stapel met alleen harten leggen en alle niet-harten op een tweede
stapel. Bij een volgende vraag naar alle klaveren weet het syteem dat
het alleen hoeft te zoeken in de stapel niet-harten."
De database cracking methode is door de onderzoeksgroep Database
Architectures van het CWI toegepast op de Sloan Digital Sky Server, de
grootste wetenschappelijke database ter wereld die ruim drie terabyte
aan gegevens over waargenomen sterren bevat. In deze database kon met de
cracking techniek het zoekproces met factor tien tot twintig worden
versneld. Het platform voor de Sloan Digital Sky Server is gerealiseerd
met het door het CWI ontwikkelde open-source database systeem MonetDB
dat wereldwijd wordt gebruikt.
Over CWI:
Het Centrum Wiskunde & Informatica (CWI) is sinds 1946 het nationale
onderzoeksinstituut voor wiskunde en informatica. Het is gevestigd op
het Science Park Amsterdam en is deel van de Nederlandse Organisatie
voor Wetenschappelijk Onderzoek (NWO). Het instituut heeft een sterke
internationale positie. Ruim 160 wetenschappers doen er grensverleggend
onderzoek in ongeveer 70 projecten, en dragen de verkregen kennis over
aan de maatschappij. Ongeveer 30 van de onderzoekers zijn hoogleraar aan
een universiteit. Uit het instituut komen circa twintig spin-off
bedrijven voort.
Noot voor redacties
(
Centrum voor Wiskunde en Informatica