{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,24]],"date-time":"2025-02-24T05:23:17Z","timestamp":1740374597977,"version":"3.37.3"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2010,7,31]],"date-time":"2010-07-31T00:00:00Z","timestamp":1280534400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2012,4]]},"DOI":"10.1007\/s10878-010-9339-1","type":"journal-article","created":{"date-parts":[[2010,7,31]],"date-time":"2010-07-31T17:49:47Z","timestamp":1280598587000},"page":"373-394","source":"Crossref","is-referenced-by-count":1,"title":["Estimating hybrid frequency moments of data streams"],"prefix":"10.1007","volume":"23","author":[{"given":"Sumit","family":"Ganguly","sequence":"first","affiliation":[]},{"given":"Mohit","family":"Bansal","sequence":"additional","affiliation":[]},{"given":"Shruti","family":"Dube","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,7,31]]},"reference":[{"issue":"1","key":"9339_CR1","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1006\/jcss.1997.1545","volume":"58","author":"N Alon","year":"1998","unstructured":"Alon\u00a0N, Matias\u00a0Y, Szegedy\u00a0M (1998) The space complexity of approximating frequency moments. J\u00a0Comput Syst Sci 58(1):137\u2013147. Preliminary version appeared in Proceedings of ACM STOC 1996, pp\u00a01\u201310","journal-title":"J\u00a0Comput Syst Sci"},{"key":"9339_CR2","doi-asserted-by":"crossref","unstructured":"Bar-Yossef\u00a0Z, Jayram\u00a0TS, Kumar\u00a0R, Sivakumar\u00a0D (2002a) An information statistics approach to data stream and communication complexity. In: Proceedings of ACM STOC, pp\u00a0209\u2013218, Princeton, NJ","DOI":"10.1109\/SFCS.2002.1181944"},{"key":"9339_CR3","doi-asserted-by":"crossref","unstructured":"Bar-Yossef\u00a0Z, Jayram\u00a0TS, Kumar\u00a0R, Sivakumar\u00a0D, Trevisan\u00a0L (2002b) Counting distinct elements in a data stream. In: Proceedings of international workshop on randomization and computation (RANDOM), Cambridge, MA","DOI":"10.1007\/3-540-45726-7_1"},{"key":"9339_CR4","unstructured":"Chakrabarti\u00a0A, Khot\u00a0S, Sun\u00a0X (2003) Near-optimal lower bounds on the multi-party communication complexity of set disjointness. In: Proceedings of international conference on computational complexity (CCC), Aarhus, Denmark"},{"issue":"1","key":"9339_CR5","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0304-3975(03)00400-6","volume":"312","author":"M Charikar","year":"2004","unstructured":"Charikar\u00a0M, Chen\u00a0K, Farach-Colton\u00a0M (2004) Finding frequent items in data streams. Theor Comput Sci 312(1):3\u201315. Preliminary version appeared in Proceedings of ICALP 2002, pp\u00a0693\u2013703","journal-title":"Theor Comput Sci"},{"issue":"1","key":"9339_CR6","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1016\/j.jalgor.2003.12.001","volume":"55","author":"G Cormode","year":"2005","unstructured":"Cormode\u00a0G, Muthukrishnan\u00a0S (2005a) An improved data stream summary: The count-min sketch and its applications. J\u00a0Algorithms 55(1):58\u201375","journal-title":"J\u00a0Algorithms"},{"key":"9339_CR7","doi-asserted-by":"crossref","unstructured":"Cormode\u00a0G, Muthukrishnan\u00a0S (2005b) Space efficient mining of multigraph streams. In: Proceedings of ACM international symposium on principles of database systems (PODS)","DOI":"10.1145\/1065167.1065201"},{"issue":"2","key":"9339_CR8","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1016\/0022-0000(85)90041-8","volume":"31","author":"P Flajolet","year":"1985","unstructured":"Flajolet\u00a0P, Martin\u00a0GN (1985) Probabilistic counting algorithms for database applications. J\u00a0Comput Syst Sci 31(2):182\u2013209","journal-title":"J\u00a0Comput Syst Sci"},{"issue":"4","key":"9339_CR9","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1007\/s00453-008-9260-5","volume":"53","author":"S Ganguly","year":"2009","unstructured":"Ganguly\u00a0S, Bhuvanagiri\u00a0L (2009) Hierarchical sampling from sketches: Estimating functions over data streams. Algorithmica 53(4):549\u2013582","journal-title":"Algorithmica"},{"key":"9339_CR10","doi-asserted-by":"crossref","unstructured":"Ganguly\u00a0S, Cormode\u00a0G (2007) On estimating frequency moments of data streams. In: Proceedings of international workshop on randomization and computation (RANDOM)","DOI":"10.1007\/978-3-540-74208-1_35"},{"key":"9339_CR11","unstructured":"Ganguly\u00a0S, Majumder\u00a0A (2007) Cr-precis: A deterministic summary structure for update streams. In: Proceedings of int\u2019l symp. on algorithms, probabilistic and experimental methodologies (ESCAPE). LNCS, vol\u00a04614, pp\u00a048\u201359"},{"key":"9339_CR12","unstructured":"Gibbons\u00a0PB, Tirthapura\u00a0S (2001) Estimating simple functions on the union of data streams. In: Proceedings of ACM SPAA, Heraklion, Crete, Greece, pp\u00a0281\u2013291"},{"issue":"3","key":"9339_CR13","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1145\/1147954.1147955","volume":"53","author":"P Indyk","year":"2006","unstructured":"Indyk\u00a0P (2006) Stable distributions, pseudorandom generators, embeddings, and data stream computation. Journal of the ACM 53(3):307\u2013323. Preliminary Version appeared in Proceedings of IEEE FOCS 2000, pp\u00a0189\u2013197","journal-title":"Journal of the ACM"},{"key":"9339_CR14","unstructured":"Indyk\u00a0P, Woodruff\u00a0D (2005) Optimal approximations of the frequency moments. In: Proceedings of ACM symposium on theory of computing STOC, June 2005, pp\u00a0202\u2013298"},{"key":"9339_CR15","doi-asserted-by":"crossref","unstructured":"Jayram\u00a0TS, Woodruff\u00a0DP (2009) The data stream space complexity of cascaded norms. In: Proceedings of IEEE foundations of computer science (FOCS)","DOI":"10.1109\/FOCS.2009.82"},{"key":"9339_CR16","doi-asserted-by":"crossref","unstructured":"Kane\u00a0DM, Nelson\u00a0J, Woodruff\u00a0DP (2010) On the exact space complexity of sketching and streaming small norms. In: Proceedings of ACM symposium on discrete algorithms (SODA)","DOI":"10.1137\/1.9781611973075.93"},{"key":"9339_CR17","unstructured":"Li\u00a0P (2008) Estimators and tail bounds for dimension reduction in \u2113 \u03b1 (0<\u03b1\u22642) using stable random projections. In: Proceedings of ACM symposium on discrete algorithms (SODA), pp\u00a010\u201319"},{"key":"9339_CR18","unstructured":"McGregor\u00a0A (2006) Open problems in data streams and related topics: IITK workshop on algorithms for data streams. http:\/\/www.cse.iitk.ac.in\/users\/sganguly\/openproblems.pdf"},{"key":"9339_CR19","unstructured":"Nisan\u00a0N (1990) Pseudo-random generators for space bounded computation. In: Proceedings of ACM symposium on theory of computing STOC, pp\u00a0204\u2013212, May 1990"},{"key":"9339_CR20","unstructured":"Woodruff\u00a0DP (2004) Optimal space lower bounds for all frequency moments. In: Proceedings of ACM symposium on discrete algorithms (SODA), pp\u00a0167\u2013175"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-010-9339-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-010-9339-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-010-9339-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,23]],"date-time":"2025-02-23T16:56:50Z","timestamp":1740329810000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-010-9339-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,7,31]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,4]]}},"alternative-id":["9339"],"URL":"https:\/\/doi.org\/10.1007\/s10878-010-9339-1","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2010,7,31]]}}}