University of Illinois Urbana-Champaign

Conformance preserving data dissemination for large-scale peer to peer systems

Chen, Liping

Content Files
Chen_Liping.pdf

Permalink

https://hdl.handle.net/2142/26088

Description

Title
Conformance preserving data dissemination for large-scale peer to peer systems
Author(s)
Chen, Liping
Issue Date
2011-08-25T22:12:31Z
Director of Research (if dissertation) or Advisor (if thesis)
Agha, Gul A.
Doctoral Committee Chair(s)
Agha, Gul A.
Committee Member(s)
  • Campbell, Roy H.
  • Gupta, Indranil
  • Zhu, Feida
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Date of Ingest
2011-08-25T22:12:31Z
Keyword(s)
  • Data Dissemination
  • Peer to Peer Systems
  • Dynamic Filters
  • Large Scale
  • Conformance Threshold
Abstract
In today's applications where dealing with vast stream data becomes a norm rather than an exception, it is in urgent need to design data dissemination systems in large scale. We identify a new pattern of data dissemination based on conformance constraints where data accuracy can be traded for low bandwidth. We formally define the problem of conformance preserving data dissemination and address two types of conformance data dissemination problems that we are interested in: data dissemination based on simple subscriptions and data dissemination based on composite subscriptions. For simple subscriptions, we propose a Multilevel Cooperative Filter (MCF) overlay. We describe an online greedy algorithm to compute the minimum-size data sequence for dissemination and prove that it gives the optimal approximation ratio to the optimal off-line solution for all deterministic online algorithms. We then show that our multilevel cooperative filter algorithm generates the same dissemination sequence as the online greedy algorithm, thus proving the optimality of our approach. We further prove the NP-hardness of the filter overlay construction and give a O(ln n)-approximation algorithm to minimize the level-wise communication cost. We extend the model to support a richer and more expressive subscription semantics, allowing the user interest to be specified as arbitrary conformance predicates combined using logical operators on multiple data sources. Through Disjunctive Normal Form (DNF) transformation, arbitrary composite filters are decomposed into conjunctive filters. We then use a hybrid method based on filtering strength to support these conjunctive filters with low communication cost and low latency. We have built a stock monitoring application using real life stock quotes collected from Yahoo Finance to evaluate the performance. A variety of experiments have been conducted to verify our design choices and deepen our understanding of the impact of various system parameters on both application-level and network-level performances. The simulation results suggest that the approaches are feasible to be deployed in large scale networks.
Graduation Semester
2011-08
Permalink
http://hdl.handle.net/2142/26088
Copyright and License Information
Copyright 2011 Liping Chen

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois
Dissertations and Theses - Computer Science
Dissertations and Theses from the Siebel School of Computer Science