Browsing by Author "Saikkonen, Riku"

Now showing 1 - 6 of 6

Bulk Indexing on Flash Devices
(2014-06-02) Lehtonen, Jonas
Perustieteiden korkeakoulu | Master's thesis
In database applications, bulk operations which affect multiple records at once are common. They are performed when operations on single records at a time are not efficient enough. They can occur in several ways, both by applications naturally having bulk operations (such as a sales database which updates daily) and by applications performing them routinely as part of some other operation. While bulk operations have been studied for decades, their use with flash memory has been studied less. Flash memory, an increasingly popular alternative/complement to magnetic hard disks, has far better seek times, low power consumption and other desirable characteristics for database applications. However, erasing data is a costly operation, which means that designing index structures specifically for flash disks is useful. This thesis will investigate flash memory on data structures in general, identifying some common design traits, and incorporate those traits into a novel index structure, the bulk index. The bulk index is an index structure for bulk operations on flash memory, and was experimentally compared to a flash-based index structure that has shown impressive results, the Lazy Adaptive Tree (LA-tree for short). The bulk insertion experiments were made with varying-sized elementary bulks, i.e. maximal sets of inserted keys that fall between two consecutive keys in the existing data. The bulk index consistently performed better than the LA-tree, and especially well on bulk insertion experiments with many very small or a few very large elementary bulks, or with large inserted bulks. It was more than 4 times as fast at best. On range searches, it performed up to 50 % faster than the LA-tree, performing better on large ranges. Range deletions were also shown to be constant-time on the bulk index.
Bulk updates and cache sensitivity in search trees
(2009) Saikkonen, Riku
Doctoral dissertation (monograph)
This thesis examines two topics related to binary search trees: cache-sensitive memory layouts and AVL-tree bulk-update operations. Bulk updates are also applied to adaptive sorting. Cache-sensitive data structures are tailored to the hardware caches in modern computers. The thesis presents a method for adding cache-sensitivity to binary search trees without changing the rebalancing strategy. Cache-sensitivity is maintained using worst-case constant-time operations executed when the tree changes. The thesis presents experiments performed on AVL trees and red-black trees, including a comparison with cache-sensitive B-trees. Next, the thesis examines bulk insertion and bulk deletion in AVL trees. Bulk insertion inserts several keys in one operation. The number of rotations used by AVL-tree bulk insertion is shown to be worst-case logarithmic in the number of inserted keys, if they go to the same location in the tree. Bulk deletion deletes an interval of keys. When amortized over a sequence of bulk deletions, each deletion requires a number of rotations that is logarithmic in the number of deleted keys. The search cost and total rebalancing complexity of inserting or deleting keys from several locations in the tree are also analyzed. Experiments show that the algorithms work efficiently with randomly generated input data. Adaptive sorting algorithms are efficient when the input is nearly sorted according to some measure of presortedness. The thesis presents an AVL-tree-based variation of the adaptive sorting algorithm known as local insertion sort. Bulk insertion is applied by extracting consecutive ascending or descending keys from the input to be sorted. A variant that does not require a special bulk-insertion algorithm is also given. Experiments show that applying bulk insertion considerably reduces the number of comparisons and time needed to sort nearly sorted sequences. The algorithms are also compared with various other adaptive and non-adaptive sorting algorithms.
Funktionaalisten reaktiivisten kielten toteutusmenetelmät
(2014-05-13) Rouhiainen, Joonas
Perustieteiden korkeakoulu | Bachelor's thesis
Group insertion in AVL trees
(2004) Saikkonen, Riku
Helsinki University of Technology | Master's thesis
Työssä tutkitaan useita algoritmeja AVL-puun ryhmälisäysoperaatiolle. Tutkitut algoritmit kuvataan yksityiskohtaisesti, mutta työn pääasiallinen sisältö on ryhmälisäyksen tehokkuuden kokeellinen tutkiminen. Tasapainotusoperaatioiden määrän lisäksi mitattiin välimuistin käytön tehokkuutta simuloidun välimuistin avulla. Työssä kuvataan myös kokeissa käytetyn ohjelmiston arkkitehtuuri. Ryhmälisäysalgoritmi lisää joukon avaimia tietorakenteeseen yhdellä operaatiolla. Ryhmälisäyksessä tarvitaan vähemmän tasapainotusoperaatioita kuin jos avaimet lisättäisiin yksi kerrallaan yksittäislisäyksellä, koska tasapainotus voidaan tehdä sen jälkeen, kun kaikki avaimet on lisätty. AVL-puut ovat tasapainoisia binäärisiä hakupuita, joiden sovelluksia ovat esimerkiksi keskusmuistitietokannat ja kokotekstihaku. AVL-puilla on pienet solmut ja tasapainotusoperaatiot ovat paikallisia, mikä tekee niistä tehokkaita rinnakkaisessa käytössä. Työn kokeissa ryhmälisäysalgoritmeja verrattiin toisiinsa ja tavalliseen yksittäislisäysalgoritmiin eri tilanteissa. Välimuistikäyttäytymistä mitattiin laskemalla työjoukon koko sekä eri kokoisilla simuloiduilla välimuisteilla. Kokeissa käytettiin kolmea ryhmälisäysalgoritmia: niin sanottua yksinkertaista ryhmälisäystä (avaimet lisätään yksi aliryhmä kerrallaan) käyttäviä O(log m)- ja O(log² m)-algoritmeja sekä monen aliryhmän lisäystä käyttävää O(log² m)-algoritmia (m on aliryhmän koko). Aliryhmä muodostuu saman lehtisolmun alle päätyvistä avaimista. Kokeissa mitatut rotaatioiden määrät sopivat hyvin analyyttisiin kompleksisuustuloksiin: O(log m)-algoritmi teki paljon vähemmän rotaatioita kuin kaksi O(log² m)-algoritmia, myös pienillä m:n arvoilla. Ryhmälisäysalgoritmit toimivat myös selvästi yksittäislisäystä paremmin yli kahden kokoisilla aliryhmillä. O(log m)-algoritmin välimuistin käyttö oli kuitenkin tehottomampaa kuin O(log² m)-algoritmilla. Nähtävästi O(log m)-algoritmilla on suurempi työjoukko, koska se tarvitsee enemmän tietoa valitessaan suoritettavia rotaatioita. Tämä ja muut päätulokset näkyivät sekä satunnaisesti muodostetulla syötteellä että simuloidusta kokotekstihakusovelluksesta tuotetusta syötteestä.
Nykyaikaisten tiedostojarjestelmien tietorakenteet
(2013-04-25) Palm, Joonas
Perustieteiden korkeakoulu | Bachelor's thesis
SSD-levyille optimoidut tietokantarakenteet
(2014-04-14) Huhtanen, Hannu
Perustieteiden korkeakoulu | Bachelor's thesis