Approximate information filtering in publish/subscribe peer-to-peer networks

Thumbnail Image

URL

Journal Title

Journal ISSN

Volume Title

School of Electrical Engineering | Licentiate thesis
Checking the digitized thesis and permission for publishing
Instructions for the author

Authors

Date

2010

Department

Tietoliikenne- ja tietoverkkotekniikan laitos

Major/Subject

Tietoverkkotekniikka

Mcode

S-38

Degree programme

Language

en

Pages

v + 69 s. + liitt. 5

Series

Abstract

Publish and subscribe systems are becoming increasingly popular in Internet mainly due to the users need to limit the information flood. The pubsub paradigm refers to a model where the receivers (subscribers) specify the information they want to receive instead of letting senders (publishers) decide what they want to send. The problem of this model is often the difficulty to compose the query for exact matching of the words. The user may not find the correct terms, or all synonyms. Approximate filtering addresses this problem by giving the user more freedom to specify the query. This thesis studies the key issues of applying approximate free text filtering to the pubsub model in p2p overlay networks. In approximate filtering the subscriber accepts a document whenever it is similar enough with the query according to the selected measure. The query may be words, phrases or even a text document, and the task of the pubsub system is to match the published documents with the queries and generate the notifications to the subscribers. In a p2p network the documents are published and the queries are stored by any peer, but the user wants the relevant documents regardless of their location, which creates the "rendezvous" problem for the pubsub system to solve efficiently. Three technical problem areas are studied. First, the pubsub model involves the problem of inverse query, i.e. each document is matched against all queries at a time and not vice versa. The solutions developed for databases and search applications are not feasible. Second, in the selected approximate filtering method the query parameters are not matched directly to the document content but both are transformed to an abstract "concept space". This raises the question about the quality of the transformation. Third, the scalability of the p2p network is addressed by comparing the message rate of different publishing strategies. A lot of previous research exists m each of the three technical problem areas However, studies containing all three together are rare. Therefore, the method of the thesis is to review previous studies in different areas and select some alternatives for evaluation. The evaluation is performed experimentally by simulations and analytically whenever feasible. The results are compared in terms of the user experience (filtering quality) and network load (message rate)

Tilauspalvelusysteemit (publish/subscribe) ovat yleistymässä Internetissä johtuen käyttäjän tarpeesta rajoittaa informaatiotulvaa. Tilauspalvelu viittaa malliin, jossa vastaanottajat (tilaajat) määrittelevät haluamansa informaation sen sijaan, että lähettäjät (julkaisijat) päättävät siitä. Tämän mallin ongelmana on usein tilausehtojen määrittelyn vaikeus silloin kun käytetään sanatarkkaa määrittelytapaa. Käyttäjän voi olla mahdotonta löytää oikeita termejä tai kaikkia sen synonyymejä. Approksimoitu suodatus tähtää tämän ongelman ratkaisemiseen antamalla käyttäjälle liikkumavaraa ehtojen määrittelyssä. Tässä työssä tutkitaan tärkeimpiä ongelmia approksimoidun vapaan tekstisuodatuksen soveltamisessa tilauspalvelumalliin vertaisverkoissa. Approksimoidussa suodatuksessa tilaaja hyväksyy dokumentin silloin kun se on riittävän samankaltainen tilausehtojen kanssa valitun mittarin mukaan. Tilausehto voi olla sanoja, fraaseja tai jopa tekstidokumentti, ja tilauspalvelusysteemin tehtävänä on löytää samankaltaiset dokumentit ja lähettää tilaajien herätteet. Vertaisverkossa dokumentit saapuvat ja hakuehtoja talletetaan kaikissa solmuissa, mutta käyttäjä haluaa relevantit dokumentit riippumatta niiden sijainnista, mistä johtuva "rendezvous" ongelma on systeemin ratkaistava tehokkaasti. Kolmea teknistä ongelma-aluetta tarkastellaan. Ensiksi, tilauspalvelumalliin liittyy käänteisen haun ongelma, eli jokaista dokumenttia verrataan kaikkiin talletettuihin kyselyihin kerrallaan eikä päinvastoin. Tietokantoja ja informaation hakua varten kehitetyt ratkaisut eivät siten ole käyttökelpoisia. Toiseksi, approksimoidussa suodatuksessa hakuehtoja ei verrata suoraan dokumentin tekstiin. Sen sijaan molemmat muunnetaan abstraktiin "käsiteavaruuteen". Kolmanneksi, vertaisverkon skaalautuvuutta tutkitaan vertailemalla erilaisten julkaisumenetelmien tuottamia sanomamääriä. Paljon aikaisempaa tutkimusta on olemassa kustakin kolmesta teknisestä ongelma-alueesta. Kuitenkin tutkimukset, jotka kattavat kaikki kolme yhdessä, ovat harvinaisia. Sen vuoksi työn metodina on tarkastella aiempia tutkimuksia eri osa-alueilta ja valita joitakin vaihtoehtoja evaluoitavaksi. Tämä evaluointi suoritetaan kokeellisesti simuloimalla ja analyyttisesti laskemalla silloin kun se on mahdollista. Tuloksia vertaillaan sekä käyttäjän kannalta (suodatuksen laatu) että verkon näkökulmasta (sanomamäärä).

Description

Supervisor

Kantola, Raimo

Thesis advisor

Beijar, Nicklas

Keywords

publish/subscribe, tilauspalvelu, approximate filtering, approksimoitu suodatus, document clustering, dokumenttiklusteri, peer-to-peer network, vertaisverkko

Other note

Citation

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202104156028

Collections

[lic] Sähkötekniikan korkeakoulu / ELEC