{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T05:00:23Z","timestamp":1725512423311},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540797081"},{"type":"electronic","value":"9783540797098"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-79709-8_22","type":"book-chapter","created":{"date-parts":[[2008,5,13]],"date-time":"2008-05-13T10:33:17Z","timestamp":1210674797000},"page":"204-215","source":"Crossref","is-referenced-by-count":6,"title":["Lower Bounds on Frequency Estimation of Data Streams (Extended Abstract)"],"prefix":"10.1007","author":[{"given":"Sumit","family":"Ganguly","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1-3","key":"22_CR1","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/S0012-365X(03)00227-9","volume":"273","author":"N. Alon","year":"2003","unstructured":"Alon, N.: Problems and results in extremal combinatorics I. Discr. Math.\u00a0273(1-3), 31\u201353 (2003)","journal-title":"Discr. Math."},{"key":"22_CR2","unstructured":"Alon, N.: Perturbed identity matrices have high rank: proof and applications (2006), http:\/\/www.math.tau.ac.il\/~nogaa\/identity.pdf"},{"issue":"1","key":"22_CR3","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1006\/jcss.1997.1545","volume":"58","author":"N. Alon","year":"1998","unstructured":"Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating frequency moments. J. Comp. Sys. and Sc.\u00a058(1), 137\u2013147 (1998)","journal-title":"J. Comp. Sys. and Sc."},{"key":"22_CR4","unstructured":"Bose, P., Kranakis, E., Morin, P., Tang, Y.: Bounds for Frequency Estimation of Packet Streams. In: Proc. SIROCCO, pp. 33\u201342 (2003)"},{"key":"22_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1007\/3-540-45465-9_59","volume-title":"Automata, Languages and Programming","author":"M. Charikar","year":"2002","unstructured":"Charikar, M., Chen, K., Farach-Colton, M.: Finding frequent items in data streams. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 693\u2013703. Springer, Heidelberg (2002)"},{"key":"22_CR6","doi-asserted-by":"crossref","unstructured":"Cormode, G., Muthukrishnan, S.: An Improved Data Stream Summary: The Count-Min Sketch and its Applications. J. Algorithms\u00a055(1)","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"22_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/3-540-45749-6_33","volume-title":"Algorithms - ESA 2002","author":"E.D. Demaine","year":"2002","unstructured":"Demaine, E.D., L\u00f3pez-Ortiz, A., Munro, J.I.: Frequency estimation of internet packet streams with limited space. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.\u00a02461, pp. 348\u2013360. Springer, Heidelberg (2002)"},{"issue":"2","key":"22_CR8","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1016\/0022-0000(85)90041-8","volume":"31","author":"P. Flajolet","year":"1985","unstructured":"Flajolet, P., Martin, G.N.: Probabilistic Counting Algorithms for Database Applications. J. Comp. Sys. and Sc.\u00a031(2), 182\u2013209 (1985)","journal-title":"J. Comp. Sys. and Sc."},{"key":"22_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74450-4_5","volume-title":"Combinatorics, Algorithms, Probabilistic and Experimental Methodologies","author":"S. Ganguly","year":"2007","unstructured":"Ganguly, S., Majumder, A.: CR-precis: A Deterministic Summary Structure for Update Streams. In: Chen, B., Paterson, M., Zhang, G. (eds.) ESCAPE 2007. LNCS, vol.\u00a04614. Springer, Heidelberg (2007)"},{"key":"22_CR10","doi-asserted-by":"crossref","unstructured":"Ganguly, S., Majumder, A.: Deterministic K-set Structure. In: Proc. ACM PODS, pp. 280\u2013289 (2006), www.cse.iitk.ac.in\/users\/sganguly","DOI":"10.1145\/1142351.1142392"},{"key":"22_CR11","unstructured":"Ganguly, S.: Distributed deterministic approximation of vector sums (November 2007) (manuscript)"},{"key":"22_CR12","unstructured":"Ganguly, S.: Lower bounds on frequency estimation of data streams. arXiv:cs\/0701004v3 (February 2008)"},{"key":"22_CR13","doi-asserted-by":"crossref","unstructured":"Gilbert, A., Kotidis, Y., Muthukrishnan, S., Strauss, M.: How to Summarize the Universe: Dynamic Maintenance of Quantiles. In: Proc. VLDB, Hong Kong, August 2002, pp. 454\u2013465 (2002)","DOI":"10.1016\/B978-155860869-6\/50047-0"},{"issue":"1","key":"22_CR14","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1145\/762471.762473","volume":"28","author":"R.M. Karp","year":"2003","unstructured":"Karp, R.M., Shenker, S., Papadimitriou, C.H.: A Simple Algorithm for Finding Frequent Elements in Streams and Bags. ACM TODS\u00a028(1), 51\u201355 (2003)","journal-title":"ACM TODS"},{"key":"22_CR15","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0167-6423(82)90012-0","volume":"2","author":"J. Misra","year":"1982","unstructured":"Misra, J., Gries, D.: Finding repeated elements. Sci. Comput. Programm.\u00a02, 143\u2013152 (1982)","journal-title":"Sci. Comput. Programm."}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-79709-8_22.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:28:47Z","timestamp":1619508527000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-79709-8_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540797081","9783540797098"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-79709-8_22","relation":{},"subject":[]}}