dc.date.accessioned |
2011-08-23T13:08:52Z |
und |
dc.date.accessioned |
2017-11-06T11:14:52Z |
|
dc.date.available |
2011-08-23 |
fi |
dc.date.available |
2011-08-23T13:08:52Z |
und |
dc.date.available |
2017-11-06T11:14:52Z |
|
dc.date.issued |
2011-08-15 |
|
dc.identifier.uri |
http://hdl.handle.net/10138/27439 |
|
dc.publisher |
Helsingin yliopisto |
fi |
dc.publisher |
Helsingfors universitet |
sv |
dc.publisher |
University of Helsinki |
en |
dc.title |
Hakupuut muistihierarkiassa |
fi |
ethesis.department.URI |
http://data.hulib.helsinki.fi/id/225405e8-3362-4197-a7fd-6e7b79e52d14 |
|
ethesis.department |
Institutionen för datavetenskap |
sv |
ethesis.department |
Department of Computer Science |
en |
ethesis.department |
Tietojenkäsittelytieteen laitos |
fi |
ethesis.faculty |
Matematisk-naturvetenskapliga fakulteten |
sv |
ethesis.faculty |
Matemaattis-luonnontieteellinen tiedekunta |
fi |
ethesis.faculty |
Faculty of Science |
en |
ethesis.faculty.URI |
http://data.hulib.helsinki.fi/id/8d59209f-6614-4edd-9744-1ebdaf1d13ca |
|
ethesis.university.URI |
http://data.hulib.helsinki.fi/id/50ae46d8-7ba9-4821-877c-c994c78b0d97 |
|
ethesis.university |
Helsingfors universitet |
sv |
ethesis.university |
University of Helsinki |
en |
ethesis.university |
Helsingin yliopisto |
fi |
dct.creator |
Koskinen, Paavo |
|
dct.issued |
2011 |
|
dct.language.ISO639-2 |
fin |
|
dct.abstract |
Algoritmien suoritusajasta kuluu usein merkittävä osa datan siirtelyyn muistihierarkian kerrosten välillä. Ongelma korostuu hakurakenteilla, sillä ne käsittelevät suuria datamääriä. Työn päämääränä on selvittää muistisiirtojen minimoinnilla saavutettavat käytännön edut hakupuiden tapauksessa. Toinen päämäärä on kartoittaa ideaalisen välimuistin malliin perustuvien parametrittomien hakupuiden etuja ja heikkouksia ulkoisen muistin malliin perustuviin parametrillisiin hakupuihin nähden. Parametrittomuus tarkoittaa, ettei algoritmi tiedä käytetyn suunnittelumallin parametreja, kuten välimuistin kokoa. Staattisista hakupuista tarkastellaan leveyssuuntaiseen järjestykseen, esijärjestykseen ja van Emde Boas -järjestykseen tallennettuja binäärihakupuita sekä staattista B-puuta. Dynaamisista hakupuista käsitellään B+-puuta sekä parametritonta B-puuta, COB-puuta. Sekä parametrittomat että parametrilliset hakupuut pyrkivät minimoimaan vaadittavaa muistisiirtojen määrää parantamalla laskennan paikallisuutta. Käsiteltävien hakupuiden käytännön nopeutta testataan monipuolisesti. Saatujen tulosten nojalla sekä staattiset että dynaamiset parametrittomat hakupuut pärjäävät satunnaisoperaatioiden nopeudessa vastaaville parametrillisille hakupuille. Ne jäävät kuitenkin jonkin verran jälkeen perättäisoperaatioita suoritettaessa. |
fi |
dct.language |
fi |
|
ethesis.language.URI |
http://data.hulib.helsinki.fi/id/languages/fin |
|
ethesis.language |
Finnish |
en |
ethesis.language |
suomi |
fi |
ethesis.language |
finska |
sv |
ethesis.supervisor |
Kärkkäinen, Juha |
|
ethesis.supervisor |
Mäkinen, Veli |
|
ethesis.thesistype |
pro gradu-avhandlingar |
sv |
ethesis.thesistype |
pro gradu -tutkielmat |
fi |
ethesis.thesistype |
master's thesis |
en |
ethesis.thesistype.URI |
http://data.hulib.helsinki.fi/id/thesistypes/mastersthesis |
|
dct.identifier.urn |
URN:NBN:fi-fe201108232274 |
|
dc.type.dcmitype |
Text |
|
dct.rights |
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited. |
en |
dct.rights |
Publikationen är skyddad av upphovsrätten. Den får läsas och skrivas ut för personligt bruk. Användning i kommersiellt syfte är förbjuden. |
sv |
dct.rights |
Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty. |
fi |