search query: @keyword user behavior / total: 3
reference: 1 / 3
« previous | next »
| Author: | Walldén, Valtteri |
| Title: | Approximating Distinct Users: A Synopsis Data Structure |
| Tiivistelmäatietorakenne uniikkien käyttäjien laskemiseen | |
| Publication type: | Master's thesis |
| Publication year: | 2016 |
| Pages: | 50 Language: eng |
| Department/School: | Perustieteiden korkeakoulu |
| Main subject: | Ohjelmistotekniikka (T-106) |
| Supervisor: | Saikkonen, Heikki |
| Instructor: | Talja, Ari |
| Electronic version URL: | http://urn.fi/URN:NBN:fi:aalto-201602161376 |
| Location: | P1 Ark Aalto 3514 | Archive |
| Keywords: | distinctness queries user behavior synopsis data structure cardinality uniikit käyttäjät tiivistelmätietorakenne |
| Abstract (eng): | More and more data about users and their behavior is being collected both on the web and in mobile applications. Aggregating, processing, and making this data available in ways that help to guide decision-making is difficult, however. This thesis presents an algorithm for pre-processing user behavior data to produce a data structure that answers queries about the numbers of distinct users matching a given set of criteria. These kinds of queries can be made directly by planners and managers, or by systems such as forecasting and reporting systems that need information about counts of distinct users. In our algorithm, users are aggregated according to their transaction profile, or the set of behaviors that each user exhibits in the input data. This aggregation results in a massive reduction in terms of the memory footprint of the information. Our data structure can only be queried for counts, however, and not the behavior of specific users. Data identifying individual users is lost upon aggregation. We advocate pruning some transaction profiles to further reduce the size of the resulting data structures, and provide insights into how this might best be done. After pruning, our output no longer provides exact counts of distinct users, but rather approximations. Such data structures are known in the literature as synopsis data structures. The method presented in this thesis reduced the memory footprint of our user behavioral test data to less than 5 % of its original size while providing accurate counts, and to less than 1.2 % with pruning. Pruning provides substantial benefits in terms of memory, but can introduce a significant amount of error into the approximate counts. This can be counteracted with scaling. The effectiveness of the algorithm depends on its ability to aggregate the input data enough so that the resulting data structures are small and so that pruning does not have too large of an effect on accuracy. |
| Abstract (fin): | Käyttäjistä kerätään internetissä ja mobiili-sovelluksissa yhä enemmän tietoa. Tämä tieto on erittäin hyödyllistä: sen avulla voidaan oppia tuntemaan käyttäjiä paremmin, tai siihen voidaan perustaa ennusteita tulevasta. Tieto on kuitenkin ensin saatettava käytettäväksi, joko suoraan ihmisten käsiin tai muiden järjestelmien ulottuville. Tässä diplomityössä esitetty algoritmi ryhmittää palvelun käyttäjistä kerättyä tietoa ja koostaa tietorakenteen, josta voi hakea käyttäjäryhmien kokoja eli annettujen määritelmien vastaavien uniikkien käyttäjien määrää. Käyttäjät ryhmitellään algoritmissa heidän transaktioprofiilinsa mukaan. Transaktioprofiili kuvaa kaikkea sitä käyttäytymistä, jota käyttäjä ilmentää. Tämä ryhmittely säästää paljon muistia, mutta se myös hävittää yksilöivän tiedon, eli tietorakennetta voidaan käyttää vain hakemaan ryhmien kokoja. Tietorakenteesta tulee tiivistelmätietorakenne (synopsis data structure), kun poistamme siitä pieniä tai muuten epäkiinnostavia transaktioprofiileita. Tiivistelmätietorakenne ei enää palauta tarkkoja vastauksia, vaan arvioita, sillä siitä on hävitetty joidenkin käyttäjien tietoja. Tietorakenne tiivisti koetiedot alle viiteen prosenttiin alkuperäiskoostaan. Kun poistimme pienimmät transaktioprofiilit, koko pieneni yhä alle 1.2 % prosenttiin koetietojen alkuperäiskoosta. Profiilien poistaminen vaikuttaa dramaattisesti käyttäjämäärien tarkkuuteen, mutta tarkkuutta voidaan yrittää parantaa esimerkiksi skaalaamalla tuloksia lineaarisesti. |
| ED: | 2016-02-21 |
INSSI record number: 53168
+ add basket
« previous | next »
INSSI