• norsk
    • English
  • norsk 
    • norsk
    • English
  • Logg inn
Vis innførsel 
  •   Hjem
  • Fakultet for informasjonsteknologi og elektroteknikk (IE)
  • Institutt for datateknologi og informatikk
  • Vis innførsel
  •   Hjem
  • Fakultet for informasjonsteknologi og elektroteknikk (IE)
  • Institutt for datateknologi og informatikk
  • Vis innførsel
JavaScript is disabled for your browser. Some features of this site may not work without it.

State of the Art Learned Index Structures

Tengs, Simen Sælevik
Master thesis
Thumbnail
Åpne
no.ntnu:inspera:112296943:23103834.pdf (7.965Mb)
Permanent lenke
https://hdl.handle.net/11250/3026813
Utgivelsesdato
2022
Metadata
Vis full innførsel
Samlinger
  • Institutt for datateknologi og informatikk [6334]
Sammendrag
"Learned Indexes" har vært et populært tema innen databasesamfunnet etter at den første Learned Index ble publisert, ved å introdusere maskinlæring til å løse indekseringsproblemet som lenge har vært dominert av tradisjonelle datastrukturer som B-trær. Siden da har det blitt publisert flere Learned Indexes. Noen av disse er laget for spesifikke situasjoner, mens andre er mer fleksible. De fleksible Learned Indexes kan utføre de samme oppgavene som et B-tre, ved å støtte en variasjon av forskjellige spørreoperasjoner. I denne oppgaven gir vi en teknisk analyse av to state of the art Learned Indexes, som begge kan brukes til generelle formål. Disse strukturene har mange av de samme egenskapene, selv om de er bygget på ulike tilnærminger. Vi dekker også to Learned Indexes som har gitt inspirasjon til, og introdusert mange viktige konsepter som blir brukt av state of the art Learned Indexes.

Vi lager en benchmark for to state of the art learned indexes kalt ALEX og PGM-Index, ved å bruke forfatternes egne implementasjoner av strukturene i C++. Vi viser at vi kan reprodusere lignende resultater som er rapportert av forfatterne, og gir en sammenligning av ytelsen til ALEX og PGM på samme datasett og med lik fordeling av spørringer. Vi fant ut at ALEX ga bedre ytelse for lesespørringer. PGM-Index ga mer konsistente resultater for alle datadistribusjoner og spørrefordelinger, og gav bedre resultater for skrivespørringer på en av datadistribusjonene.
 
”Learned Indexes” have been a hot topic within the database community after the release

of the first learned index, which introduces machine learning to solve the indexing prob-

lem that have for a long time, and still are, dominated by traditional structures like B-trees.

There have since been created several learned indexes, some of which are created for spe-

cific purposes, and some that prove to be very flexible. These flexible learned indexes

may serve the same purpose as the B-tree, by supporting a wide variety of workloads and

still providing great performance. In this thesis, we provide a technical analysis of two

state of the art, general purpose learned indexes; ALEX and PGM-Index. These structures

have many of the same characteristics while being built on different approaches. We also

cover two learned indexes that have given inspiration to, and introduced many important

concepts that are being used by the state of the art learned indexes.

We create a benchmark for the two state of the art learned indexes, by using the authors

own implementations of their respective structures in C++. We show that we are able

to reproduce similar performance results as reported by the authors, as well as provide a

novel side by side comparison of ALEX and PGM-Index on the same data distributions

and query workloads. We found that ALEX produced better query performance overall

for read-only workloads. PGM-Index performed more consistent for all data distribu-

tions and workloads, and had better write performance than ALEX on one of the data

distributions.
 
Utgiver
NTNU

Kontakt oss | Gi tilbakemelding

Personvernerklæring
DSpace software copyright © 2002-2019  DuraSpace

Levert av  Unit
 

 

Bla i

Hele arkivetDelarkiv og samlingerUtgivelsesdatoForfattereTitlerEmneordDokumenttyperTidsskrifterDenne samlingenUtgivelsesdatoForfattereTitlerEmneordDokumenttyperTidsskrifter

Min side

Logg inn

Statistikk

Besøksstatistikk

Kontakt oss | Gi tilbakemelding

Personvernerklæring
DSpace software copyright © 2002-2019  DuraSpace

Levert av  Unit