Bibliography

[ADRR04]

G. Aggarwal, M. Data, S. Rajagopalan and M. Ruhl, "On the Streaming Model Augmented with a Sorting Primitive." In FOCS 04.

[AMS96]

N. Alon, Y. Matias and M. Szegedy, "The space complexity of approximating the frequency moments." In JCSS 99 (prelim. version STOC 96).

[BBDMW02]

B. Babcock, S. Babu, M. Datar, R. Motwani and J. Widom, "Models and Issues in Data Stream Systems." In PODS 02.

[BJKS02]

Z. Bar-Yossef, T. S. jayram, R. Kumar and D. Sivakumar, "Information theory methods in communication complexity." In FOCS 02.

[BJKST02]

Z. Bar-Yossef, T. S. Jayram, R. Kumar, D. Sivakumar and L. Trevisan, "Counting distinct elements in a data stream." In RANDOM 02.

[BFRSW00]

T. Batu, L. Fortnow, R. Rubinfeld, W. D. Smith and P. White, "Testing That Distributions Are Close." In FOCS 00.

[BJR07]

P. Beame, T. S. Jayram and A. Rudra, "Lower Bounds for Randomized Read/Write Stream Algorithms." In STOC 07.

[CCM07]

A. Chakrabarti, G. Cormode and A. Mcgregor, " A Near-Optimal Algorithm for Computing the Entropy of a Stream." In SODA 07.

[CJP08]

A. Chakrabarti, T. S. Jayram and M. Patrascu, " Tight Lower Bounds for Selection in Randomly Ordered Streams." In SODA 08.

[CKS03]

A. Chakrabarti, S. Khot and X. Sun, "Near-Optimal Lower Bounds on the Multi-Party Communication Complexity of Set Disjointness." In CCC 03.

[CK06]

Kevin L. Chang , Ravi Kannan, The space complexity of pass-efficient algorithms for clustering, In SODA 06.

[CM05]

G. Cormode, S. Muthukrishan. Space Efficient Mining of Multigraph Streams. PODS 2005

[COR03]

M. Charikar, L. O'Callaghan and R. Panigrahy, "Better Streaming Algorithms for Clustering Problems." In STOC 03.

[CCF02]

M. Charikar, K. Chen and M. Farach-Colton, "Finding Frequent Items in Data Streams." In ICALP 02.

[CS06]

E. Cohen and M. Strauss, "Maintaining Time-Decaying Stream Aggregates." In JoA 06.

[CKT08]

G. Cormode, F. Korn and S. Tirthapua, "Exponentially decayed aggregates on data streams." In ICDE 08.

[CM03]

G. Cormode and S. Muthukrishnan, "What is hot and what is not: Tracking most frequent items dynamically." In PODS 03.

[DGIM02]

M. Datar, A. Gionis, P. Indyk and R. Motwani, "Maintaining Stream Statistics over Siliding Windows." In SICOMP 02 (prelim. version in SODA 02).

[DG04]

J. Dean and S. Ghemawat, "MapReduce: Simplified Data Processing on Large Clusters." In OSDI 04.

[DLM02]

E. Demaine, A. López-Ortiz and J. I. Munro, "Frequency Estimation of Internet Packet Streams with Limited Space." In ESA 02.

[FKMSZ04] 

        J. Feigenbaum, S. Kannan, A. McGregor, S. Suri, and J. Zhang. On graph problems in a semi-streaming model. In Proceedings of the International Colloquium on Automata, Languages, and Programming, 2004. (ICALP'04)

[FKMSZ05]
        J. Feigenbaum, S. Kannan, A. McGregor, S. Suri, and J. Zhang. Graph distances in the streaming model: The value of space. In Proceedings of ACM-SIAM Symposium on Discrete Algorithms, 2005. (SODA'05)

[FMSSS06]

J. Feldman, S. Muthukrishnan, A. Sidiropoulos, C. Stein and Z. Svitkina, "On the Complexity of Processing Massive, Unordered, Distributed Data." Manuscript, 2007.

[GM99]

P. B. Gibbons and Y. Matias, "Synopsis Data Structures for Massive Data Sets." In SODA 99.

[GT04]

P. B. Gibbons and S. Tirthapura, "Distributed Streams Algorithms for Sliding Windows." In Theory of Comp. Sys. 04.

[GGIKMS02]

A. C. Gilbert, S. Guha, P. Indyk, Y. Kotidis, S. Muthukrishnan and M. J. Strauss, "Fast, small space algorithms for approximate histogram maintenance." In STOC 02.

[GK01]

M. Greenwald and S. Khanna, "Space-Efficient Online Computation of Quantile Summaries." In SIGMOD 01.

[GHS06]

M. Grohe, A. Hernich and N. Schweikardt, "Randomized Computations on Large Data Sets: Tight Lower Bounds." In PODS 06.

[GKS05]

M. Grohe, C. Koch and N. Schweikardt, "Tight Lower Bounds for Query Processing on Streaming and External Memory Data External Memory." In TCS 07 (prelim. version ICALP 05).

[GS05]

M. Grohe and N. Schweikardt, "Lower Bounds for Sorting with Few Random Accesses to External Memory." In PODS 05.

[GMMMO03]

S. Guha, A. Meyerson, N. Mishra, R. Motwani and L. O'Callaghan, " Clustering Data Streams: Theory and Practice." In IEEE Trans. Knowl. Data Eng. 03.

[HRR98]

M. R. Henzinger, P. Raghavan and S. Rajagopalan, "Computing on Data Streams." DEC tech. report 98.

[I00]

P. Indyk, "Stable Distributions, Pseudorandom Generators, Embeddings and Data Stream Computation." In JACM 06 (prelim. version in FOCS00).

[IM08]

P. Indyk and A. McGregor, "Declaring Independence via the Sketching of Sketches." In SODA 08.

[IW03]

P. Indyk and D. Woodruff, "Tight Lower Bounds for the Distinct Elements Problem." In FOCS 03.

[IW05]

P. Indyk and D. Woodruff, "Optimal Approximations of the Frequency Moments of Data Streams." In STOC 05.

[JKV07]

T. S. Jayram, S. Kale and E. Vee, "Efficient Aggregation Algorithms for Probabilistic Data." In SODA 07.

[KSP03]

R. M. Karp, S. Shenker and C. H. Papadimitriou, "A Simple Algorithm for Finding Frequent Elements in Streams and Bags." In TODS 03.

[KSS02]

F. Korn, S. Muthukrishnan and D. Srivastava, "Reverse nearest neighbor aggregates over data streams." In VLDB 02.

[LSOXZ06]

A. Lall, V. Sekar, M. Ogihara, J. Xu, and H. Zhang. Data streaming algorithms for estimating entropy of network traffic. In ACM SIGMETRICS, 2006

[MM02]

G. S. Manku and R. Motwani, "Approximate Frequency Counts over Streaming Data." In VLDB 02.

[MAA05]

A. Metwally, D. Agrawal and A. E. Abbadi, "Efficient Computation of Frequent and Top-k Elements in Data Streams." In ICDT 05.

[MG82]

J. Misra and D. Gries, "Finding Repeated Elements." In Science of Comp. Prog. 82.

[MP78]

I. Munro and M. Paterson, "Selection and Sorting with Limited Storage." In TCS 80 (prelim. version in FOCS 78)

[R03]

M. Ruhl, "Efficient Algorithms for New Computational Models." MIT thesis 03.

[VSGB05]

S. Venkataraman, D. Song, P. B. Gibbons, and A. Blum. New Streaming Algorithms for Fast Detection of Superspreaders . In Proceedings of Network and Distributed System Security Symposium (NDSS), 2005.

[W04]

D. Woodruff, "Optimal Space Lower Bounds for all Frequency Moments." In SODA 04.

[W07]

D. Woodruff, "Efficient and Private Distance Approximation in the Communication and Streaming Models." MIT thesis 07.