Auxiliary data structures for improved suffix array query performance

Visa fullständig post



Permalänk

http://urn.fi/URN:NBN:fi:hulib-202012084732
Titel: Auxiliary data structures for improved suffix array query performance
Författare: Heino, Lauri
Medarbetare: Helsingfors universitet, Matematisk-naturvetenskapliga fakulteten
Utgivare: Helsingin yliopisto
Datum: 2020
Språk: eng
Permanenta länken (URI): http://urn.fi/URN:NBN:fi:hulib-202012084732
http://hdl.handle.net/10138/322476
Nivå: pro gradu-avhandlingar
Ämne: Tietojenkäsittelytiede
Abstrakt: The suffix array is a space-efficient data structure that provides fast access to all occurrences of a search pattern in a text. Typically suffix arrays are queried with algorithms based on binary search. With a pre-computed index data structure that provides fast access to the relevant suffix array interval, querying can be sped-up, because the binary search process operates over a smaller interval. In this thesis a number different ways of implementing such an index data structure are studied, and the performance of each implementation is measured. Our experiments show that with relatively small data structures, one can reduce suffix array query times by almost 50%. There is a trade-off between the size of the data structure and the speed-up potential it offers.
Subject: suffix arrays
data structures


Filer under denna titel

Totalt antal nerladdningar: Laddar...

Filer Storlek Format Granska
Heino_Lauri_tutkielma_2020.pdf 560.7Kb PDF Granska/Öppna

Detta dokument registreras i samling:

Visa fullständig post