More Stream Models
On doing literature search (aka catching up), I noticed some developments in data stream models.
- MUD (Massive, Unordered, Distributed) model is an abstraction of a special case of MapReduce. Most (approximate) streaming algorithms work in the MUD model immediately. A recent work by Nanongkai et al. in progress seems to generalize this to MUDB model (MUD with broadcasting) and studies graph problems that are difficult to solve in vanilla streaming or MUD model.
- Many have asked and formulated problems of how streams may be augmented with different types of annotations. Read/write annotations are a natural class, and recent results by Beame and Huynh-Ngoc on estimating freq moments in this model seem interesting.