Yliopiston etusivulle Suomeksi På svenska In English Helsingin yliopisto

Hakupuut muistihierarkiassa

Show full item record

Files in this item

Files Description Size Format View/Open
hakupuut.pdf 468.0Kb PDF View/Open
Use this URL to link or cite this item: http://urn.fi/URN:NBN:fi-fe201108232274
Vie RefWorksiin
Title: Hakupuut muistihierarkiassa
Author: Koskinen, Paavo
Contributor: University of Helsinki, Faculty of Science, Department of Computer Science
Thesis level: Master's thesis
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.
URI: URN:NBN:fi-fe201108232274
http://hdl.handle.net/10138/27439
Date: 2011-08-15
Copyright information: This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
This item appears in the following Collection(s)

Show full item record

Search Helda


Advanced Search

Browse

My Account