Auxiliary data structures for improved suffix array query performance

Show full item record



Permalink

http://urn.fi/URN:NBN:fi:hulib-202012084732
Title: Auxiliary data structures for improved suffix array query performance
Author: Heino, Lauri
Other contributor: Helsingin yliopisto, Matemaattis-luonnontieteellinen tiedekunta
University of Helsinki, Faculty of Science
Helsingfors universitet, Matematisk-naturvetenskapliga fakulteten
Publisher: Helsingin yliopisto
Date: 2020
Language: eng
URI: http://urn.fi/URN:NBN:fi:hulib-202012084732
http://hdl.handle.net/10138/322476
Thesis level: master's thesis
Discipline: Tietojenkäsittelytiede
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.
Subject: suffix arrays
data structures


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 full item record