Auxiliary data structures for improved suffix array query performance

Show simple item record

dc.contributor Helsingin yliopisto, Matemaattis-luonnontieteellinen tiedekunta fi
dc.contributor University of Helsinki, Faculty of Science en
dc.contributor Helsingfors universitet, Matematisk-naturvetenskapliga fakulteten sv
dc.contributor.author Heino, Lauri
dc.date.issued 2020
dc.identifier.uri URN:NBN:fi:hulib-202012084732
dc.identifier.uri http://hdl.handle.net/10138/322476
dc.description.abstract 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. en
dc.language.iso eng
dc.publisher Helsingin yliopisto fi
dc.publisher University of Helsinki en
dc.publisher Helsingfors universitet sv
dc.subject suffix arrays en
dc.subject data structures en
dc.title Auxiliary data structures for improved suffix array query performance en
dc.type.ontasot pro gradu -tutkielmat fi
dc.type.ontasot master's thesis en
dc.type.ontasot pro gradu-avhandlingar sv
dc.subject.discipline Tietojenkäsittelytiede und
dct.identifier.urn URN:NBN:fi:hulib-202012084732

Files in this item

Total number of downloads: Loading...

Files Size Format View
Heino_Lauri_tutkielma_2020.pdf 560.7Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record