Files in this item



application/pdfChen_Liping.pdf (946kB)
(no description provided)PDF


Title:Conformance preserving data dissemination for large-scale peer to peer systems
Author(s):Chen, Liping
Director of Research:Agha, Gul A.
Doctoral Committee Chair(s):Agha, Gul A.
Doctoral Committee Member(s):Campbell, Roy H.; Gupta, Indranil; Zhu, Feida
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(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.
Issue Date:2011-08-25
Rights Information:Copyright 2011 Liping Chen
Date Available in IDEALS:2011-08-25
Date Deposited:2011-08

This item appears in the following Collection(s)

Item Statistics