Hakupuut muistihierarkiassa

Show simple item record

dc.contributor Helsingin yliopisto, Matemaattis-luonnontieteellinen tiedekunta, Tietojenkäsittelytieteen laitos fi
dc.contributor University of Helsinki, Faculty of Science, Department of Computer Science en
dc.contributor Helsingfors universitet, Matematisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap sv
dc.contributor.author Koskinen, Paavo
dc.date.issued 2011
dc.identifier.uri URN:NBN:fi-fe201108232274
dc.identifier.uri http://hdl.handle.net/10138/27439
dc.description.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
dc.language.iso fi
dc.publisher Helsingfors universitet sv
dc.publisher University of Helsinki en
dc.publisher Helsingin yliopisto fi
dc.rights This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
dc.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.
dc.rights Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.
dc.title Hakupuut muistihierarkiassa fi
dc.type.ontasot pro gradu-avhandlingar sv
dc.type.ontasot pro gradu -tutkielmat fi
dc.type.ontasot master's thesis en
dct.identifier.urn URN:NBN:fi-fe201108232274

Files in this item

Total number of downloads: Loading...

Files Size Format View
hakupuut.pdf 457.0Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record