David Eppstein - Publications

• 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.
  Lecture Notes in Comp. Sci. 4619, 2007, pp. 637-648, © Springer-Verlag.
  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.

  (WADS talk slides)

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

Semi-automatically filtered from a common source file.