Top-k Publish/Subscribe Matching Model Based on Sliding Window

doctoral thesis

• Title (croatian): Model usporedbe ”k-najboljih” u sustavima objavi-pretplati temeljen na klizećem prozoru
• Author: Krešimir Pripužić
• Mentor: Ivana Podnar Žarko (mentor)
• Mentor: Karl Aberrer (komentor); strani drzavljanin: Nije dostupno
• Committee member: Bojana Dalbelo Bašić (predsjednik povjerenstva)
• Committee member: Ignac Lovrek (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2010-06-15, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing
• Universal decimal classification (UDC): 004 - Computer science and technology. Computing. Data processing

Abstract

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.

Abstract (croatian)

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.

• Keywords: data stream processing; publish/subscribe; event-based systems; top-k; sliding-window
• Keywords (croatian): procesiranje toka podataka; objavi-pretplati; k-najboljih; klizeći prozor
• Language: english
• URN:NBN: urn:nbn:hr:168:507965
• Promotion: 2010
• Study programme: Title: Computer Science; Study programme type: university; Study level: postgraduate; Academic / professional title: Doktor znanosti (Doktor znanosti)
• Type of resource: Text
• Extent: xvii, 173 str. : graf. prikazi
• File origin: Born digital
• Access conditions: Open access
• Created on: 2024-03-20 12:58:39