{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T20:53:39Z","timestamp":1725742419769},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642401633"},{"type":"electronic","value":"9783642401640"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40164-0_8","type":"book-chapter","created":{"date-parts":[[2013,7,21]],"date-time":"2013-07-21T21:01:30Z","timestamp":1374440490000},"page":"48-59","source":"Crossref","is-referenced-by-count":2,"title":["Efficient Sampling of Non-strict Turnstile Data Streams"],"prefix":"10.1007","author":[{"given":"Neta","family":"Barkay","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ely","family":"Porat","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bar","family":"Shalem","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"Cohen, E., Cormode, G., Duffield, N.G.: Don\u2019t let the negatives bring you down: sampling from streams of signed updates. In: SIGMETRICS, pp. 343\u2013354 (2012)","DOI":"10.1145\/2318857.2254798"},{"issue":"3","key":"8_CR2","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1109\/TKDE.2003.1198388","volume":"15","author":"G. Cormode","year":"2003","unstructured":"Cormode, G., Datar, M., Indyk, P., Muthukrishnan, S.: Comparing data streams using hamming norms (how to zero in). IEEE Trans. Knowl. Data Eng.\u00a015(3), 529\u2013540 (2003)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"8_CR3","doi-asserted-by":"crossref","unstructured":"Cormode, G., Muthukrishnan, S., Rozenbaum, I.: Summarizing and mining inverse distributions on data streams via dynamic inverse sampling. In: VLDB, pp. 25\u201336 (2005)","DOI":"10.1137\/1.9781611972757.5"},{"key":"8_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/3-540-45749-6_31","volume-title":"Algorithms - ESA 2002","author":"M. Datar","year":"2002","unstructured":"Datar, M., Muthukrishnan, S.M.: Estimating rarity and similarity over data stream windows. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.\u00a02461, pp. 323\u2013334. Springer, Heidelberg (2002)"},{"issue":"2","key":"8_CR5","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/(SICI)1098-2418(199809)13:2<99::AID-RSA1>3.0.CO;2-M","volume":"13","author":"D.P. Dubhashi","year":"1998","unstructured":"Dubhashi, D.P., Ranjan, D.: Balls and bins: A study in negative dependence. Random Struct. Algorithms\u00a013(2), 99\u2013124 (1998)","journal-title":"Random Struct. Algorithms"},{"key":"8_CR6","doi-asserted-by":"crossref","unstructured":"Frahling, G., Indyk, P., Sohler, C.: Sampling in dynamic data streams and applications. In: Symposium on Computational Geometry, pp. 142\u2013149 (2005)","DOI":"10.1145\/1064092.1064116"},{"issue":"1\/2","key":"8_CR7","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1142\/S0218195908002520","volume":"18","author":"G. Frahling","year":"2008","unstructured":"Frahling, G., Indyk, P., Sohler, C.: Sampling in dynamic data streams and applications. Int. J. Comput. Geometry Appl.\u00a018(1\/2), 3\u201328 (2008)","journal-title":"Int. J. Comput. Geometry Appl."},{"issue":"3","key":"8_CR8","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/j.tcs.2007.02.031","volume":"378","author":"S. Ganguly","year":"2007","unstructured":"Ganguly, S.: Counting distinct items over update streams. Theor. Comput. Sci.\u00a0378(3), 211\u2013222 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"8_CR9","volume-title":"Modern computer algebra","author":"J. von zur Gathen","year":"1999","unstructured":"von zur Gathen, J., Gerhard, J.: Modern computer algebra. Cambridge University Press, New York (1999)"},{"key":"8_CR10","unstructured":"Gemulla, R., Lehner, W., Haas, P.J.: A dip in the reservoir: Maintaining sample synopses of evolving datasets. In: VLDB, pp. 595\u2013606 (2006)"},{"key":"8_CR11","doi-asserted-by":"crossref","unstructured":"Gemulla, R., Lehner, W., Haas, P.J.: Maintaining bernoulli samples over evolving multisets. In: PODS, pp. 93\u2013102 (2007)","DOI":"10.1145\/1265530.1265544"},{"key":"8_CR12","unstructured":"Gibbons, P.B.: Distinct sampling for highly-accurate answers to distinct values queries and event reports. In: VLDB, pp. 541\u2013550 (2001)"},{"key":"8_CR13","doi-asserted-by":"crossref","unstructured":"Gilbert, A.C., Li, Y., Porat, E., Strauss, M.J.: Approximate sparse recovery: optimizing time and measurements. In: STOC, pp. 475\u2013484 (2010)","DOI":"10.1145\/1806689.1806755"},{"issue":"4","key":"8_CR14","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1006\/jcom.1994.1021","volume":"10","author":"I. Gohberg","year":"1994","unstructured":"Gohberg, I., Olshevsky, V.: Fast algorithms with preprocessing for matrix-vector multiplication problems. J. Complexity\u00a010(4), 411\u2013427 (1994)","journal-title":"J. Complexity"},{"key":"8_CR15","doi-asserted-by":"crossref","unstructured":"Goodrich, M.T., Mitzenmacher, M.: Invertible bloom lookup tables. In: 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 792\u2013799. IEEE (2011)","DOI":"10.1109\/Allerton.2011.6120248"},{"issue":"1","key":"8_CR16","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1006\/jagm.2000.1131","volume":"38","author":"P. Indyk","year":"2001","unstructured":"Indyk, P.: A small approximately min-wise independent family of hash functions. J. Algorithms\u00a038(1), 84\u201390 (2001)","journal-title":"J. Algorithms"},{"key":"8_CR17","doi-asserted-by":"crossref","unstructured":"Jowhari, H., Saglam, M., Tardos, G.: Tight bounds for lp samplers, finding duplicates in streams, and related problems. In: PODS, pp. 49\u201358 (2011)","DOI":"10.1145\/1989284.1989289"},{"key":"8_CR18","doi-asserted-by":"crossref","unstructured":"Kane, D.M., Nelson, J., Woodruff, D.P.: An optimal algorithm for the distinct elements problem. In: PODS, pp. 41\u201352 (2010)","DOI":"10.1145\/1807085.1807094"},{"key":"8_CR19","doi-asserted-by":"crossref","unstructured":"Karamcheti, V., Geiger, D., Kedem, Z.M., Muthukrishnan, S.: Detecting malicious network traffic using inverse distributions of packet contents. In: MineNet, pp. 165\u2013170 (2005)","DOI":"10.1145\/1080173.1080176"},{"key":"8_CR20","doi-asserted-by":"crossref","unstructured":"Micciancio, D.: Oblivious data structures: Applications to cryptography. In: STOC, pp. 456\u2013464 (1997)","DOI":"10.1145\/258533.258638"},{"key":"8_CR21","doi-asserted-by":"crossref","unstructured":"Monemizadeh, M., Woodruff, D.P.: 1-pass relative-error lp-sampling with applications. In: SODA, pp. 1143\u20131160 (2010)","DOI":"10.1137\/1.9781611973075.92"},{"key":"8_CR22","doi-asserted-by":"crossref","unstructured":"Muthukrishnan, S.: Data streams: Algorithms and applications. Foundations and Trends in Theoretical Computer Science\u00a01(2) (2005)","DOI":"10.1561\/0400000002"},{"key":"8_CR23","doi-asserted-by":"crossref","unstructured":"Naor, M., Teague, V.: Anti-persistence: History independent data structures. IACR Cryptology ePrint Archive 2001, 36 (2001)","DOI":"10.1145\/380752.380844"},{"issue":"1","key":"8_CR24","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1137\/060658400","volume":"38","author":"A. Pagh","year":"2008","unstructured":"Pagh, A., Pagh, R.: Uniform hashing in constant time and optimal space. SIAM J. Comput.\u00a038(1), 85\u201396 (2008)","journal-title":"SIAM J. Comput."},{"key":"8_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/978-3-540-73437-6_19","volume-title":"Combinatorial Pattern Matching","author":"E. Porat","year":"2007","unstructured":"Porat, E., Lipsky, O.: Improved sketching of hamming distance with error correcting. In: Ma, B., Zhang, K. (eds.) CPM 2007. LNCS, vol.\u00a04580, pp. 173\u2013182. Springer, Heidelberg (2007)"},{"issue":"2","key":"8_CR26","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1137\/0108018","volume":"8","author":"I. Reed","year":"1960","unstructured":"Reed, I., Golomb, S.: Polynomial codes over certain finite fields. Joint Society of Industrial and Applied Mathematics Journal\u00a08(2), 300\u2013304 (1960)","journal-title":"Joint Society of Industrial and Applied Mathematics Journal"},{"issue":"1","key":"8_CR27","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1109\/TKDE.2007.250588","volume":"19","author":"Y. Tao","year":"2007","unstructured":"Tao, Y., Lian, X., Papadias, D., Hadjieleftheriou, M.: Random sampling for continuous streams with arbitrary updates. IEEE Trans. Knowl. Data Eng.\u00a019(1), 96\u2013110 (2007)","journal-title":"IEEE Trans. Knowl. Data Eng."}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40164-0_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T21:38:28Z","timestamp":1557956308000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40164-0_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642401633","9783642401640"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40164-0_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}