Browsing by discipline "Computer science"

This thesis goes further in the study of implicit indicators used to infer interest in documents for information retrieval tasks. We study the behavior of two different categories of implicit indicators: fixation-derived features (number of fixations, average time of fixations, regression ratio, length of forward saccades), and physiology (pupil dilation, electrodermal activity). Based on the limited number of participants at our disposal we study how these measures react when addressing documents at three different reading rates. Most of the fixation-derived features are reported to differ significantly when reading at different speeds. Furthermore, the ability of pupil size and electrodermal activity to indicate perceived relevance is found intrinsically dependent on speed of reading. That is, when users read at comfortable reading speed, these measures are found to be able to correctly discriminate relevance judgments, but fail when increasing the addressed speed of reading. Therefore, the outcomes of this thesis strongly suggest to take into account reading speed when designing highly adaptive information retrieval systems.

Minimum-cost minimum path cover is a graph-theoretic problem with an application in gene sequencing problems in bioinformatics. This thesis studies decomposing graphs as a preprocessing step for solving the minimum-cost minimum path cover problem. By decomposing graphs, we mean splitting graphs into smaller pieces. When the graph is split along the maximum anti-chains of the graph, the solution for the minimum-cost minimum path cover problem can be computed independently in the small pieces. In the end all the partial solutions are joined together to form the solution for the original graph. As a part of our decomposition pipeline, we will introduce a novel way to solve the unweighted minimum path cover problem and with that algorithm, we will also obtain a new time/space tradeoff for reachability queries in directed acyclic graphs. This thesis also includes an experimental section, where an example implementation of the decomposition is tested on randomly generated graphs. On the test graphs we do not really get a speedup with the decomposition compared to solving the same instances without the decomposition. However, from the experiments we get some insight on the parameters that affect the decomposition's performance and how the implementation could be improved.

Suuri osa nykyisistä sovelluksista on selaimella käytettäviä web-sovelluksia. Eräs web-sovellusten suurimmista haasteista on tapahtumien käsittely, joka sisältää suuren osan sovelluksen virheistä. Funktionaalinen reaktiivinen ohjelmointi pyrkii selkeyttämään tapahtumienkäsittelyä ja sovelluksen tilan automaattista päivitystä. Funktionaalinen reaktiivinen ohjelmointi tarjoaa tähän kaksi työkalua: signaalit ja tapahtumavirrat. Signaalit ovat automaattisesti päivittyviä arvoja, joiden avulla sovelluksen käyttöliittymä voidaan pitää automaattisesti päivitettynä. Tapahtumavirrat ovat ajan mukaan järjestettyjä kokoelmia tapahtumia. Tapahtuman tapahtuessa se lisätään tapahtumavirtaan ja käsitellään. Tapahtumavirroille voidaan tehdä funktionaalisen ohjelmoinnin kokoelmien käsittelyn tyylisiä operaatioita. Tutkielmassa esitellään funktionaalisen reaktiivisen ohjelmoinnin periaatteet ja käsitellään tarkemmin Javascriptillä tehdyistä funktionaalisen reaktiivisen ohjelmoinnin toteutuksista RxJS ja Bacon.js. Funktionaalinen reaktiivinen ohjelmointi on selvä edistysaskel yksinkertaisista pelkkiin takaisinkutsuihin perustuvista ratkaisuista. Se parantaa sovellusten ylläpidettävyyttä, laajennettavuutta ja selkeyttää ohjelmakoodia. Useimpien sovellusten kehittämisessä käytetään sovelluskehyksiä. Sovelluskehysten tavoitteet ovat usein yhteneväisiä funktionaalisen reaktiivisen ohjelmoinnin kanssa, eli ne pyrkivät selkeyttämään tapahtumien käsittelyä, yhtenäistämään rajapintoja ja selkeyttämään sovellusten rakennetta. Tutkielmassa esimerkkisovelluskehyksenä on AngularJS. AngularJS toteuttaa monia reaktiivisuuden piirteitä ja sitä voidaan käyttää yhdessä Bacon.js:n ja RxJS:n kanssa. Funktionaalista reaktiivista ohjelmointia voidaan käyttää yhdessä sovelluskehysten kanssa, mutta sovelluskehysten kanssa funktionaalisen reaktiivisen ohjelmoinnin hyöty jää pienemmäksi. Monimutkaisen tapahtuman käsittelyn yhteydessä funktionaalisen reaktiivisen ohjelmoinnin käyttö voi olla järkevää, vaikka sovelluksessa olisikin sovelluskehys käytössä.

Tutkielma käsittelee funktionaalisille kielille tyypillisten piirteiden, ensimmäisen luokan funktioarvojen ja häntäkutsujen toteutusta oliokielille suunnatuilla JVM- ja .NET-virtuaalikonealustoilla. Oliokielille suunnattujen virtuaalikonealustojen tarjoamien tavukoodirajapintojen rajoitteet verrattuna matalamman tason assembly-kieliin ovat pitkään aiheuttaneet valtavirran oliokielistä poikkeavien kielten toteuttajille päänvaivaa. Tarkasteltavista alustoista .NET-alustan tavoitteena on alusta asti ollut monenlaisten kielten tukeminen. JVM-alustalla erilaisten kielten toteuttajien tarpeisiin on havahduttu vasta viimeisten vuosien aikana. Tutkielma tarkastelee, millaisia mahdollisuuksia alustat nykyisellään tarjoavat ensimmäisen luokan funktioarvojen ja häntäkutsujen toteuttajille ja miten alustoilla käytettävät toteutustekniikat poikkeavat perinteisistä konekieltä tuottavista kääntäjistä. Lisäksi esitetään arvio alustojen tarjoaman tuen soveltuvuudesta funktionaalisten kielten toteuttajien käyttöön ja verrataan alustojen tarjoamia tukitoimintoja. Arvioinnin tueksi esitellään oma prototyyppitoteutus Scheme-kielen osajoukolle, Cottontail Scheme, sekä selvitetään, millaisia toteutustekniikoita olemassa olevat funktionaaliset kielet tai funktionaalisia piirteitä tukevat moniparadigmakielet tällä hetkellä käyttävät virtuaalikonealustoilla. Tutkielmassa tehdyn vertailun perusteella havaittiin, että molemmilla alustoilla on omat vahvuutensa: JVM-alustan sulkeumien tuki on parantunut huomattavasti erityisesti JVM-alustan Java SE 8 -version myötä, mutta .NET-alusta on edelleen ainoa alusta, joka tarjoaa sisäänrakennettua tukea häntäkutsuille. Olemassa olevien kielten vertailussa huomattiin, että harva kielistä hyödyntää ominaisuuksien toteutuksessa alustan tukea, mikä saattaa esimerkiksi JVM-alustan sulkeumatuen tapauksessa johtua yksinomaan toiminnallisuuden tuoreudesta. Kummankaan alustoista ei havaittu tällä hetkellä tarjoavan selvästi toista parempaa tukea esimerkiksi Schemen kaltaisten funktionaalisten kielten toteuttajille.

Tietokonepelit on kehitetty perinteisesti joko pöytätietokoneille tai pelikonsoleille. Räjähdysmäisesti kasvaneet mobiilipelimarkkinat ovat kuitenkin haastaneet nämä pelialustat. Mobiilipelien kehitys tapahtuu usein samalla tyylillä kuin pöytätietokoneille ja pelikonsoleille, vaikka niistä löytyy pöytätietokoneista ja pelikonsoleista poikkeavaa tekniikkaa, joka mahdollistaa perinteisestä poikkeavan käyttäjäsyötteen. Nykyaikaisista mobiililaitteista löytyy muun muassa erilaisia ympäristöä tarkkailevia sensoreita sekä usein myös GPS-vastaanotin. GPS-vastaanotin tarjoaa pelin käyttöön pelaajan sijaintitiedon. Sensorit puolestaan tarkkailevat mobiililaitteen ympäristöä, kuten mobiililaitteen kiihtyvyyksiä kolmessa ulottuvuudessa. Sensoreilta saatua dataa voidaan käyttää käyttäjäsyötteessä joko suoraan tai muokattuna. Niiltä saadun datan avulla on myös mahdollista päätellä pelaajan tekemät eleet, jotka voidaan hahmontunnistuksen avulla sitoa osaksi pelin käyttäjäsyötettä. Tällainen mobiililaitteiden mahdollistama uudenlainen käyttäjäsyöte mahdollistaa uudenlaisia peligenrejä, jotka käyttävät pelaajan liikettä ja sijaintitietoa osana pelimekaniikkaa. Tämä työ esittelee ne pelimoottorin osat jotka ovat mukana GPS- ja sensoridatan keräämisessä ja käsittelyssä sekä esittelee tässä työssä suunnitellun GPS- ja sensoridataa hyödyntävän arkkitehtuurimallin mobiililaitteille. Työssä perehdytään aluksi aiheeseen liittyviin käsitteisiin sekä pelin reaaliaikaisuudesta huolehtivaan pelisilmukkaan ja sen erilaisiin arkkitehtuurimalleihin. Tämän jälkeen käydään läpi pelimoottorien suoritusaikaisesta arkkitehtuurista ne puolet, jotka liittyvät GPS- ja sensoridatan keräämiseen. Lopuksi esitellään ja arvioidaan tässä työssä suunniteltu arkkitehtuurimalli GPS- ja sensoridatan hyödyntämiselle mobiililaitteiden pelimoottoriarkkitehtuurissa. Työn ohessa tämän ehdotetun mallin toimivuus todennetaan Windows Phone 8 laitealustalle tehdyllä toteutuksella ja tämän toteutuksen lähdekoodia käytetään apuna ehdotetun mallin esittelyssä.

Grafiikkaprosessorin avustama järjestäminen on hyödyllistä tilanteissa, joissa keskusyksikkö ei pysty järjestämään syötettä riittävän nopeasti, tai jos syöte on jo valmiiksi grafiikkaprosessorin muistissa muun laskennan yhteydessä. Tässä työssä käydään läpi pikajärjestämisen, kantalukujärjestämisen ja lomitusjärjestämisen peräkkäin toimivat algoritmit ja selitetään uusimpien tutkimusten perusteella, kuinka niitä sovelletaan grafiikkaprosessorille rinnakkain suoritettavaksi. Lomitusvaihtojärjestäminen toteutettiin CUDA-alustalle ja sen suorituskykyä verrattiin Thrust-kirjaston lomitus- ja kantalukujärjestämistoteutuksiin. Mittausten mukaan lomitusvaihtojärjestäminen on keskusyksikössä toimivaa pikajärjestämistä nopeampi, mutta se ei pärjää suorituskyvyssä kirjaston toteutuksiin, kun syötteen alkioiden lukumäärä kasvatetaan. Lisäksi mitattiin, miten syötteen alkioiden koon muuttaminen vaikuttaa mainittujen kolmen toteutuksen järjestämisnopeuksiin. Kokeiden mukaan kantalukujärjestäminen on nopein, kun alkiot ovat muutaman tavun kokoisia, mutta alkioiden koon kasvaessa lomitusjärjestäminen menee suorituskyvyssä edelle.

Ihmisten käyttäytyminen internetissä voi määräytyä hyvin sattumanvaraisesti. Esimerkiksi sosiaalisen median kautta uudet ja kiinnostavat asiat voivat levitä hyvinkin nopeasti usealle eri ihmiselle. Jos sisällönjakaja ei ole varautunut, tai pystynyt varautumaan esimerkiksi rahallisista syistä, piikkeihin kysynnässä, niin odottamaton kiinnostus voi vaikuttaa palvelun laatuun tai jopa estää palvelun kokonaan. Esimerkkinä tilanteesta, jossa sisällön jakaja ei pysty täysin varautumaan äkkinäiseen resurssitarpeeseen, otetaan pieni videonjakopalvelu. Palvelua käyttää pieni vakiokäyttäjien joukko, jonka palveluun tarvittavan resurssimäärän yksittäinen palvelin pystyy hyvin tarjoamaan. Jos tällaisessa tilanteessa yksittäinen video menee viraaliksi sosiaalisessa mediassa ja käyttäjäkunta nousee hetkellisesti siihenastisesta maksimaalisesta ruuhkahuipusta 10-1000 -kertaiseksi, voi palvelin kaatua kokonaan tai ainakaan se ei pysty tarjoamaan ainoallekaan käyttäjälle palvelua. Jopa perinteinen sisällönjakeluverkko (CDN, content distribution network) auttaa huonosti tilanteeseen, jossa syntynyt salamajoukko (flash crowd) on vahvasti paikkaan sidottu ilmiö. Sisällönjakeluverkossa tieto jakaantuu kyllä suuremmalle maantieteelliselle alueelle kuin vain yksittäiseen keskuskoneeseen, mutta kun tarvitaan paljon kapasiteettia pienemmässä, vahvasti lokaalissa, paikallisessa osassa ei sisällönjakeluverkko olekaan enää paras ratkaisu ongelmaan. Tässä pro gradu -tutkielmassa keskitytään tutkimaan miten hyvin rajatuilla resursseilla varustettu palveluntarjoaja pystyisi rakentamaan suorituskykyisen videonjakopalvelun hajautetulla sisällönjakelulla. Samalla varmistetaan, että mahdollisen salamajoukon aiheuttaman käyttäjäpiikin aiheuttama ongelma ei johda palvelun kaatumiseen. Ratkaisuvaihtoehdoissa keskitytään käyttäjille hajautettuun ratkaisuun, koska palvelinkapasiteettia nimenomaan ei haluta lisätä. Jos pienemmillä resursseilla varustetut yksityishenkilöt voisivat ylläpitää omia palveluitaan halvalla ratkaisulla, saavutettaisiin monia etuja. Näitä etuja ovat muun muassa mahdollisen sensuurin väheneminen, yksityisyyden suoja, kilpailun mahdollistaminen, sopeutumiskyky ja virheiden sietokyky.

Tässä työssä käsitellään sähköisiä potilaskertomuksia (EHR) sekä tiedonhakua niistä hakemistoja hyödyntäen. Aluksi työssä esitellään keskeisimmät sähköisten potilaskertomusten standardit, kuten HL7 versiot 2 ja 3, CDA ja IHE XDS sekä BPPC. Tämän jälkeen siirrytään tarkastelemaan tarkemmin potilastiedon hakemistoja. Työssä tarkastellaan erityisesti IHE XDS –profiilia, joka kuvaa hakemistoon perustuvan sähköisten potilaskertomusten tiedonvälitystavan potilastietojärjestelmien välillä. ebXML:ään pohjautuvan IHE XDS:n keskeiset komponentit ovat arkisto (Document repository), asiakirjahakemisto (Document registry), asiakirjan tuottaja (Document source) ja asiakirjan käyttäjä (Document consumer). Työssä kuvataan näiden eri komponenttien tehtävät hakemistossa. Työssä kuvataan myös potilaskertomusten hakemista käyttäen IHE XDS-hakemista sekä OWL- ja SPARQL –kieleliä. Työssä esitellään myös muutamia kansallisia potilaskertomusjärjestelmiä, kuten suomen KanTa –järjestelmä sekä Hollannin ja Singaporen kansallisia potilaskertomusten arkistot sekä yleiseurooppalainen epSOS-hanke. Pohdintaosiossa arvioidaan potilaskertomusten hakemiseen käytettävissä olevien menetelmien tehokkuutta.

Bayesian networks are graphical models used to represent the joint probability distribution for all variables in a data set. A Bayesian network can be constructed by an expert, but learning the network from the data is another option. This thesis is centered around exact score-based Bayesian network structure learning. The idea is to optimize a scoring function measuring the fit of the network to the data, and the solution represents an optimal network structure. The thesis adds to the earlier literature by extending an external memory frontier breadth-first branch and bound algorithm by Malone et al. [MYHB11], which searches the space of candidate networks using dynamic programming in a layered fashion. To detect duplicates during the candidate solution generation, the algorithm uses efficiently both semiconductor and magnetic disk memory. In-memory duplicate detection is performed using a hash table, while a delayed duplicate detection strategy is employed when resorting to the disk. Delayed duplicate detection is designed to work well against long disk latencies, because hash tables are currently still infeasible on disk. Delayed duplicate detection allows the algorithm to scale beyond search spaces of candidate solutions fitting only in the comparatively expensive and limited semiconductor memory at disposal. The sorting-based delayed duplicate detection strategy employed by the original algorithm has been found to be inferior to a hashing-based delayed duplicate strategy in other application domains [Kor08]. This thesis presents an approach to use hashing-based delayed duplicate detection in Bayesian network structure learning and compares it to the sorting-based method. The problem faced in the hashing of candidate solutions to disk is dividing the candidate solutions in a certain stage of the search in an efficient and scalable manner to files on the disk. The division presented in this thesis distributes the candidate solutions into files unevenly, but takes into account the maximum number of candidate solutions that can be held in the semiconductor memory. The method works in theory as long as operating system has free space and inodes to allocate for new files. Although the hashing-based method should in principle be faster than the sorting-based, the benchmarks presented in this thesis for the two methods show mixed results. However, the analysis presented also highlights the fact that by improving the efficiency of, for example, the distribution of hashed candidate solutions to different files, the hashing-based method could be further improved.

Computation offloading can be used to leverage the resources of nearby computers to ease the computational burden of mobile devices. Cloudlets are an approach, where the client's tasks are executed inside a virtual machine (VM) on a nearby computing element, while the client orchestrates the deployment of the VM and the remote execution in it. Mobile devices tend to move, and while moving between networks, their address is prone to change. Should a user bring their device close to a better performing Cloudlet host, migration of the original Cloudlet VM might also be desired, but their address is then prone to change as well. Communication with Cloudlets relies on the TCP/IP networking stack, which resolves address changes by terminating connections, and this seriously impairs the usefulness of Cloudlets in presence of mobility events. We surveyed a number of mobility management protocols, and decided to focus on Host Identity Protocol (HIP). We ported an implementation, HIP for Linux (HIPL), to the Android operating system, and assessed its performance by benchmarking throughput and delay for connection recovery during network migration scenarios. We found that as long as the HIPL hipfw-module, and especially the Local Scope Identifier (LSI) support was not used, the implementation performed adequately in terms of throughput. On the average, the connection recovery delays were tolerable, with an average recovery time of about 8 seconds when roaming between networks. We also found that with highly optimized VM synthesis methods, the recovery time of 8 seconds alone does not make live migration favourable over synthesizing a new VM. We found HIP to be an adequate protocol to support both client mobility and server migration with Cloudlets. Our survey suggests that HIP avoids some of the limitations found in competing protocols. We also found that the HIPL implementation could benefit from architectural changes, for improving the performance of the LSI support.