Computing on data streams
Monika Rauch Henzinger, Prabhakar Raghavan, Sridhar Rajagopalan · DIMACS series in discrete mathematics and theoretical computer science · 1999
In this paper we study the space requirement of algorithms that make only one (or a small number of) pass(es) over the input data. We study such algorithms under a model of data streams that we introduce here. We give a number of upper and lower bounds for problems stemming from queryprocessing, invoking in the process tools from the area of communication complexity. 1
Cited by 418 works. doi:10.1090/dimacs/050/05
Authors
References
- Access path selection in a relational database management system
- Amortized efficiency of list update and paging rules
- Some complexity questions related to distributive computing(Preliminary Report)
- Syntactic clustering of the Web
- Competitive snoopy caching
- Communication Complexity
- The space complexity of approximating the frequency moments
- Improved histograms for selectivity estimation of range predicates
- Applications of a Web query language
- Lore