"space construction" .
_:N9e51b5d240674cfdb6de4b08669991b7 .
.
_:N16b472b2f3bc4a3d969b6b5f0fabfb5c .
"first theoretical investigation" .
"error probability" .
_:Nc72632ec70fd4ea3a442057edb502989 _:Na45e04593cd0436780af792f81bfd114 .
_:Na45e04593cd0436780af792f81bfd114 _:N930cea0cb4a34133be26b8fb66a8464b .
.
"problem" .
"Yogev" .
"queries" .
"https://doi.org/10.1007/978-3-642-45030-3_48" .
_:Nc212fca8fce24ff1a8c9f6dfaacc19fe .
"paper" .
.
.
_:N23d9aef0081f4d64926a486e9eeadb2b "978-3-642-45030-3" .
"Mathematical Sciences" .
"513-523" .
"elements" .
_:Nb0b830f27adb4da79f300e6205d152fb _:N00b01937ff0049e2a2dcee704192d5ca .
"Statistics" .
_:N23d9aef0081f4d64926a486e9eeadb2b "Algorithms and Computation" .
"false"^^ .
"chapter" .
_:N6e19e570e9dc4249b582bfb3acc1f98a "Leizhen" .
"probability" .
"structure" .
"space" .
.
"filter" .
_:N23d9aef0081f4d64926a486e9eeadb2b "978-3-642-45029-7" .
_:Nc05091bbfd58486aba65caaa278a8784 "Springer Nature - SN SciGraph project" .
"stream of elements" .
_:Nb0b830f27adb4da79f300e6205d152fb .
.
_:Nc05091bbfd58486aba65caaa278a8784 .
_:Nc72632ec70fd4ea3a442057edb502989 .
_:Nc212fca8fce24ff1a8c9f6dfaacc19fe .
_:Naaa12ec48a49497b850562fe08d03156 .
"Bloom filter" .
"A Bloom filter is a method for reducing the space (memory) required for representing a set by allowing a small error probability. In this paper we consider a Sliding Bloom Filter: a data structure that, given a stream of elements, supports membership queries of the set of the last n elements (a sliding window), while allowing a small error probability and a slackness parameter. The problem of sliding Bloom filters has appeared in the literature in several communities, but this work is the first theoretical investigation of it.We formally define the data structure and its relevant parameters and analyze the time and memory requirements needed to achieve them. We give a low space construction that runs in O(1) time per update with high probability (that is, for all sequences with high probability all operations take constant time) and provide an almost matching lower bound on the space that shows that our construction has the best possible space consumption up to an additive lower order term." .
"Eylon" .
.
"update" .
_:N6e19e570e9dc4249b582bfb3acc1f98a "Cai" .
"en" .
_:N23d9aef0081f4d64926a486e9eeadb2b .
_:Nc05091bbfd58486aba65caaa278a8784 .
"2013" .
"streams" .
"Sliding Bloom Filters" .
"work" .
"membership queries" .
_:Na45e04593cd0436780af792f81bfd114 _:Nb0b830f27adb4da79f300e6205d152fb .
"construction" .
"https://scigraph.springernature.com/explorer/license/" .
"requirements" .
.
"method" .
.
"high probability" .
"relevant parameters" .
"chapters" .
_:N23d9aef0081f4d64926a486e9eeadb2b .
_:N930cea0cb4a34133be26b8fb66a8464b "Cheng" .
.
_:N930cea0cb4a34133be26b8fb66a8464b .
"lower order terms" .
.
"set" .
"2013-01-01" .
"parameters" .
"community" .
"Naor" .
_:Naaa12ec48a49497b850562fe08d03156 "pub.1020480472" .
"small error probability" .
_:N9e51b5d240674cfdb6de4b08669991b7 .
_:Ncfb2515bb5ed4451bfdea090b11936e0 "doi" .
"2022-05-20T07:45" .
"Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel" .
"theoretical investigation" .
"Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel" .
_:N00b01937ff0049e2a2dcee704192d5ca "Lam" .
.
_:Ncfb2515bb5ed4451bfdea090b11936e0 .
_:Naaa12ec48a49497b850562fe08d03156 .
"memory requirements" .
"space consumption" .
.
_:N16b472b2f3bc4a3d969b6b5f0fabfb5c .
"consumption" .
_:Ncfb2515bb5ed4451bfdea090b11936e0 .
_:N6e19e570e9dc4249b582bfb3acc1f98a .
"Moni" .
"investigation" .
_:Nc212fca8fce24ff1a8c9f6dfaacc19fe _:N9e51b5d240674cfdb6de4b08669991b7 .
"time" .
_:Naaa12ec48a49497b850562fe08d03156 "dimensions_id" .
_:N00b01937ff0049e2a2dcee704192d5ca "Tak-Wah" .
"order terms" .
_:N16b472b2f3bc4a3d969b6b5f0fabfb5c "Springer Nature" .
.
"literature" .
.
.
_:Ncfb2515bb5ed4451bfdea090b11936e0 "10.1007/978-3-642-45030-3_48" .
_:N930cea0cb4a34133be26b8fb66a8464b "Siu-Wing" .
_:Nc72632ec70fd4ea3a442057edb502989 _:N6e19e570e9dc4249b582bfb3acc1f98a .
_:N00b01937ff0049e2a2dcee704192d5ca .
.
"terms" .
"data structure" .