Yliopiston etusivulle Suomeksi På svenska In English Helsingin yliopisto

Hakupuut muistihierarkiassa

Show simple item record

dc.contributor Helsingin yliopisto, matemaattis-luonnontieteellinen tiedekunta, tietojenkäsittelytieteen laitos fi
dc.contributor Helsingfors universitet, matematisk-naturvetenskapliga fakulteten, institutionen för datavetenskap sv
dc.contributor University of Helsinki, Faculty of Science, Department of Computer Science en
dc.contributor.author Koskinen, Paavo fi
dc.date.accessioned 2011-08-23T13:08:52Z
dc.date.available 2011-08-23 fi
dc.date.available 2011-08-23T13:08:52Z
dc.date.issued 2011-08-15 fi
dc.identifier.uri URN:NBN:fi-fe201108232274 fi
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 fi
dc.publisher Helsingin yliopisto fi
dc.publisher Helsingfors universitet sv
dc.publisher University of Helsinki en
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. fi
dc.rights This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited. en
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. sv
dc.title Hakupuut muistihierarkiassa fi
dc.type.ontasot Pro gradu fi
dc.type.ontasot Master's thesis en
dc.type.ontasot Pro gradu sv
dc.ths Kärkkäinen, Juha fi
dc.ths Mäkinen, Veli fi
dc.type.dcmitype Text fi

Files in this item

Files Description Size Format View/Open
hakupuut.pdf 468.0Kb PDF View/Open
This item appears in the following Collection(s)

Show simple item record

Search Helda


Advanced Search

Browse

My Account