M.Sc. Bella Zhukova puollustaa väitöskirjaansa "New space-time trade-offs for pattern matching with compressed indexes" torstaina 22.2.2024 klo 13 Helsingin yliopiston Exactum-rakennuksen auditoriossa B123 (Pietari Kalmin katu 5, 1. krs). Vastaväittäjänä toimii professori Johannes Fischer (Technische Universität Dortmund, Saksa) ja kustoksena professori Simon J. Puglisi (Helsingin yliopisto). Väitöstilaisuus pidetään englanniksi.
Bella Zhukovan väitöskirja on osa Helsingin yliopiston tietojenkäsittelytieteen osastolla ja Algorithmic Bioinformatics -ryhmän Compressed Data Structures -tiimissä tehtävää tutkimusta. Väitöskirjatyön ohjaajana on toiminut professori Simon J. Puglisi (Helsingin yliopisto).
Uusia tila-aikavaihtoehtoja merkkijonohakuun pakatuilla indeksirakenteilla
Merkkijonohaku on perustavanlaatuinen ongelma tietojenkäsittelytieteessä ja sen läheisillä aloilla. Tehtävänä on löytää tekstihahmon tai osamerkkijonon esiintymiä laajemmassa tekstissä. Ongelma esiintyy useissa sovelluksissa, kuten bioinformatiikassa, tekstinkäsittelyssä ja tiedonhaussa. Klassiset algoritmit tähän ongelmaan tarvitsevat suuren määrän muistia syötteen lisäksi, mikä saattaa muodostua ongelmaksi suurien modernien syötteiden kohdalla. Ratkaisuna tähän on kehitetty uusia indeksirakenteita, joiden tilantarve on lähellä informaatioteoreettista alarajaa tai jopa tämän alle toisteisten syötteiden tapauksessa, siten, että kyselyt voidaan edelleen suorittaa tehokkaasti.
Tässä väitöskirjassa on suunniteltu ja toteutettu uusia pakattuja tietorakenteita merkkijonohaulle toisteisissa syötteissä, joita löytyy esimerkiksi bioinformatiikasta ja versioiduista tekstikokoelmista kuten ohjelman lähdekoodit. Työ on julkaistu viitenä artikkelina.
Indeksoitu merkkijonohaku tarvitsee yleensä kaksi operaatiota: laskeminen, joka palauttaa hahmon esiintymien määrän tekstissä, ja paikallistaminen, joka listaa näiden esiintymien sijainnit. Artikkelissa I tarkastelemme erästä tapaa nopeuttaa laskemisoperaatiota FM-indeksirakenteessa, jonka tehokkuus riippuu vain rank-kyselyn nopeudesta tekstin Burrows-Wheeler-muunnoksessa.
Seuraavat kaksi artikkelia keskittyvät paikallistamiskyselyihin. Artikkelissa II kuvaillaan ja toteutetaan erittäin tehokas pakattu tekstitietorakenne perustuen Lempel-Ziv (RLZ) -pakattuun loppuosataulukkon. Kolmannessa artikkelissa pienennetään tämän indeksin tilankäyttöä esittelemällä tehokkaampia RLZ-hakemistoja ja käyttämällä tilatiiviimpiä esitystapoja tietorakenteen osille.
Artikkelissa IV tutkimme algoritmeja dokumenttilistauskyselyille, jotka perustuvat dokumenttitaulukon välien skannaukselle. Tutkimme myös menetelmiä dokumenttitaulukon pakkaamiseksi siten, että nopeat kyselyt ovat edelleen mahdollisia.
Lopuksi, artikkelissa V suunnitellaan ja toteutetaan indeksirakenteita, jotka mahdollistavat tekstihaun suurissa aineistoissa hahmoilla, jotka sisältävät vaihtuvanpituisia aukkoja.
Väitöskirjan saatavuus
Väitöskirjan elektroninen versio tulee olemaan saatavilla Helsingin yliopiston e-thesis-palvelussa osoitteessa http://urn.fi/URN:ISBN:978-952-84-0088-2.
Painettuja väitöskirjoja voi tiedustella väittelijältä itseltään: bella.zhukova@helsinki.fi.