Naslov Top-k Publish/Subscribe Matching Model Based on Sliding Window Naslov (hrvatski) Model usporedbe ”k-najboljih” u sustavima objavi-pretplati temeljen na
klizećem prozoru Autor Krešimir Pripužić Mentor Ivana Podnar Žarko (mentor)Mentor Karl Aberrer (komentor) Član povjerenstva Bojana Dalbelo Bašić (predsjednik povjerenstva)Član povjerenstva Ignac Lovrek (član povjerenstva)Ustanova koja je dodijelila Sveučilište u Zagrebu Datum i država obrane 2010-06-15, Hrvatska Znanstveno / umjetničko TEHNIČKE ZNANOSTI Univerzalna decimalna klasifikacijaUDC ) 004 - Računalna znanost i tehnologija. Računalstvo. Obrada podataka Sažetak In this thesis we present the top-k/w matching model, a novel publish/subscribe matching model which
enables a subscriber to control the number of publications it will receive per subscription within a predefined
time period. In this model, each subscription defines an arbitrary and time-independent scoring
function and parameters k and window-size w such that, at a point in time t, parameter k restricts the
number of delivered publications to the k best scored publications that are published between t-w and t.
We propose novel algorithms for efficient top-k/w processing in environments publishing data objects
at high rates. Existing solutions are typically tailored to specific scoring functions, and thus we define
a generic data stream processing model that is independent of data representation and scoring functions.
Our complexity analysis and extensive comparative evaluation show that our algorithms significantly
outperform the competing approaches in both memory consumption and processing efficiency.
For each of the commonly used routing strategies in both centralized and distributed environments
we explain how it can be adapted to support the proposed top-k/w matching model. We identify and
evaluate routing strategies which are particularly well suited for large-scale top-k/w publish/subscribe
systems. Additionally, we present D-ZaLaPS, a distributed top-k/w publish/subscribe system based on a
peer-to-peer structured overlay. The experimental evaluation shows that D-ZaLaPS is scalable both for
increasing number of peers and subscriptions.
Finally, using the case study with k-nearest neighbor subscriptions, we experimentally evaluate and
compare the top-k/w and Boolean matching models. This experimental evaluation shows that, assuming
the subscribers are interested in top-k publications in the sliding window, the top-k/w matching model
can significantly reduce message overhead in the system when compared to the Boolean matching model,
and this, together with built-in support for flexible subscriptions and control of the number of matching
publications in the top-k/w model, represents a significant enhancement of publish/subscribe systems.
Sažetak (hrvatski) Ova disertacija predlaže novi model usporedbe u sustavima objavi-pretplati koji omogućava korisnicima da po svakoj svojoj pretplati kontroliraju broj objava koje žele primiti u odabranom vremenskom intervalu. U ovom modelu usporedbe, pretplate definiraju funkciju za rangiranje objava, parametar k te veličinu vremenskog prozora w. U bilo kojem trenutku t, parametar k ograničava broj isporučenih objava na k najbolje rangiranih od onih koje su objavljene u periodu između t-w i t. U disertaciji se predlaže nekoliko različitih algoritama za obradu ove vrste pretplata u slučaju velikog intenziteta objavljivanja. Iz razloga što u literaturi ne postoje općenita rješenja, već su sva postojeća namijenjena strogo specifičnim funkcijama rangiranja, u disertaciji se predlaže općeniti model obrade ove vrste pretplata koji je u potpunosti neovisan o vrsti podataka i odabranoj funkciji rangiranja. Rezultati eksperimentalne evaluacije i analize složenosti algoritama pokazuju da su predloženi algoritmi znatno učinkovitiji pri odradi podataka te da zauzimaju manje radne memorije od postojećih rješenja. U disertaciji se predlažu i objašnjavaju preinake uobičajenih strategija usmjeravanja u centraliziranim i raspodijeljenim sustavima objavi-pretplati koje su neophodne za podršku predloženog modela usporedbe. Također se identificiraju strategije koje su posebno pogodne za izvedbu sustava objavi-pretplati koji imaju veliki broj korisnika i podržavaju predloženi model usporedbe. U disertaciji se predstavlja jedan takav sustav temeljen na prekrivajućoj mreži istovrsnih čvorova. Rezultati eksperimentalne evaluacije pokazuju da je ovaj sustav skalabilan pri povećanju broja čvorova i pretplata u sustavu. Eksperimentalna evaluacija na odabranom studijskom primjeru pokazuje da se broj razmijenjenih poruka u sustavu objavi-pretplati može značajno smanjiti ukoliko se umjesto postojećeg koristi predloženi model usporedbe, što zajedno s fleksibilnošću pretplata i ugrađenom kontrolom intenziteta isporučenih objava u ovom modelu predstavlja značajno poboljšanje sustava objavi-pretplati.
Ključne riječi
data stream processing
publish/subscribe
event-based systems
top-k
sliding-window
Ključne riječi (hrvatski)
procesiranje toka podataka
objavi-pretplati
k-najboljih
klizeći prozor
Jezik engleski URN:NBN urn:nbn:hr:168:507965 Datum promocije 2010 Studijski program Naziv: Računarstvo Vrsta resursa Tekst Opseg xvii, 173 str. : graf. prikazi Način izrade datoteke Izvorno digitalna Prava pristupa Otvoreni pristup Uvjeti korištenja Datum i vrijeme pohrane 2024-03-20 12:58:39
