...researching fundamentals of networking and communications


Wrap Filters - A new non-interactive method to determine sizes of deviation between similar data sets - 02/28/2002

Sachin Agarwal

In many problems related to computer networks and database consistency in lazy replication of distributed databases, it is important to gauge the extent of dissimiliarity between two datasets in order to make intelligent decisions about when to initiate synchronization procedures and to estimate the level of deviation in databases that are only weakly consistent. We propose, describe and analyze a new algorithm based on "Wrap Filters" to estimate this information. Our scheme has low communication complexity and requires only one round of communication in order for two hosts to determine an estimate of the size of the difference between them. Moreover, the information exchanged may also be used as a normal bloom filter to estimate what set elements the local set has that the remote host's set does not. We are thus able to extend the functionality of the bloom filter and make it more informative, at a modest cost in terms of the computation and communication.

r1 - 2008-09-05 - 23:00:05 - WeiyaoXiao

Laboratory of Networking and Information Systems
Photonics Building, Room 413
8 St Mary's Street,
Boston MA 02215

Initial web site created by Sachin Agarwal (ska@alum.bu.edu), Modified by Weiyao Xiao (weiyao@alum.bu.edu), Moved to TWiki backend by Ari Trachtenberg (trachten@bu.edu). Managed by Jiaxi Jin (jin@bu.edu).
Syndicate this site RSSATOM