{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,6]],"date-time":"2025-02-06T08:10:02Z","timestamp":1738829402228,"version":"3.37.0"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2008,12,18]],"date-time":"2008-12-18T00:00:00Z","timestamp":1229558400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2009,4]]},"DOI":"10.1007\/s00453-008-9260-5","type":"journal-article","created":{"date-parts":[[2008,12,17]],"date-time":"2008-12-17T20:36:29Z","timestamp":1229546189000},"page":"549-582","source":"Crossref","is-referenced-by-count":4,"title":["Hierarchical Sampling from Sketches: Estimating\u00a0Functions over Data Streams"],"prefix":"10.1007","volume":"53","author":[{"given":"Sumit","family":"Ganguly","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lakshminath","family":"Bhuvanagiri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,12,18]]},"reference":[{"issue":"1","key":"9260_CR1","doi-asserted-by":"crossref","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.\u00a0Comput. Syst. Sci. 58(1), 137\u2013147 (1998)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9260_CR2","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 the ACM Symposium on Theory of Computing, 2002","DOI":"10.1109\/SFCS.2002.1181944"},{"key":"9260_CR3","doi-asserted-by":"crossref","unstructured":"Bhuvanagiri, L., Ganguly, S.: Estimating entropy over data streams. In: Proceedings of the European Symposium on Algorithms, pp.\u00a0148\u2013159 (2006)","DOI":"10.1007\/11841036_16"},{"issue":"2","key":"9260_CR4","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","volume":"18","author":"J.L. Carter","year":"1979","unstructured":"Carter, J.L., Wegman, M.N.: Universal classes of hash functions. J. Comput. Syst. Sci. 18(2), 143\u2013154 (1979)","journal-title":"J. Comput. Syst. Sci."},{"key":"9260_CR5","doi-asserted-by":"crossref","unstructured":"Chakrabarti, A., Ba, D.K., Muthukrishnan, S.: Estimating entropy and entropy norm on data streams. In: Proceedings of the Symposium on Theoretical Aspects of Computer Science, 2006","DOI":"10.1007\/11672142_15"},{"key":"9260_CR6","unstructured":"Chakrabarti, A., Cormode, G., McGregor, A.: A near-optimal algorithm for computing the entropy of a stream. In: Proceedings of the ACM Symposium on Discrete Algorithms, 2007"},{"key":"9260_CR7","doi-asserted-by":"crossref","unstructured":"Chakrabarti, A., Khot, S., Sun, X.: Near-optimal lower bounds on the multi-party communication complexity of set disjointness. In: Proceedings of the Conference on Computational Complexity, 2003","DOI":"10.1109\/CCC.2003.1214414"},{"key":"9260_CR8","doi-asserted-by":"crossref","unstructured":"Charikar, M., Chen, K., Farach-Colton, M.: Finding frequent items in data streams. In: Proceedings of the International Colloquium on Automata, Languages and Programming, pp. 693\u2013703 (2002)","DOI":"10.1007\/3-540-45465-9_59"},{"key":"9260_CR9","unstructured":"Coppersmith, D., Kumar, R.: An improved data stream algorithm for estimating frequency moments. In: Proceedings of the ACM Symposium on Discrete Algorithms, pp. 151\u2013156 (2004)"},{"issue":"1","key":"9260_CR10","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1016\/j.jalgor.2003.12.001","volume":"55","author":"G. Cormode","year":"2005","unstructured":"Cormode, G., Muthukrishnan, S.: An improved data stream summary: The count-min sketch and its applications. J. Algorithms 55(1), 58\u201375 (2005)","journal-title":"J. Algorithms"},{"issue":"2","key":"9260_CR11","doi-asserted-by":"crossref","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. Comput. Syst. Sci. 31(2), 182\u2013209 (1985)","journal-title":"J. Comput. Syst. Sci."},{"key":"9260_CR12","unstructured":"Ganguly, S.: A hybrid technique for estimating frequency moments over data streams. Manuscript (July 2004)"},{"key":"9260_CR13","doi-asserted-by":"crossref","unstructured":"Ganguly, S.: Estimating frequency moments of update streams using random linear combinations. In: Proceedings of the International Workshop on Randomization and Computation (RANDOM), 2004","DOI":"10.1007\/978-3-540-27821-4_33"},{"key":"9260_CR14","doi-asserted-by":"crossref","unstructured":"Ganguly, S., Kesh, D., Saha, C.: Practical algorithms for tracking database join sizes. In: Proceedings of the FSTTCS, December 2005, pp. 294\u2013305","DOI":"10.1007\/11590156_24"},{"key":"9260_CR15","doi-asserted-by":"crossref","unstructured":"Gu, Y., McCallum, A., Towsley, D.: Detecting anomalies in network traffic using maximum entropy estimation. In: Proceedings of Internet Measurement Conference, pp. 345\u2013350 (2005)","DOI":"10.1145\/1330107.1330148"},{"key":"9260_CR16","doi-asserted-by":"crossref","unstructured":"Guha, S., McGregor, A., Venkatsubramanian, S.: Streaming and sublinear approximation of entropy and information distances. In: Proceedings of the ACM Symposium on Discrete Algorithms, 2006","DOI":"10.1145\/1109557.1109637"},{"key":"9260_CR17","doi-asserted-by":"crossref","unstructured":"Indyk, P.: Stable distributions, pseudo-random generators, embeddings and data stream computation. In: Proceedings of the IEEE Foundations of Computer Science, pp. 189\u2013197 (2000)","DOI":"10.1109\/SFCS.2000.892082"},{"key":"9260_CR18","doi-asserted-by":"crossref","unstructured":"Indyk, P., Woodruff, D.: Optimal approximations of the frequency moments. In: Proceedings of the ACM Symposium on Theory of Computing, pp. 202\u2013298 (2005)","DOI":"10.1145\/1060590.1060621"},{"key":"9260_CR19","doi-asserted-by":"crossref","unstructured":"Nisan, N.: Pseudo-random generators for space bounded computation. In: Proceedings of the ACM Symposium on Theory of Computing, 1990","DOI":"10.1145\/100216.100242"},{"key":"9260_CR20","doi-asserted-by":"crossref","unstructured":"Saks, M., Sun, X.: Space lower bounds for distance approximation in the data stream model. In: Proceedings of the ACM Symposium on Theory of Computing, 2002","DOI":"10.1145\/509907.509963"},{"key":"9260_CR21","unstructured":"Thorup, M., Zhang, Y.: Tabulation based 4-universal hashing with applications to second moment estimation. In: Proceedings of the ACM Symposium on Discrete Algorithms, January 2004, pp. 615\u2013624"},{"key":"9260_CR22","doi-asserted-by":"crossref","unstructured":"Wagner, A., Plattner, B.: Entropy based worm and anomaly detection in fast IP networks. In: 14th IEEE WET ICE, STCA Security Workshop, 2005","DOI":"10.1109\/WETICE.2005.35"},{"key":"9260_CR23","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0022-0000(81)90033-7","volume":"22","author":"M.N. Wegman","year":"1981","unstructured":"Wegman, M.N., Carter, J.L.: New hash functions and their use in authentication and set equality. J.\u00a0Comput. Syst. Sci. 22, 265\u2013279 (1981)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9260_CR24","unstructured":"Woodruff, D.P.: Optimal space lower bounds for all frequency moments. In: Proceedings of the ACM Symposium on Discrete Algorithms, pp. 167\u2013175 (2004)"},{"issue":"4","key":"9260_CR25","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1145\/1090191.1080112","volume":"35","author":"K. Xu","year":"2005","unstructured":"Xu, K., Zhang, Z., Bhattacharyya, S.: Profiling Internet backbone traffic: behavior models and applications. SIGCOMM Comput. Commun. Rev. 35(4), 169\u2013180 (2005)","journal-title":"SIGCOMM Comput. Commun. Rev."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9260-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-008-9260-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9260-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,6]],"date-time":"2025-02-06T07:08:16Z","timestamp":1738825696000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-008-9260-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,12,18]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,4]]}},"alternative-id":["9260"],"URL":"https:\/\/doi.org\/10.1007\/s00453-008-9260-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2008,12,18]]}}}