Efficient Covering for Top-k Filtering in Content-Based Publish/Subscribe Systems

Kaiwen Zhang, Vinod Muthusamy, Mohammad Sadoghi, and Hans-Arno Jacobsen.

University of Toronto, 2016.

Abstract

Large-scale applications require a scalable data dissemination service with advanced filtering capabilities. We propose the use of a content-based publish/subscribe system with support for top-k filtering in the context of such applications. We focus on the problem of top-k subscription filtering, where a publication is delivered only to the k best ranked subscribers. The naive approach to perform filtering early at the publisher edge works only if complete knowledge of the subscriptions is available, which is not compatible with the well-established covering optimization in scalable content-based publish/subscribe systems. We propose an efficient rank-cover technique to reconcile top-k subscription filtering with covering. We extend the covering model to support top-k and describe a novel algorithm for forwarding subscriptions to publishers while maintaining correctness. We also establish a framework for supporting different types of ranking semantics and propose an implementation to support fairness. Finally, we compare our solutions to a baseline covering system and perform sensitivity analysis to demonstrate that our optimized rank-cover algorithm retains both covering and fairness while achieving properties advantageous to our targeted workloads. Our optimized solution is scalable and provides over 81\% of the covering benefit when k is set at 1% selectivity.

Download



Tags: topk, content-based publish/subscribe, covering


Readers who enjoyed the above work, may also like the following:


  • Distributed Ranked Data Dissemination in Social Networks.
    Kaiwen Zhang, Mohammad Sadoghi, Vinod Muthusamy, and Hans-Arno Jacobsen.
    In 33rd IEEE International Conference on Distributed Computing Systems (ICDCS), 2013.
    Acceptance rate: 13%.
    Tags: aggregation, topk, content-based publish/subscribe, social networks
  • Distributed Ranked Data Dissemination in Social Networks.
    Kaiwen Zhang, Mohammad Sadoghi, Vinod Muthusamy, and Hans-Arno Jacobsen.
    University of Toronto, 2012.
    Tags: topk, publish/subscribe, aggregation
  • Total Order in Content-based Publish/Subscribe Systems.
    Kaiwen Zhang, Vinod Muthusamy, and Hans-Arno Jacobsen.
    In 32nd IEEE International Conference on Distributed Computing Systems (ICDCS), 2012.
    Acceptance rate: 13%.
    Tags: total order, content-based publish/subscribe