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

Chen, Liping

Permalink

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

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

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