Difference between revisions of "Bibliography"
m (1 revision) 

(No difference)

Revision as of 05:43, 8 November 2012
Citations: Write {{citepaper_id_1paper_id_2…paper_id_k}} to cite papers paper_id_1, paper_id_2, …, paper_id_k. For instance, {{citeAlonMS99BlumLR93}} results in [AlonMS99,BlumLR93].
 [AlonMS99]
 Noga Alon, Yossi Matias, Mario Szegedy. The Space Complexity of Approximating the Frequency Moments. J. Comput. Syst. Sci. 58(1), pages 137147, 1999.
 [AndoniIK09]
 Alexandr Andoni, Piotr Indyk, and Robert Krauthgamer. Overcoming the $\ell_1$ nonembeddability barrier: algorithms for product metrics. In ACMSIAM Symposium on Discrete Algorithms, pages 865874, 2009.
 [AndoniJP10]
 Alexandr Andoni, T. S. Jayram, and Mihai Patrascu. Lower bounds for edit distance and product metrics via Poincarétype inequalities. In ACMSIAM Symposium on Discrete Algorithms, pages 184192, 2010.
 [AndoniN12]
 Alexandr Andoni, Huy L. Nguyen. Width of points in the streaming model. In ACMSIAM Symposium on Discrete Algorithms, pages 447452, 2012.
 [AndoniO09]
 Alexandr Andoni and Krzysztof Onak. Approximating edit distance in nearlinear time. In ACM Symposium on Theory of Computing, pages 199204, 2009.
 [BarYossefJKST02]
 Ziv BarYossef, 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 110, 2002.
 [BarYossefKS02]
 Ziv BarYossef, Ravi Kumar, and D. Sivakumar. Reductions in streaming algorithms, with an application to counting triangles in graphs. In ACMSIAM Symposium on Discrete Algorithms, pages 623632, 2002.
 [Baswana06]
 Surender Baswana. Faster streaming algorithms for graph spanners. 2006.
 [BerindeIR08]
 Radu Berinde, Piotr Indyk, and Milan Ruzic. Practical nearoptimal sparse recovery in the $l_1$ norm. Allerton, 2008.
 [BhattacharyyaMMY07]
 S. Bhattacharyya, A. Madeira, S. Muthukrishnan, and T. Ye. How to scalably skip past streams. In WSSP (Workshop with ICDE), 2007.
 [BhuvanagiriG06]
 Lakshminath Bhuvanagiri and Sumit Ganguly. Estimating entropy over data streams. In ESA, pages 148159, 2006.
 [BhuvanagiriGKS06]
 Lakshminath Bhuvanagiri, Sumit Ganguly, Deepanjan Kesh, and Chandan Saha. Simpler algorithm for estimating frequency moments of data streams. In ACMSIAM Symposium on Discrete Algorithms, pages 708713, 2006.
 [BlumLR93]
 Manuel Blum, Michael Luby, Ronitt Rubinfeld. SelfTesting/Correcting with Applications to Numerical Problems. J. Comput. Syst. Sci. 47(3), pages 549595, 1993.
 [BroderCFM00]
 Andrei Z. Broder, Moses Charikar, Alan M. Frieze, and Michael Mitzenmacher. Minwise independent permutations. J. Comput. Syst. Sci., 60(3), pages 630659, 2000.
 [BuriolFLMS06]
 Luciana S. Buriol, Gereon Frahling, Stefano Leonardi, Alberto MarchettiSpaccamela, and Christian Sohler. Counting triangles in data streams. In ACM SIGMODSIGACTSIGART Symposium on Principles of Database Systems, pages 253262, 2006.
 [CandesRT06]
 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):489509, 2006.
 [ChakrabartiCM07]
 Amit Chakrabarti, Graham Cormode, and Andrew McGregor. A nearoptimal algorithm for computing the entropy of a stream. In ACMSIAM Symposium on Discrete Algorithms, pages 328335, 2007.
 [Charikar02]
 Moses Charikar. Similarity estimation techniques from rounding algorithms. In STOC, pages 380388, 2002.
 [CormodeDIM03]
 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 529540, 2003.
 [CormodeKMS06]
 Graham Cormode, Flip Korn, S. Muthukrishnan, and Divesh Srivastava. Space and timeefficient deterministic algorithms for biased quantiles over data streams. In PODS, pages 263272, 2006.
 [CormodeM05]
 Graham Cormode and S. Muthukrishnan. An improved data stream summary: the countmin sketch and its applications. J. Algorithms, 55(1), pages 5875, 2005.
 [CormodeM05a]
 Graham Cormode and S. Muthukrishnan. What's new: finding significant differences in network data streams. IEEE/ACM Trans. Netw., 13(6), pages 12191232, 2005.
 [CormodeM05b]
 Graham Cormode and S. Muthukrishnan. Space efficient mining of multigraph streams. In ACM SIGMODSIGACTSIGART Symposium on Principles of Database Systems, pages 271282, 2005.
 [CormodeM06]
 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 25, 2006, Proceedings, volume 4056 of Lecture Notes in Computer Science, pages 280294. Springer, 2006.
 [DasSarmaGP08]
 Atish Das Sarma, Sreenivas Gollapudi, and Rina Panigrahy. Estimating PageRank on graph streams. In PODS, pages 6978, 2008.
 [DeanG04]
 Jeffrey Dean and Sanjay Ghemawat. MapReduce: Simplified data processing on large clusters. In OSDI, pages 137150, 2004.
 [DemaineLM02]
 Erik D. Demaine, Alejandro LópezOrtiz, and J. Ian Munro. Frequency estimation of internet packet streams with limited space. In ESA, pages 348360, 2002.
 [DemetrescuFR06]
 Camil Demetrescu, Irene Finocchi, and Andrea Ribichini. Trading off space for passes in graph streaming problems. In ACMSIAM Symposium on Discrete Algorithms, pages 714723, 2006.
 [Donoho06]
 David L. Donoho. Compressed sensing. IEEE Transactions on Information Theory, 52(4):12891306, 2006.
 [DrakeH03]
 Doratha E. Drake and Stefan Hougardy. Improved linear time approximation algorithms for weighted matchings. In RANDOMAPPROX, pages 1423, 2003.
 [DrineasMM06]
 Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan. Sampling algorithms for $\ell_2$ regression and applications. In ACMSIAM Symposium on Discrete Algorithms, pages 11271136, 2006.
 [DrineasMM06a]
 Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan. Subspace sampling and relativeerror matrix approximation: Columnbased methods. In APPROXRANDOM, pages 316326, 2006.
 [DrineasMM06b]
 Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan. Subspace sampling and relativeerror matrix approximation: Columnrowbased methods. In ESA, pages 304314, 2006.
 [Edmonds65]
 Jack Edmonds. Maximum matching and a polyhedron with 0,1vertices. J. Res. Nat. Bur. Standards, 69(B):125130, 1965.
 [Elkin06]
 Michael Elkin. A nearoptimal fully dynamic distributed algorithm for maintaining sparse spanners. 2006.
 [ElkinZ06]
 Michael Elkin and Jian Zhang. Efficient algorithms for constructing $(1+\epsilon, \beta)$spanners in the distributed and streaming models. Distributed Computing, 18(5):375385, 2006.
 [FeigenbaumKMSZ05]
 Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. Graph distances in the streaming model: the value of space. In ACMSIAM Symposium on Discrete Algorithms, pages 745754, 2005.
 [FeigenbaumKMSZ05a]
 Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. On graph problems in a semistreaming model. Theoretical Computer Science, 348(23):207216, 2005.
 [FeigenbaumKMSZ08]
 Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. Graph distances in the datastream model. SIAM J. Comput., 38(5):17091727, 2008.
 [FeigenbaumKSV02]
 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 131151, 2002.
 [FeldmanMSSS06]
 Jon Feldman, S. Muthukrishnan, Anastasios Sidiropoulos, Cliff Stein, and Zoya Svitkina. On the complexity of processing massive, unordered, distributed data. 2006.
 [FeldmanMSSS10]
 Jon Feldman, S. Muthukrishnan, Anastasios Sidiropoulos, Clifford Stein, and Zoya Svitkina. On distributing symmetric streaming computations. ACM Transactions on Algorithms, 6(4), 2010.
 [GabizonH10]
 Ariel Gabizon and Avinatan Hassidim. Derandomizing algorithms on product distributions and other applications of orderbased extraction. In ICS, pages 397405, 2010.
 [Gabow90]
 Harold N. Gabow. Data structures for weighted matching and nearest common ancestors with linking. In ACMSIAM Symposium on Discrete Algorithms, pages 434443, 1990.
 [Ganguly06]
 Sumit Ganguly and Anirban Majumder. CRprecis: A deterministic summary structure for update data streams. In ESCAPE, 2007.
 [GilbertKMS02]
 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 454465, 2002.
 [GilbertSTV07]
 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.
 [GolubV89]
 G.H. Golub and C.F. Van Loan. Matrix Computations. Johns Hopkins University Press, Baltimore, 1989.
 [GoreinovT01]
 S. A. Goreinov and E. E. Tyrtyshnikov. The maximumvolume concept in approximation by lowrank matrices. Contemporary Mathematics, 280, pages 4751, 2001.
 [GoreinovTZ97]
 S. A. Goreinov, E. E. Tyrtyshnikov, and N. L. Zamarashkin. A theory of pseudoskeleton approximations. Linear Algebra and its Applications, 261, pages 121, August 1997.
 [Gould96]
 Stephen Jay Gould.The Mismeasure of Man. W. W. Norton and Company, 1996.
 [GreenwaldK01]
 Michael Greenwald and Sanjeev Khanna. Spaceefficient online computation of quantile
summaries. In ACM SIGMOD International Conference on Management of Data, pages 5866, 2001.
 [GroheGLSTV07]
 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 284298, 2007.
 [GuE96]
 M. Gu and S.C. Eisenstat. Efficient algorithms for computing a strong rankrevealing QR factorization. SIAM Journal on Scientific Computing, 17, pages 848869, 1996.
 [GuhaIM07]
 Sudipto Guha, Piotr Indyk, and Andrew McGregor. Sketching information divergences. In Conference on Learning Theory, 2007.
 [GuhaM06]
 Sudipto Guha and Andrew McGregor. Approximate quantiles and the order of the stream. In ACM SIGMODSIGACTSIGART Symposium on Principles of Database Systems, pages 273279, 2006.
 [GuhaM07]
 Sudipto Guha and Andrew McGregor. Lower bounds for quantile estimation in randomorder and multipass streaming. Manuscript, 2007.
 [GuhaM07a]
 Sudipto Guha and Andrew McGregor. Spaceefficient sampling. In AISTATS, pages 169176, 2007.
 [GuhaMV06]
 Sudipto Guha, Andrew McGregor, and Suresh Venkatasubramanian. Streaming and sublinear approximation of entropy and information distances. In ACMSIAM Symposium on Discrete Algorithms, pages 733742, 2006.
 [HershbergerSST04]
 John Hershberger, Nisheeth Shrivastava, Subhash Suri, and Csaba D. Tóth. Adaptive spatial partitioning for multidimensional data streams. In ISAAC, pages 522533, 2004.
 [HoffmannMR04]
 M. Hoffmann, S. Muthukrishnan, and R. Raman. Location streams: Models and algorithms. Technical Report 200428, DIMACS, May 2004.
 [HopcroftK73]
 John E. Hopcroft and Richard M. Karp. An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs. SIAM J. Comput., 2(4):225231, 1973.
 [Indyk00]
 Piotr Indyk. Stable distributions, pseudorandom generators, embeddings and data stream computation. In IEEE Symposium on Foundations of Computer Science, pages 189197, 2000.
 [Indyk04]
 Piotr Indyk. Algorithms for dynamic geometric problems over data streams. In ACM Symposium on Theory of Computing, pages 373380, 2004.
 [IndykR08]
 Piotr Indyk and Milan Ruzic. Nearoptimal sparse recovery in the $\ell_1$ norm. In IEEE Symposium on Foundations of Computer Science, pages 199207, 2008.
 [IndykT03]
 Piotr Indyk and Niten Thaper. Fast color image retrieval via embeddings. Workshop on Statistical and Computational Theories of Vision (at ICCV), 2003.
 [IndykW03]
 Piotr Indyk and David P. Woodruff. Tight lower bounds for the distinct elements problem. In IEEE Symposium on Foundations of Computer Science, pages 283288, 2003.
 [IndykW05]
 Piotr Indyk and David P. Woodruff. Optimal approximations of the frequency moments of data streams. In ACM Symposium on Theory of Computing, pages 202208, 2005.
 [JayramKS07]
 T. S. Jayram, Ravi Kumar, and D. Sivakumar. Simple lower bound on oneway GapHamming. In http://www.cse.iitk.ac.in/users/sganguly/slides/ravikumar.pdf, 2007.
 [JayramW09]
 T. S. Jayram and David P. Woodruff. The data stream space complexity of cascaded norms. In IEEE Symposium on Foundations of Computer Science, 2009.
 [JowhariG05]
 Hossein Jowhari and Mohammad Ghodsi. New streaming algorithms for counting triangles in graphs. In COCOON, pages 710716, 2005.
 [KalantariS95]
 Bahman Kalantari and Ali Shokoufandeh. Approximation schemes for maximum cardinality matching. Technical Report LCSRTR248, Laboratory for Computer Science Research, Department of Computer Science. Rutgers University, August 1995.
 [KarloffSV10]
 Howard J. Karloff, Siddharth Suri, and Sergei Vassilvitskii. A model of computation for MapReduce. In ACMSIAM Symposium on Discrete Algorithms, pages 938948, 2010.
 [KuroseR04]
 James F. Kurose and Keith W. Ross. Computer Networking: A TopDown Approach Featuring the Internet. Addison Wesley, 2004.
 [Li06]
 Ping Li. Very sparse stable random projections, estimators and tail bounds for stable random projections.
 [LiHC06]
 Ping Li, Trevor Hastie, and Kenneth Ward Church. Very sparse random projections. In KDD, pages 287296, 2006.
 [MahoneyMD06]
 Michael W. Mahoney, Mauro Maggioni, and Petros Drineas. Tensorcur decompositions for tensorbased data. In ACM SIGKDD international conference on knowledge discovery and data mining, pages 327336, 2006.
 [MankuRL98]
 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 426435, 1998.
 [MankuRL99]
 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 251262, 1999.
 [Matousek02]
 Jiří Matoušek. Lectures on Discrete Geometry. Springer, 2002.
 [McGregor05]
 Andrew McGregor. Finding graph matchings in data streams. In APPROXRANDOM, pages 170181, 2005.
 [MetwallyAA05]
 Ahmed Metwally, Divyakant Agrawal, and Amr El Abbadi. Efficient computation of frequent and topk elements in data streams. In ICDT, pages 398412, 2005.
 [MicaliV80]
 Silvio Micali and Vijay V. Vazirani. An ${O}(\sqrt{V}{E})$ algorithm for finding maximum matching in general graphs. In FOCS, pages 1727, 1980.
 [MisraG82]
 Jayadev Misra and David Gries. Finding repeated elements. Sci. Comput. Program., 2(2), pages143152, 1982.
 [MitzenmacherV08]
 Michael Mitzenmacher and Salil P. Vadhan. Why simple hash functions work: exploiting the entropy in a data stream. In ACMSIAM Symposium on Discrete Algorithms, pages 746755, 2008.
 [MunroP80]
 J. Ian Munro and Mike Paterson. Selection and sorting with limited storage. Theor. Comput. Sci., 12:315323, 1980.
 [Muthukrishnan06]
 S. Muthukrishnan. Data streams: Algorithms and applications. Now Publishers, 2006.
 [Muthukrishnan06a]
 S. Muthukrishnan. Some algorithmic problems and results in compressed sensing. In Allerton Conference, 2006.
 [NaorS06]
 Assaf Naor and Gideon Schechtman. Planar earthmover is not in $l_1$. In FOCS, pages 655666, 2006.
 [NeedellT10]
 Deanna Needell and Joel A. Tropp. Cosamp: iterative signal recovery from incomplete and inaccurate samples. Commun. ACM, 53(12):93100, 2010.
 [PettieS04]
 Seth Pettie and Peter Sanders. A simpler linear time $2/3\epsilon$ approximation for maximum weight matching. Inf. Process. Lett., 91(6):271276, 2004.
 [RudelsonV06]
 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.
 [ShrivastavaBAS04]
 Nisheeth Shrivastava, Chiranjeeb Buragohain, Divyakant Agrawal, and Subhash Suri. Medians and beyond: new aggregation techniques for sensor networks. In SenSys, pages 239249, 2004.
 [Stewart99]
 G.W. Stewart. Four algorithms for the efficient computation of truncated QR approximations to a sparse matrix. Numerische Mathematik, 83, pages 313323, 1999.
 [Stewart04]
 G.W. Stewart. Error analysis of the quasiGramSchmidt algorithm. Technical Report UMIACS TR200417 CMSC TR4572, University of Maryland, College Park, MD, 2004.
 [Woodruff04]
 David P. Woodruff. Optimal space lower bounds for all frequency moments. In ACMSIAM Symposium on Discrete Algorithms, pages 167175, 2004.