{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,26]],"date-time":"2025-09-26T04:54:41Z","timestamp":1758862481102},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2015,5,13]],"date-time":"2015-05-13T00:00:00Z","timestamp":1431475200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2015,12]]},"DOI":"10.1007\/s00453-015-0007-9","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T08:58:14Z","timestamp":1431421094000},"page":"652-672","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Tight Bounds for Sliding Bloom Filters"],"prefix":"10.1007","volume":"73","author":[{"given":"Moni","family":"Naor","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eylon","family":"Yogev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,5,13]]},"reference":[{"key":"7_CR1","doi-asserted-by":"crossref","unstructured":"Arbitman, Y., Naor, M., Segev, G.: Backyard cuckoo hashing: constant worst-case operations with a succinct representation. FOCS, pp. 787\u2013796 (2010)","DOI":"10.1109\/FOCS.2010.80"},{"key":"7_CR2","doi-asserted-by":"crossref","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method, 3rd edn. Wiley Series in Discrete Mathematics and Optimization. Wiley (2008)","DOI":"10.1002\/9780470277331"},{"issue":"7","key":"7_CR3","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1145\/362686.362692","volume":"13","author":"BH Bloom","year":"1970","unstructured":"Bloom, B.H.: Space\/time trade-offs in hash coding with allowable errors. Commun. ACM 13(7), 422\u2013426 (1970)","journal-title":"Commun. ACM"},{"issue":"4","key":"7_CR4","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1080\/15427951.2004.10129096","volume":"1","author":"AZ Broder","year":"2003","unstructured":"Broder, A.Z., Mitzenmacher, M.: Survey: network applications of Bloom filters: a survey. Internet Math. 1(4), 485\u2013509 (2003)","journal-title":"Internet Math."},{"key":"7_CR5","doi-asserted-by":"crossref","unstructured":"Carter, L., Floyd, R.W., Gill, J., Markowsky, G., Wegman, M.N.: Exact and approximate membership testers. STOC, pp. 59\u201365 (1978)","DOI":"10.1145\/800133.804332"},{"key":"7_CR6","doi-asserted-by":"crossref","unstructured":"Chang, F., Li, K., Feng, W.-C.: Approximate caches for packet classification. INFOCOM (2004)","DOI":"10.1109\/INFCOM.2004.1354643"},{"issue":"2","key":"7_CR7","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","volume":"18","author":"JL Carter","year":"1979","unstructured":"Carter, J.L., Wegman, M.N.: Universal classes of hashfunctions. J. Comput. Syst. Sci. 18(2), 143\u2013154 (1979)","journal-title":"J. Comput. Syst. Sci."},{"key":"7_CR8","unstructured":"Demaine, E.: Lecture notes for the course \u201cAdvanced data structures\u201d. http:\/\/courses.csail.mit.edu\/6.851\/spring07\/scribe\/lec21.pdf (2007)"},{"issue":"6","key":"7_CR9","doi-asserted-by":"crossref","first-page":"1794","DOI":"10.1137\/S0097539701398363","volume":"31","author":"M Datar","year":"2002","unstructured":"Datar, M., Gionis, A., Indyk, P., Motwani, R.: Maintaining stream statistics over sliding windows. SIAM J. Comput. 31(6), 1794\u20131813 (2002)","journal-title":"SIAM J. Comput."},{"key":"7_CR10","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger, M., Pagh, R.: Succinct data structures for retrieval and approximate membership. ICALP, pp. 385\u2013396 (2008)","DOI":"10.1007\/978-3-540-70575-8_32"},{"key":"7_CR11","doi-asserted-by":"crossref","unstructured":"Deng, F., Rafiei, D.: Approximately detecting duplicates for streaming data using stable Bloom filters. SIGMOD, pp. 25\u201336 (2006)","DOI":"10.1145\/1142473.1142477"},{"issue":"3","key":"7_CR12","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1109\/90.851975","volume":"8","author":"L Fan","year":"2000","unstructured":"Fan, L., Cao, P., Almeida, J.M., Broder, A.Z.: Summary cache: a scalable wide-area web cache sharing protocol. IEEE\/ACM Trans. Netw. 8(3), 281\u2013293 (2000)","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"7_CR13","doi-asserted-by":"crossref","unstructured":"Lovett, S., Porat, E.: A lower bound for dynamic approximate membership data structures. FOCS, pp. 797\u2013804 (2010)","DOI":"10.1109\/FOCS.2010.81"},{"key":"7_CR14","doi-asserted-by":"crossref","unstructured":"Metwally, A., Agrawal, D., El Abbadi, A.: Duplicate detection in click streams. In: Proceedings of the 14th International Conference on World Wide Web. ACM Press, pp. 12\u201321 (2005)","DOI":"10.1145\/1060745.1060753"},{"key":"7_CR15","unstructured":"Pagh, A., Pagh, R., Rao, S.S.: An optimal Bloom filter replacement. SODA, pp. 823\u2013829 (2005)"},{"key":"7_CR16","doi-asserted-by":"crossref","unstructured":"Pagh, R., Segev, G., Wieder, U.: How to approximate a set without knowing its size in advance. FOCS, pp. 80\u201389 (2013)","DOI":"10.1109\/FOCS.2013.17"},{"key":"7_CR17","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Timeouts with time-reversed linear probing. INFOCOM, pp. 166\u2013170 (2011)","DOI":"10.1109\/INFCOM.2011.5934961"},{"issue":"1","key":"7_CR18","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1109\/SURV.2011.031611.00024","volume":"14","author":"S Tarkoma","year":"2012","unstructured":"Tarkoma, S., Rothenberg, C.E., Lagerspetz, E.: Theory and practice of Bloom filters for distributed systems. IEEE Commun. Surv. Tutor. 14(1), 131\u2013155 (2012)","journal-title":"IEEE Commun. Surv. Tutor."},{"issue":"1","key":"7_CR19","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1109\/TKDE.2009.136","volume":"22","author":"M Yoon","year":"2010","unstructured":"Yoon, M.: Aging Bloom filter with two active buffers for dynamic sets. IEEE Trans. Knowl. Data Eng. 22(1), 134\u2013138 (2010)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"7_CR20","doi-asserted-by":"crossref","unstructured":"Zhang, L., Guan, Y.: Detecting click fraud in pay-per-click streams of online advertising networks. ICDCS, pp. 77\u201384 (2008)","DOI":"10.1109\/ICDCS.2008.98"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0007-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0007-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0007-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,24]],"date-time":"2019-08-24T20:20:51Z","timestamp":1566678051000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0007-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,13]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,12]]}},"alternative-id":["7"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0007-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,5,13]]}}}