{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T07:35:34Z","timestamp":1725521734396},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540921813"},{"type":"electronic","value":"9783540921820"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-92182-0_8","type":"book-chapter","created":{"date-parts":[[2008,12,10]],"date-time":"2008-12-10T02:38:06Z","timestamp":1228876686000},"page":"52-63","source":"Crossref","is-referenced-by-count":4,"title":["Data Stream Algorithms via Expander Graphs"],"prefix":"10.1007","author":[{"given":"Sumit","family":"Ganguly","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"8_CR1","unstructured":"Alon, N.: Perturbed identity matrices have high rank: proof and applications (2006), http:\/\/www.math.tau.ac.il\/~nogaa\/identity.pdf"},{"key":"8_CR2","unstructured":"Bose, P., Kranakis, E., Morin, P., Tang, Y.: Bounds for Frequency Estimation of Packet Streams. In: Proc. of SIROCCO, pp. 33\u201342 (2003)"},{"issue":"2","key":"8_CR3","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1109\/TIT.2005.862083","volume":"52","author":"E. Cand\u00e8s","year":"2006","unstructured":"Cand\u00e8s, E., Romberg, J., Tao, T.: Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory\u00a052(2), 489\u2013509 (2006)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"8_CR4","doi-asserted-by":"crossref","unstructured":"Capalbo, M., Reingold, O., Vadhan, S., Wigderson, A.: Randomness conductors and constant degree lossless expanders. In: Proc. of ACM STOC (2002)","DOI":"10.1145\/510002.510003"},{"key":"8_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":"8_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1007\/11537311_24","volume-title":"Fundamentals of Computation Theory","author":"B. Cheblus","year":"2005","unstructured":"Cheblus, B., Kowalski, D.R.: Almost Optimal Explicit Selectors. In: Li\u015bkiewicz, M., Reischuk, R. (eds.) FCT 2005. LNCS, vol.\u00a03623, pp. 270\u2013280. Springer, Heidelberg (2005)"},{"key":"8_CR7","doi-asserted-by":"crossref","unstructured":"Cormode, G., Muthukrishnan, S.: An Improved Data Stream Summary: The Count-Min Sketch and its Applications. J. Algo.\u00a055(1)","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"8_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/3-540-45061-0_8","volume-title":"Automata, Languages and Programming","author":"A. Bonis De","year":"2003","unstructured":"De Bonis, A., G\u00e0sieniec, L., Vaccaro, U.: Generalized framework for selectors with applications in optimal group testing. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 81\u201396. Springer, Heidelberg (2003)"},{"key":"8_CR9","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":"4","key":"8_CR10","doi-asserted-by":"publisher","first-page":"1289","DOI":"10.1109\/TIT.2006.871582","volume":"52","author":"D. Donoho","year":"2006","unstructured":"Donoho, D.: Compressed sensing. IEEE Trans. Inf. Theory\u00a052(4), 1289\u20131306 (2006)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"8_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1007\/978-3-540-73951-7_55","volume-title":"Algorithms and Data Structures","author":"D. Eppstein","year":"2007","unstructured":"Eppstein, D., Goodrich, M.T.: Space-Efficient Straggler Identification in Round-Trip Data Streams. In: Dehne, F., Sack, J.-R., Zeh, N. (eds.) WADS 2007. LNCS, vol.\u00a04619, pp. 637\u2013648. Springer, Heidelberg (2007)"},{"key":"8_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1007\/11602613_51","volume-title":"Algorithms and Computation","author":"S. Ganguly","year":"2005","unstructured":"Ganguly, S.: Counting distinct items over update streams. In: Deng, X., Du, D.-Z. (eds.) ISAAC 2005. LNCS, vol.\u00a03827, pp. 505\u2013514. Springer, Heidelberg (2005)"},{"key":"8_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1007\/978-3-540-79709-8_22","volume-title":"Computer Science \u2013 Theory and Applications","author":"S. Ganguly","year":"2008","unstructured":"Ganguly, S.: Lower bounds for frequency estimation over data streams. In: Hirsch, E.A., Razborov, A.A., Semenov, A., Slissenko, A. (eds.) Computer Science \u2013 Theory and Applications. LNCS, vol.\u00a05010, pp. 204\u2013215. Springer, Heidelberg (2008)"},{"key":"8_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"48","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, pp. 48\u201359. Springer, Heidelberg (2007)"},{"key":"8_CR15","doi-asserted-by":"crossref","unstructured":"Ganguly, S., Majumder, A.: Deterministic K-set Structure. In: Proc. ACM PODS, pp. 280\u2013289 (2006)","DOI":"10.1145\/1142351.1142392"},{"key":"8_CR16","doi-asserted-by":"crossref","unstructured":"Ganguly, S., Majumder, A.: Deterministic K-set Structure. Manuscript under review (July 2006), http:\/\/www.cse.iitk.ac.in\/users\/sganguly","DOI":"10.1145\/1142351.1142392"},{"key":"8_CR17","doi-asserted-by":"crossref","unstructured":"Gilbert, A., Guha, S., Indyk, P., Kotidis, Y., Muthukrishnan, S., Strauss, M.: Fast Small-space Algorithms for Approximate Histogram Maintenance. In: Proc. ACM STOC, pp. 152\u2013161 (2002)","DOI":"10.1145\/509907.509966"},{"key":"8_CR18","doi-asserted-by":"crossref","unstructured":"Gilbert, A., Strauss, M., Tropp, J., Vershynin, R.: One sketch for all: Fast algorithms for Compressed Sensing. In: Proc. ACM STOC (2007)","DOI":"10.1145\/1250790.1250824"},{"key":"8_CR19","doi-asserted-by":"crossref","unstructured":"Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Draft of book (2006)","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"8_CR20","unstructured":"Indyk, P.: Explicit Constructions for Compressed Sensing of Sparse Signals. In: Proc. ACM SODA (2008)"},{"issue":"1","key":"8_CR21","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":"8_CR22","doi-asserted-by":"crossref","unstructured":"Minsky, Y., Trachtenberg, A., Zippel, R.: Set Reconciliation with Nearly Optimal Communication Complexity. IEEE Trans. Inf. Theory\u00a049(9), 2213\u20132218","DOI":"10.1109\/TIT.2003.815784"},{"key":"8_CR23","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."},{"key":"8_CR24","unstructured":"Schmidt, J., Siegel, A., Srinivasan, A.: Chernoff-Hoeffding Bounds with Applications for Limited Independence. In: Proc. ACM SODA, pp. 331\u2013340 (1992)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-92182-0_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T03:44:25Z","timestamp":1557978265000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-92182-0_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540921813","9783540921820"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-92182-0_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}