Finding a Duplicate and a Missing Item in a Stream
Finding a Duplicate and a Missing Item in a Stream
复制标题
DOI：
10.1007/978-3-540-72504-6_11
复制
发表时间：
2007-05
期刊：
影响因子：
--
通讯作者：
J. Tarui
中科院分区：
文献类型：
--
作者：
J. Tarui
我们在流模型中考虑以下问题：给定一个序列，其中每个ai∈ [n] = {1,...,n}且m>n，在序列中找到重复项，即，通过使用有限的内存位和r遍输入序列来找到somed=ai=alwithi≠l。在 onepassan 算法中，按 a1,a2, ...,am 的顺序读取输入序列。由于m>n，根据鸽巢原理，存在重复项。 Muthukrishnan [Mu05a]，[Mu05b]针对m=n+ 1的情况提出了以下问题：Fors=O(logn)，是否有一个恒定次数的解决方案？我们已经通过将序列长度作为参数来描述概括 Muthukrishnan 问题的问题。我们通过以下方式给出原始问题的否定答案：假设m=n+ 1。具有O(logn)空间的流算法需要Ω(logn/loglogn)通过； ak-pass 流算法需要 Ω(n1/(2k− 1)) 空间。我们还考虑以下寻找缺失项的问题：假设n<m，找到x∈ [m]，使得x≠aj，对于1 ≤j≤n。相同的下限适用于丢失项目查找问题。证明是关系通信复杂性的简单降低。我们还考虑单遍算法并准确确定所需的最小空间。诸如以下的有趣的悬而未决的问题仍然存在。对于使用 O(logn) 空间的算法的传递次数，显示 ω(1) 下界（或 O(1) 上限）：(1) 重复查找形式= 2n，(2) 缺失项查找形式= 2n，以及 (3) 我们允许拉斯维加斯类型随机化形式=n+ 1 的情况。
We consider the following problem in a stream model: Given a sequencewich eachai∈ [n] = {1,...,n} andm>n, find aduplicatein the sequence, i.e., find somed=ai=alwithi≠lby using limitedsbits of memory andrpasses over the input sequence. In onepassan algorithm reads the input sequenceain the ordera1,a2, ...,am. Sincem>n, a duplicate exists by the pigeonhole principle. Muthukrishnan [Mu05a], [Mu05b] has posed the following question for the case wherem=n+ 1: Fors=O(logn), is there a solution with aconstantnumber of passes? We have described the problem generalizing Muthukrishnan’s question by taking the sequence lengthmas a parameter. We give a negative answer to the original question by showing the following: Assume thatm=n+ 1. A streaming algorithm withO(logn) space requiresΩ(logn/loglogn) passes; ak-pass streaming algorithm requiresΩ(n1/(2k− 1)) space. We also consider the following problem offinding a missing item: Assuming thatn<m, findx∈ [m] such thatx≠ajfor 1 ≤j≤n. The same lower bound applies for the missing-item finding problem. The proof is a simple reduction to the communication complexity of arelation. We also considerone-pass algorithms and exactly determine the minimum space required. Interesting open questions such as the following remain. For the number of passes of algorithms usingO(logn) space, show anω(1) lower bound (or anO(1) upper bound) for: (1) duplicate finding form= 2n, (2) missing-item finding form= 2n, and (3) the case where we allow Las-Vegas type randomization form=n+ 1.