**Space-efficient straggler identification in round-trip data streams via Newton's identitities and invertible Bloom filters.**

D. Eppstein, and M. T. Goodrich.

*10th Worksh. Algorithms and Data Structures,*Halifax, Nova Scotia, 2007.

Springer,*Lecture Notes in Comp. Sci.*4619, 2007, pp. 637–648.

arXiv:0704.3313.

*IEEE Trans. Knowledge and Data Engineering*23 (2): 297–306, 2011.We consider data structures for handling streams of check-in and check-out requests, and that must identify the set of check-ins that are not matched by a corresponding check-out. We show that, if this set has size k, it is possible to handle this problem in space O(k log n) by a deterministic data structure. However, if check-outs may occur that do not match any check-in, then no low-space deterministic solution is possible; instead, we provide a randomized solution with near-optimal space and high probability of answering queries correctly.

Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.