Recent results on processing random-order streams and space-efficient sampling
Andrew McGregor · 2008
The data-stream model is a model of computation that has attracted significant attention over the last twenty years because of its applicability to a variety of problems including network monitoring, database query planning, and processing massive data sets residing in external memory. The model is also theoretically appealing and much of the research in the area has strong links to other areas of active research including compressed sensing, communication complexity, online algorithms, and metric embeddings. In this paper, we overview some of the recent research that has explored how the computational resources required to solve various problems in this model are dependent on how the data stream is ordered, specifically whether the order is chosen adversarially or uniformly at random.