首页> 外文期刊>Knowledge and Data Engineering, IEEE Transactions on >Straggler Identification in Round-Trip Data Streams via Newton's Identities and Invertible Bloom Filters
【24h】

Straggler Identification in Round-Trip Data Streams via Newton's Identities and Invertible Bloom Filters

机译:通过牛顿身份和可逆布隆过滤器识别来回行程数据流中的跨行者

获取原文
获取原文并翻译 | 示例

摘要

In this paper, we study the straggler identification problem, in which an algorithm must determine the identities of the remaining members of a set after it has had a large number of insertion and deletion operations performed on it, and now has relatively few remaining members. The goal is to do this in o(n) space, where n is the total number of identities. Straggler identification has applications, for example, in determining the unacknowledged packets in a high-bandwidth multicast data stream. We provide a deterministic solution to the straggler identification problem that uses only O(dlog n) bits, based on a novel application of Newton''s identities for symmetric polynomials. This solution can identify any subset of d stragglers from a set of n O(log n)-bit identifiers, assuming that there are no false deletions of identities not already in the set. Indeed, we give a lower bound argument that shows that any small-space deterministic solution to the straggler identification problem cannot be guaranteed to handle false deletions. Nevertheless, we provide a simple randomized solution, using O(dlog nlog (1/epsilon )) bits that can maintain a multiset and solve the straggler identification problem, tolerating false deletions, where epsilon >0 is a user-defined parameter bounding the probability of an incorrect response. This randomized solution is based on a new type of Bloom filter, which we call the invertible Bloom filter.
机译:在本文中,我们研究了散乱识别问题,在该问题中,算法必须对集合执行大量插入和删除操作,而现在剩余成员相对较少之后,才能确定集合中剩余成员的身份。目的是在o(n)空间中执行此操作,其中n是身份的总数。跨行者识别具有例如在确定高带宽多播数据流中未确认的数据包方面的应用。我们基于牛顿恒等式在对称多项式上的新应用,为仅使用O(dlog n)位的散布者识别问题提供了确定性解决方案。该解决方案可以从一组n个O(log n)位标识符中识别出d散乱者的任何子集,假设不存在对该集合中尚未存在的身份的错误删除。确实,我们给出了一个下界论证,该论证表明,不能保证对散杂身份识别问题的任何小空间确定性解决方案都可以处理错误的删除。但是,我们提供了一个简单的随机解决方案,使用O(dlog nlog(1 / epsilon))位可以维护多集并解决散杂的标识问题,可以容忍错误删除,其中epsilon> 0是用户定义的参数,限制了概率错误的响应。这种随机解决方案基于一种新型的布隆过滤器,我们将其称为可逆布隆过滤器。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号