3rd International ICST Conference on Collaborative Computing: Networking, Applications and Worksharin

Research Article

A Random Projection Approach to Subscription Covering Detection in Publish/Subscribe Systems

  • @INPROCEEDINGS{10.1109/COLCOM.2007.4553856,
        author={Duc  A. Tran and Thinh Nguyen},
        title={A Random Projection Approach to Subscription Covering Detection in Publish/Subscribe Systems},
        proceedings={3rd International ICST Conference on Collaborative Computing: Networking, Applications and Worksharin},
        publisher={IEEE},
        proceedings_a={COLLABORATECOM},
        year={2008},
        month={6},
        keywords={Computer science  Data structures  Detection algorithms  Organizing  Routing  Scalability  Subscriptions},
        doi={10.1109/COLCOM.2007.4553856}
    }
    
  • Duc A. Tran
    Thinh Nguyen
    Year: 2008
    A Random Projection Approach to Subscription Covering Detection in Publish/Subscribe Systems
    COLLABORATECOM
    IEEE
    DOI: 10.1109/COLCOM.2007.4553856
Duc A. Tran1,*, Thinh Nguyen2,*
  • 1: Department of Computer Science, University of Massachusetts, Boston, MA 02125
  • 2: Department of Electrical and Computer Engineering, Oregon State University, Corvallis, OR 97331
*Contact email: duc@cs.umb.edu, thinhq@eecs.oregonstate.edu

Abstract

Subscription covering detection is useful to improving the performance of any publish/subscribe system. However, an exact solution to querying coverings among a large set of subscriptions in high dimension is computationally too expensive to be practicable. Therefore, we are interested in an approximate approach. We focus on spherical subscriptions and propose a solution based on random projections. Our complexities are substantially better than that of the exact approach. The proposed solution can potentially find exact coverings with a success probability 100% asymptotically approachable.