# Bibliography

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Citations: Write {{cite|paper_id_1|paper_id_2||paper_id_k}} to cite papers paper_id_1, paper_id_2, …, paper_id_k. For instance, {{cite|AlonMS-99|BlumLR-93}} results in [AlonMS-99,BlumLR-93].

[AlonMS-99]
Noga Alon, Yossi Matias, Mario Szegedy. The Space Complexity of Approximating the Frequency Moments. J. Comput. Syst. Sci. 58(1), pages 137-147, 1999.
[AndoniIK-09]
Alexandr Andoni, Piotr Indyk, and Robert Krauthgamer. Overcoming the $\ell_1$ non-embeddability barrier: algorithms for product metrics. In ACM-SIAM Symposium on Discrete Algorithms, pages 865-874, 2009.
[AndoniJP-10]
Alexandr Andoni, T. S. Jayram, and Mihai Patrascu. Lower bounds for edit distance and product metrics via Poincaré-type inequalities. In ACM-SIAM Symposium on Discrete Algorithms, pages 184-192, 2010.
[AndoniN-12]
Alexandr Andoni, Huy L. Nguyen. Width of points in the streaming model. In ACM-SIAM Symposium on Discrete Algorithms, pages 447-452, 2012.
[AndoniO-09]
Alexandr Andoni and Krzysztof Onak. Approximating edit distance in near-linear time. In ACM Symposium on Theory of Computing, pages 199-204, 2009.
[BarYossefJKST-02]
Ziv Bar-Yossef, T.S. Jayram, Ravi Kumar, D. Sivakumar, and Luca Trevisan. Counting distinct elements in a data stream. In Proc. 6th International Workshop on Randomization and Approximation Techniques in Computer Science, pages 1-10, 2002.
[BarYossefKS-02]
Ziv Bar-Yossef, Ravi Kumar, and D. Sivakumar. Reductions in streaming algorithms, with an application to counting triangles in graphs. In ACM-SIAM Symposium on Discrete Algorithms, pages 623-632, 2002.
[Baswana-06]
Surender Baswana. Faster streaming algorithms for graph spanners. 2006.
[BerindeIR-08]
Radu Berinde, Piotr Indyk, and Milan Ruzic. Practical near-optimal sparse recovery in the $l_1$ norm. Allerton, 2008.
[BhattacharyyaMMY-07]
S. Bhattacharyya, A. Madeira, S. Muthukrishnan, and T. Ye. How to scalably skip past streams. In WSSP (Workshop with ICDE), 2007.
[BhuvanagiriG-06]
Lakshminath Bhuvanagiri and Sumit Ganguly. Estimating entropy over data streams. In ESA, pages 148--159, 2006.
[BhuvanagiriGKS-06]
Lakshminath Bhuvanagiri, Sumit Ganguly, Deepanjan Kesh, and Chandan Saha. Simpler algorithm for estimating frequency moments of data streams. In ACM-SIAM Symposium on Discrete Algorithms, pages 708-713, 2006.
[BlumLR-93]
Manuel Blum, Michael Luby, Ronitt Rubinfeld. Self-Testing/Correcting with Applications to Numerical Problems. J. Comput. Syst. Sci. 47(3), pages 549-595, 1993.
[BroderCFM-00]
Andrei Z. Broder, Moses Charikar, Alan M. Frieze, and Michael Mitzenmacher. Min-wise independent permutations. J. Comput. Syst. Sci., 60(3), pages 630-659, 2000.
[BuriolFLMS-06]
Luciana S. Buriol, Gereon Frahling, Stefano Leonardi, Alberto Marchetti-Spaccamela, and Christian Sohler. Counting triangles in data streams. In ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pages 253-262, 2006.
[CandesRT-06]
Emmanuel J. Candès, Justin K. Romberg, and Terence Tao. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on Information Theory, 52(1):489-509, 2006.
[ChakrabartiCM-07]
Amit Chakrabarti, Graham Cormode, and Andrew McGregor. A near-optimal algorithm for computing the entropy of a stream. In ACM-SIAM Symposium on Discrete Algorithms, pages 328-335, 2007.
[Charikar-02]
Moses Charikar. Similarity estimation techniques from rounding algorithms. In STOC, pages 380-388, 2002.
[CormodeDIM-03]
Graham Cormode, Mayur Datar, Piotr Indyk, and S. Muthukrishnan. Comparing data streams using hamming norms (how to zero in). IEEE Trans. Knowl. Data Eng., 15(3), pages 529-540, 2003.
[CormodeKMS-06]
Graham Cormode, Flip Korn, S. Muthukrishnan, and Divesh Srivastava. Space- and time-efficient deterministic algorithms for biased quantiles over data streams. In PODS, pages 263-272, 2006.
[CormodeM-05]
Graham Cormode and S. Muthukrishnan. An improved data stream summary: the count-min sketch and its applications. J. Algorithms, 55(1), pages 58-75, 2005.
[CormodeM-05a]
Graham Cormode and S. Muthukrishnan. What's new: finding significant differences in network data streams. IEEE/ACM Trans. Netw., 13(6), pages 1219-1232, 2005.
[CormodeM-05b]
Graham Cormode and S. Muthukrishnan. Space efficient mining of multigraph streams. In ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pages 271-282, 2005.
[CormodeM-06]
Graham Cormode and S. Muthukrishnan. Combinatorial algorithms for compressed sensing.In Paola Flocchini and Leszek Gasieniec, editors, Structural Information and Communication Complexity, 13th International Colloquium, SIROCCO 2006, Chester, UK, July 2-5, 2006, Proceedings, volume 4056 of Lecture Notes in Computer Science, pages 280-294. Springer, 2006.
[DasSarmaGP-08]
Atish Das Sarma, Sreenivas Gollapudi, and Rina Panigrahy. Estimating PageRank on graph streams. In PODS, pages 69-78, 2008.
[DeanG-04]
Jeffrey Dean and Sanjay Ghemawat. MapReduce: Simplified data processing on large clusters. In OSDI, pages 137-150, 2004.
[DemaineLM-02]
Erik D. Demaine, Alejandro López-Ortiz, and J. Ian Munro. Frequency estimation of internet packet streams with limited space. In ESA, pages 348-360, 2002.
[DemetrescuFR-06]
Camil Demetrescu, Irene Finocchi, and Andrea Ribichini. Trading off space for passes in graph streaming problems. In ACM-SIAM Symposium on Discrete Algorithms, pages 714-723, 2006.
[Donoho-06]
David L. Donoho. Compressed sensing. IEEE Transactions on Information Theory, 52(4):1289-1306, 2006.
[DrakeH-03]
Doratha E. Drake and Stefan Hougardy. Improved linear time approximation algorithms for weighted matchings. In RANDOM-APPROX, pages 14-23, 2003.
[DrineasMM-06]
Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan. Sampling algorithms for $\ell_2$ regression and applications. In ACM-SIAM Symposium on Discrete Algorithms, pages 1127-1136, 2006.
[DrineasMM-06a]
Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan. Subspace sampling and relative-error matrix approximation: Column-based methods. In APPROX-RANDOM, pages 316-326, 2006.
[DrineasMM-06b]
Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan. Subspace sampling and relative-error matrix approximation: Column-row-based methods. In ESA, pages 304-314, 2006.
[Edmonds-65]
Jack Edmonds. Maximum matching and a polyhedron with 0,1-vertices. J. Res. Nat. Bur. Standards, 69(B):125-130, 1965.
[Elkin-06]
Michael Elkin. A near-optimal fully dynamic distributed algorithm for maintaining sparse spanners. 2006.
[ElkinZ-06]
Michael Elkin and Jian Zhang. Efficient algorithms for constructing $(1+\epsilon, \beta)$-spanners in the distributed and streaming models. Distributed Computing, 18(5):375-385, 2006.
[FeigenbaumKMSZ-05]
Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. Graph distances in the streaming model: the value of space. In ACM-SIAM Symposium on Discrete Algorithms, pages 745-754, 2005.
[FeigenbaumKMSZ-05a]
Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. On graph problems in a semi-streaming model. Theoretical Computer Science, 348(2-3):207-216, 2005.
[FeigenbaumKMSZ-08]
Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. Graph distances in the data-stream model. SIAM J. Comput., 38(5):1709-1727, 2008.
[FeigenbaumKSV-02]
Joan Feigenbaum, Sampath Kannan, Martin Strauss, and Mahesh Viswanathan. An approximate $L^1$ difference algorithm for massive data streams. Journal on Computing, 32(1), pages 131-151, 2002.
[FeldmanMSSS-06]
Jon Feldman, S. Muthukrishnan, Anastasios Sidiropoulos, Cliff Stein, and Zoya Svitkina. On the complexity of processing massive, unordered, distributed data. 2006.
[FeldmanMSSS-10]
Jon Feldman, S. Muthukrishnan, Anastasios Sidiropoulos, Clifford Stein, and Zoya Svitkina. On distributing symmetric streaming computations. ACM Transactions on Algorithms, 6(4), 2010.
[GabizonH-10]
Ariel Gabizon and Avinatan Hassidim. Derandomizing algorithms on product distributions and other applications of order-based extraction. In ICS, pages 397-405, 2010.
[Gabow-90]
Harold N. Gabow. Data structures for weighted matching and nearest common ancestors with linking. In ACM-SIAM Symposium on Discrete Algorithms, pages 434-443, 1990.
[Ganguly-06]
Sumit Ganguly and Anirban Majumder. CR-precis: A deterministic summary structure for update data streams. In ESCAPE, 2007.
[GilbertKMS-02]
Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, and Martin Strauss. How to summarize the universe: Dynamic maintenance of quantiles. In Proc. 28th International Conference on Very Large Data Bases, pages 454-465, 2002.
[GilbertSTV-07]
A. C. Gilbert, M. J. Strauss, J. A. Tropp, and R. Vershynin. One sketch for all: fast algorithms for compressed sensing. ACM Symposium on Theory of Computing, 2007.
[GolubV-89]
G.H. Golub and C.F. Van Loan. Matrix Computations. Johns Hopkins University Press, Baltimore, 1989.
[GoreinovT-01]
S. A. Goreinov and E. E. Tyrtyshnikov. The maximum-volume concept in approximation by low-rank matrices. Contemporary Mathematics, 280, pages 47-51, 2001.
[GoreinovTZ-97]
S. A. Goreinov, E. E. Tyrtyshnikov, and N. L. Zamarashkin. A theory of pseudoskeleton approximations. Linear Algebra and its Applications, 261, pages 1-21, August 1997.
[Gould-96]
Stephen Jay Gould.The Mismeasure of Man. W. W. Norton and Company, 1996.
[GreenwaldK-01]
Michael Greenwald and Sanjeev Khanna. Space-efficient online computation of quantile

summaries. In ACM SIGMOD International Conference on Management of Data, pages 58-66, 2001.

[GroheGLSTV-07]
Martin Grohe, Yuri Gurevich, Dirk Leinders, Nicole Schweikardt, Jerzy Tyszkiewicz, and Jan Van den Bussche. Database query processing using finite cursor machines. In ICDT, pages 284-298, 2007.
[GuE-96]
M. Gu and S.C. Eisenstat. Efficient algorithms for computing a strong rank-revealing QR factorization. SIAM Journal on Scientific Computing, 17, pages 848-869, 1996.
[GuhaIM-07]
Sudipto Guha, Piotr Indyk, and Andrew McGregor. Sketching information divergences. In Conference on Learning Theory, 2007.
[GuhaM-06]
Sudipto Guha and Andrew McGregor. Approximate quantiles and the order of the stream. In ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pages 273-279, 2006.
[GuhaM-07]
Sudipto Guha and Andrew McGregor. Lower bounds for quantile estimation in random-order and multi-pass streaming. Manuscript, 2007.
[GuhaM-07a]
Sudipto Guha and Andrew McGregor. Space-efficient sampling. In AISTATS, pages 169-176, 2007.
[GuhaMV-06]
Sudipto Guha, Andrew McGregor, and Suresh Venkatasubramanian. Streaming and sublinear approximation of entropy and information distances. In ACM-SIAM Symposium on Discrete Algorithms, pages 733-742, 2006.
John Hershberger, Nisheeth Shrivastava, Subhash Suri, and Csaba D. Tóth. Adaptive spatial partitioning for multidimensional data streams. In ISAAC, pages 522-533, 2004.
[HoffmannMR-04]
M. Hoffmann, S. Muthukrishnan, and R. Raman. Location streams: Models and algorithms. Technical Report 2004-28, DIMACS, May 2004.
[HopcroftK-73]
John E. Hopcroft and Richard M. Karp. An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs. SIAM J. Comput., 2(4):225-231, 1973.
[Indyk-00]
Piotr Indyk. Stable distributions, pseudorandom generators, embeddings and data stream computation. In IEEE Symposium on Foundations of Computer Science, pages 189-197, 2000.
[Indyk-04]
Piotr Indyk. Algorithms for dynamic geometric problems over data streams. In ACM Symposium on Theory of Computing, pages 373-380, 2004.
[IndykR-08]
Piotr Indyk and Milan Ruzic. Near-optimal sparse recovery in the $\ell_1$ norm. In IEEE Symposium on Foundations of Computer Science, pages 199-207, 2008.
[IndykT-03]
Piotr Indyk and Niten Thaper. Fast color image retrieval via embeddings. Workshop on Statistical and Computational Theories of Vision (at ICCV), 2003.
[IndykW-03]
Piotr Indyk and David P. Woodruff. Tight lower bounds for the distinct elements problem. In IEEE Symposium on Foundations of Computer Science, pages 283-288, 2003.
[IndykW-05]
Piotr Indyk and David P. Woodruff. Optimal approximations of the frequency moments of data streams. In ACM Symposium on Theory of Computing, pages 202-208, 2005.
[JayramKS-07]
T. S. Jayram, Ravi Kumar, and D. Sivakumar. Simple lower bound on one-way Gap-Hamming. In http://www.cse.iitk.ac.in/users/sganguly/slides/ravikumar.pdf, 2007.
[JayramW-09]
T. S. Jayram and David P. Woodruff. The data stream space complexity of cascaded norms. In IEEE Symposium on Foundations of Computer Science, 2009.
[JowhariG-05]
Hossein Jowhari and Mohammad Ghodsi. New streaming algorithms for counting triangles in graphs. In COCOON, pages 710-716, 2005.
[KalantariS-95]
Bahman Kalantari and Ali Shokoufandeh. Approximation schemes for maximum cardinality matching. Technical Report LCSR-TR-248, Laboratory for Computer Science Research, Department of Computer Science. Rutgers University, August 1995.
[KarloffSV-10]
Howard J. Karloff, Siddharth Suri, and Sergei Vassilvitskii. A model of computation for MapReduce. In ACM-SIAM Symposium on Discrete Algorithms, pages 938-948, 2010.
[KuroseR-04]
James F. Kurose and Keith W. Ross. Computer Networking: A Top-Down Approach Featuring the Internet. Addison Wesley, 2004.
[Li-06]
Ping Li. Very sparse stable random projections, estimators and tail bounds for stable random projections.
[LiHC-06]
Ping Li, Trevor Hastie, and Kenneth Ward Church. Very sparse random projections. In KDD, pages 287-296, 2006.
[MahoneyMD-06]
Michael W. Mahoney, Mauro Maggioni, and Petros Drineas. Tensor-cur decompositions for tensor-based data. In ACM SIGKDD international conference on knowledge discovery and data mining, pages 327-336, 2006.
[MankuRL-98]
Gurmeet Singh Manku, Sridhar Rajagopalan, and Bruce G. Lindsay. Approximate medians and other quantiles in one pass and with limited memory. In ACM SIGMOD International Conference on Management of Data, pages 426-435, 1998.
[MankuRL-99]
Gurmeet Singh Manku, Sridhar Rajagopalan, and Bruce G. Lindsay. Random sampling techniques for space efficient online computation of order statistics of large datasets. In ACM SIGMOD International Conference on Management of Data, pages 251-262, 1999.
[Matousek-02]
Jiří Matoušek. Lectures on Discrete Geometry. Springer, 2002.
[McGregor-05]
Andrew McGregor. Finding graph matchings in data streams. In APPROX-RANDOM, pages 170-181, 2005.
[MetwallyAA-05]
Ahmed Metwally, Divyakant Agrawal, and Amr El Abbadi. Efficient computation of frequent and top-k elements in data streams. In ICDT, pages 398-412, 2005.
[MicaliV-80]
Silvio Micali and Vijay V. Vazirani. An ${O}(\sqrt{V}{E})$ algorithm for finding maximum matching in general graphs. In FOCS, pages 17-27, 1980.
[MisraG-82]
Jayadev Misra and David Gries. Finding repeated elements. Sci. Comput. Program., 2(2), pages143--152, 1982.
[MitzenmacherV-08]
Michael Mitzenmacher and Salil P. Vadhan. Why simple hash functions work: exploiting the entropy in a data stream. In ACM-SIAM Symposium on Discrete Algorithms, pages 746-755, 2008.
[MunroP-80]
J. Ian Munro and Mike Paterson. Selection and sorting with limited storage. Theor. Comput. Sci., 12:315-323, 1980.
[Muthukrishnan-06]
S. Muthukrishnan. Data streams: Algorithms and applications. Now Publishers, 2006.
[Muthukrishnan-06a]
S. Muthukrishnan. Some algorithmic problems and results in compressed sensing. In Allerton Conference, 2006.
[NaorS-06]
Assaf Naor and Gideon Schechtman. Planar earthmover is not in $l_1$. In FOCS, pages 655-666, 2006.
[NeedellT-10]
Deanna Needell and Joel A. Tropp. Cosamp: iterative signal recovery from incomplete and inaccurate samples. Commun. ACM, 53(12):93-100, 2010.
[PettieS-04]
Seth Pettie and Peter Sanders. A simpler linear time $2/3-\epsilon$ approximation for maximum weight matching. Inf. Process. Lett., 91(6):271-276, 2004.
[RudelsonV-06]
Mark Rudelson and Roman Vershynin. Sparse reconstruction by convex relaxation: Fourier and gaussian measurements. In Proceedins of 40th Annual Conference on Information Sciences and Systems, 2006.
[ShrivastavaBAS-04]
Nisheeth Shrivastava, Chiranjeeb Buragohain, Divyakant Agrawal, and Subhash Suri. Medians and beyond: new aggregation techniques for sensor networks. In SenSys, pages 239--249, 2004.
[Stewart-99]
G.W. Stewart. Four algorithms for the efficient computation of truncated QR approximations to a sparse matrix. Numerische Mathematik, 83, pages 313-323, 1999.
[Stewart-04]
G.W. Stewart. Error analysis of the quasi-Gram-Schmidt algorithm. Technical Report UMIACS TR-2004-17 CMSC TR-4572, University of Maryland, College Park, MD, 2004.
[Woodruff-04]
David P. Woodruff. Optimal space lower bounds for all frequency moments. In ACM-SIAM Symposium on Discrete Algorithms, pages 167-175, 2004.