Naslov
Top-k/w Publish/Subscribe: Finding k Most Relevant Publications in Sliding Time Window w

Autori
Pripužić, Krešimir ; Podnar Žarko, Ivana ; Aberer, Karl

Vrsta, podvrsta i kategorija rada
Radovi u zbornicima skupova, cjeloviti rad (in extenso), znanstveni

Izvornik
Proceedings of the 2nd International conference on Distributed Event-based Systems (DEBS 2008) / Baldoni, Roberto ; Buchmann, Alejandro P. ; Tucci Piergiovanni, Sara ; Dekel, Eliezer ; Hinze, Annika ; Mühl, Gero ;  Querzoni, Leonardo ; Quéma, Vivien - New York (NY) : The Association for Computing Machinery (ACM), 2008, 127-138

ISBN
978-1-60558-090-6

Skup
The 2nd International Conference on Distributed Event-Based Systems (DEBS)

Mjesto i datum
Rim, Italija, 01.07.2008. - 04.07.2008

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Međunarodna recenzija

Ključne riječi
publish/subscribe; data stream processing; matching; relevance; probabilistic criterion

Sažetak
Existing content-based publish/subscribe systems are designed assuming that all matching publications are equally relevant to a subscription. As we cannot know in advance the distribution of publication content, the following two unwanted situations are highly possible: a subscriber either receives too many or only few publications. In this paper we present a new publish/subscribe model which is based on the sliding window computation model. Our model assumes that publications have different relevance to a subscription. In the model, a subscriber receives k most relevant publications published within a time window w, where k and w are parameters defined per each subscription. As a consequence, the arrival rate of incoming relevant publications per subscription is predefined, and does not depend on the publication rate. Since all relevant objects (i.e. publications in our case) cannot be kept in main memory, existing solutions immediately discard less relevant objects, and store only a small representative set for subsequent delivery. In this paper we develop a probabilistic criterion to decide upon the arrival of a new object whether it may become the top-k object at some future point in time and should thus be stored in a special publication queue. We show that by accepting typically very small probability of error, the queue length is reasonably small and does not significantly depend on publication rate. Furthermore, we xperimentally evaluate our approach to demonstrate its applicability in practice.

Izvorni jezik
Engleski

Znanstvena područja
Elektrotehnika, Računarstvo

POVEZANOST RADA