{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:17:37Z","timestamp":1763468257470,"version":"3.41.0"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662476710"},{"type":"electronic","value":"9783662476727"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47672-7_44","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T10:07:39Z","timestamp":1434708459000},"page":"542-553","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Taylor Polynomial Estimator for Estimating Frequency Moments"],"prefix":"10.1007","author":[{"given":"Sumit","family":"Ganguly","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"issue":"1","key":"44_CR1","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. Journal of Computer Systems and Sciences 58(1), 137\u2013147 (1998). Preliminary version appeared in Proceedings of ACM Symposium on Theory of Computing (STOC) 1996, pp. 1\u201310","journal-title":"Journal of Computer Systems and Sciences"},{"key":"44_CR2","doi-asserted-by":"crossref","unstructured":"Andoni, A., Krauthgamer, R., Onak, K.: Streaming algorithms via precision sampling. In: Proceedings of IEEE Foundations of Computer Science (FOCS) (2011). A version appears in arXiv:1011.1263v1 [cs.DS] November 2010","DOI":"10.1109\/FOCS.2011.82"},{"key":"44_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/978-3-642-39206-1_3","volume-title":"Automata, Languages, and Programming","author":"A Andoni","year":"2013","unstructured":"Andoni, A., Nguyen, H.L., Polyanskiy, Y., Wu, Y.: Tight lower bound for linear sketches of moments. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol. 7965, pp. 25\u201332. Springer, Heidelberg (2013)"},{"key":"44_CR4","unstructured":"Ba, K.D., Indyk, P., Price, E., Woodruff, D.: Lower bounds for sparse recovery. In: Proceedings of ACM Symposium on Discrete Algorithms (SODA) (2008)"},{"key":"44_CR5","doi-asserted-by":"crossref","unstructured":"Bar-Yossef, Z., Jayram, T.S., Kumar, R., Sivakumar, D.: An information statistics approach to data stream and communication complexity. In: Proceedings of ACM Symposium on Theory of Computing STOC, pp. 209\u2013218 (2002)","DOI":"10.1109\/SFCS.2002.1181944"},{"key":"44_CR6","doi-asserted-by":"crossref","unstructured":"Bhuvanagiri, L., Ganguly, S., Kesh, D., Saha, C.: Simpler algorithm for estimating frequency moments of data streams. In: Proceedings of ACM Symposium on Discrete Algorithms (SODA), pp. 708\u2013713 (2006)","DOI":"10.1145\/1109557.1109634"},{"key":"44_CR7","unstructured":"Braverman, V., Katzman, J., Seidell, C., Vorsanger, G.: Approximating large frequency moments with $$O(n^{1-2\/k})$$ bits. In: Proceedings of International Workshop on Randomization and Computation (RANDOM) (2014). Published earlier as arXiv:1401.1763, January 2014"},{"key":"44_CR8","unstructured":"Braverman, V., Ostrovsky, R.: Recursive Sketching For Frequency Moments (November 2010). arXiv:1011.2571v1 [cs.DS]"},{"key":"44_CR9","doi-asserted-by":"crossref","unstructured":"Cesa-Bianchi, N., Shwartz, S.S., Shamir, O.: Online learning of noisy data with kernels. In: Proceedings of ACM International Conference on Learning Theory (COLT) (2010)","DOI":"10.1109\/TIT.2011.2164053"},{"key":"44_CR10","unstructured":"Chakrabarti, A., Khot, S., Sun, X.: Near-optimal lower bounds on the multi-party communication complexity of set disjointness. In: Proceedings of International Conference on Computational Complexity (CCC) (2003)"},{"issue":"1","key":"44_CR11","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0304-3975(03)00400-6","volume":"312","author":"M Charikar","year":"2004","unstructured":"Charikar, M., Chen, K., Farach-Colton, M.: Finding frequent items in data streams. Theoretical Computer Science 312(1), 3\u201315 (2004). Preliminary version appeared inProceedings of ICALP 2002, pp. 693\u2013703","journal-title":"Theoretical Computer Science"},{"key":"44_CR12","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1007\/s00453-008-9260-5","volume":"53","author":"S Ganguly","year":"2009","unstructured":"Ganguly, S., Bhuvanagiri, L.: Hierarchical Sampling from Sketches: Estimating Functions over Data Streams. Algorithmica 53, 549\u2013582 (2009)","journal-title":"Algorithmica"},{"key":"44_CR13","unstructured":"Ganguly, S.: A Lower Bound for Estimating High Moments of a Data Stream (December 2011). arXiv:1201.0253"},{"issue":"3","key":"44_CR14","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1145\/1147954.1147955","volume":"53","author":"P Indyk","year":"2006","unstructured":"Indyk, P.: Stable distributions, pseudorandom generators, embeddings, and data stream computation. J. ACM 53(3), 307\u2013323 (2006). Preliminary Version appeared in Proceedings of IEEE FOCS 2000, pp. 189\u2013197","journal-title":"J. ACM"},{"key":"44_CR15","doi-asserted-by":"crossref","unstructured":"Indyk, P., Woodruff, D.: Optimal approximations of the frequency moments. In: Proceedings of ACM Symposium on Theory of Computing STOC, pp. 202\u2013298. Baltimore, Maryland, USA (June 2005)","DOI":"10.1145\/1060590.1060621"},{"key":"44_CR16","doi-asserted-by":"crossref","unstructured":"Jayram, T.S., Woodruff, D.: Optimal bounds for johnson-lindenstrauss transforms and streaming problems with low error. In: Proceedings of ACM Symposium on Discrete Algorithms (SODA) (2011)","DOI":"10.1137\/1.9781611973082.1"},{"key":"44_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1007\/978-3-642-40328-6_43","volume-title":"Approximation, Randomization, and Combinatorial Optimization","author":"Y Li","year":"2013","unstructured":"Li, Y., Woodruff, D.P.: A tight lower bound for high frequency moment estimation with small error. In: Raghavendra, P., Raskhodnikova, S., Jansen, K., Rolim, J.D.P. (eds.) RANDOM 2013 and APPROX 2013. LNCS, vol. 8096, pp. 623\u2013638. Springer, Heidelberg (2013)"},{"key":"44_CR18","doi-asserted-by":"crossref","unstructured":"Monemizadeh, M., Woodruff, D.: 1-pass relative-error $$l_p$$-sampling with applications. In: Proceedings of ACM Symposium on Discrete Algorithms (SODA) (2010)","DOI":"10.1137\/1.9781611973075.92"},{"key":"44_CR19","doi-asserted-by":"crossref","unstructured":"Nisan, N.: Pseudo-random generators for space bounded computation. In: Proceedings of ACM Symposium on Theory of Computing STOC, pp. 204\u2013212 (May 1990)","DOI":"10.1145\/100216.100242"},{"key":"44_CR20","doi-asserted-by":"crossref","unstructured":"Price, E., Woodruff, D.: $$(1+\\epsilon )$$-approximate sparse recovery. In: Proceedings of IEEE Foundations of Computer Science (FOCS) (2011)","DOI":"10.1109\/FOCS.2011.92"},{"issue":"1","key":"44_CR21","first-page":"93","volume":"26","author":"R Singh","year":"1964","unstructured":"Singh, R.: Existence of unbiased estimates. Sankhya: The Indian Journal of Statistics 26(1), 93\u201396 (1964)","journal-title":"Sankhya: The Indian Journal of Statistics"},{"key":"44_CR22","unstructured":"Woodruff, D.P.: Optimal space lower bounds for all frequency moments. In: Proceedings of ACM Symposium on Discrete Algorithms (SODA), pp. 167\u2013175 (2004)"},{"key":"44_CR23","doi-asserted-by":"crossref","unstructured":"Woodruff, D.P., Zhang, Q.: Tight bounds for distributed functional monitoring. In: Proceedings of ACM Symposium on Theory of Computing STOC (2012)","DOI":"10.1145\/2213977.2214063"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47672-7_44","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T19:09:59Z","timestamp":1748459399000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-47672-7_44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476710","9783662476727"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47672-7_44","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"20 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}