Väitös tietotekniikan alalta, DI Matti Karppa

Väitöskirjan nimi on "On Bilinear Techniques for Similarity Search and Boolean Matrix Multiplication"

Skaalautuvuus on algoritmitutkimuksen keskeisimpiä tutkimuskohteita. Suuret data-aineistot eivät esimerkiksi yleensä mahdollista pareittaisten vertailujen tekemistä kaikille aineiston alkioille: miljardin olion tietokannassa tämä tarkoittaisi triljoonan vertailun tekemistä.

Tässä väitöstyössä on tutkittu samankaltaisuushakua ja Boolen matriisikertolaskua. Samankaltaisuushaku vastaa kysymykseen, miten tietokannasta löydetään samanlaiselta vaikuttavia olioita, mielellään vertailematta kaikkia pareittain. Matriisikertolasku on eräs keskeisimpiä matemaattisia peruslaskutoimituksia, jonka luonnontieteellisten ja teknisten alojen opiskelijat oppivat perusopinnoissaan. Matriisikertolaskulle tunnetaan tehokkaita algoritmeja, joten sitä hyödyntämällä samankaltaisuushakua voidaan tehdä ilmeistä tehokkaammin eli vertailematta kaikkia alkioita keskenään.

Väitöstyössä on tutkittu myös matriisikertolaskun ja muiden samankaltaisten operaatioiden laskemista itsessään. Tuloksena on saatu uusia algoritmeja, joiden avulla voidaan löytää uusia algoritmeja, ja näiden sovelluksena saatu tuloksina uusia algoritmeja Boolen matriisikertolaskun eli 1/0-arvoisen matriisikertolaskun laskemiseen. Lisäksi on toteutuksella osoitettu, että Boolen matriisikertolasku voidaan tehdä tehokkaasti jaetun muistin rinnakkaisjärjestelmässä jopa 1 terabitin syötteillä.

Vastaväittäjänä toimii professori Rasmus Pagh, University of Copenhagen, Tanska

Kustos: professori Petteri Kaski, Aalto-yliopiston perustieteiden korkeakoulu, tietotekniikan laitos

Väittelijän yhteystiedot: Matti Karppa, p. 044 0499 708, [email protected]

Väitöskirja on julkisesti nähtävillä kymmenen päivää ennen väitöstä Aalto-yliopiston perustieteiden korkeakoulun ilmoitustaululla, Konemiehentie 2