search query: @keyword database / total: 70
reference: 4 / 70
« previous | next »
Author:Lehtonen, Jonas
Title:Bulk Indexing on Flash Devices
Tietuekimppujen indeksointi flash-muistilla
Publication type:Master's thesis
Publication year:2014
Pages:xii + 69      Language:   eng
Department/School:Tietotekniikan laitos
Main subject:Tietojenkäsittelytiede   (IL3010)
Supervisor:Soisalon-Soininen, Eljas
Instructor:Saikkonen, Riku
Electronic version URL: http://urn.fi/URN:NBN:fi:aalto-201406252208
OEVS:
Electronic archive copy is available via Aalto Thesis Database.
Instructions

Reading digital theses in the closed network of the Aalto University Harald Herlin Learning Centre

In the closed network of Learning Centre you can read digital and digitized theses not available in the open network.

The Learning Centre contact details and opening hours: https://learningcentre.aalto.fi/en/harald-herlin-learning-centre/

You can read theses on the Learning Centre customer computers, which are available on all floors.

Logging on to the customer computers

  • Aalto University staff members log on to the customer computer using the Aalto username and password.
  • Other customers log on using a shared username and password.

Opening a thesis

  • On the desktop of the customer computers, you will find an icon titled:

    Aalto Thesis Database

  • Click on the icon to search for and open the thesis you are looking for from Aaltodoc database. You can find the thesis file by clicking the link on the OEV or OEVS field.

Reading the thesis

  • You can either print the thesis or read it on the customer computer screen.
  • You cannot save the thesis file on a flash drive or email it.
  • You cannot copy text or images from the file.
  • You cannot edit the file.

Printing the thesis

  • You can print the thesis for your personal study or research use.
  • Aalto University students and staff members may print black-and-white prints on the PrintingPoint devices when using the computer with personal Aalto username and password. Color printing is possible using the printer u90203-psc3, which is located near the customer service. Color printing is subject to a charge to Aalto University students and staff members.
  • Other customers can use the printer u90203-psc3. All printing is subject to a charge to non-University members.
Location:P1 Ark Aalto  1717   | Archive
Keywords:index structures
database
search trees
B-tree
group update
bulk update
group deletion
bulk deletion
group insertion
bulk insertion
interval deletion
range deletion
flash memory
hakemistorakenne
indeksointi
hakupuu
B-puu
kimppupäivitys
kimppupoisto
kimppulisäys
intervallipoisto
tietokanta
avainvälipoisto
flash-muisti
Abstract (eng):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.
Abstract (fin):Tietokantasovelluksissa kimppuoperaatiot jotka vaikuttavat useampaan alkioon kerralla ovat yleisiä, ja niitä käytetään tehostamaan tietokannan toimintaa.
Niitä voi käyttää kun data lisätään tietokantaan suuressa erässä (esimerkiksi myyntidata jota päivitetään kerran päivässä)tai osana muita tietokantaoperaatioita.

Kimppuoperaatioita on tutkittu jo vuosikymmeniä, mutta niiden käyttöä flash-muistilla on tutkittu vähemmän.
Flash-muisti on yleistyvä muistiteknologiajota käytetään magneettisten kiintolevyjen sijaan tai niiden rinnalla.
Sen tietokannoille hyödyllisiin ominaisuuksiin kuuluvat mm. nopeat hakuajat ja alhainen sähkönkulutus.
Kuitenkin datan poisto levyltä on työläs operaatio flash-levyillä, mistä johtuen tietorakenteet kannattaa suunnitella erikseen flash-levyille.
Tämä työ tutkii flashin käyttöä tietorakenteissa ja koostaa niistä flashille soveltuvia suunnitteluperiaatteita.
Näitä periaatteita edustaa myös työssä esitetty uusi rakenne, kimppuhakemisto (bulk index).
Kimppuhakemisto on tietorakenne kimppuoperaatioille flash-muistilla, ja sitä verrataan kokeellisesti LA-puuhun (Lazy Adaptive Tree, suom. laiska adaptiivinen puu), joka on suoriutunut hyvin kokeissa flash-muistilla.

Kokeissa käytettiin vaihtelevan kokoisia alkeiskimppuja, eli maksimaalisia joukkoja lisätyssä datassa jotka sijoittuvat kahden olemassaolevan avaimen väliin.
Kimppuhakemisto oli nopeampi kuin LA-puu, ja erityisen paljon nopeampi kimppulisäyksissä pienellä määrällä hyvin suuria tai suurella määrällä hyvin pieniä alkeiskimppuja, tai suurilla kimppulisäyksillä.
Parhaimmillaan se oli yli neljä kertaa nopeampi.
Välihauissa se oli jopa 50 % nopeampi kuin LA-puu, ja parempi suurten välien kanssa.
Välipoistot näytettiin vakioaikaisiksi kimppuhakemistossa.
ED:2014-08-03
INSSI record number: 49429
+ add basket
« previous | next »
INSSI