2013
AUTHORS ABSTRACTA 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. More... »
PAGES513-523
Algorithms and Computation
ISBN
978-3-642-45029-7
978-3-642-45030-3
http://scigraph.springernature.com/pub.10.1007/978-3-642-45030-3_48
DOIhttp://dx.doi.org/10.1007/978-3-642-45030-3_48
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1020480472
JSON-LD is the canonical representation for SciGraph data.
TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT
[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
"about": [
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Mathematical Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0104",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Statistics",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel",
"id": "http://www.grid.ac/institutes/grid.13992.30",
"name": [
"Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel"
],
"type": "Organization"
},
"familyName": "Naor",
"givenName": "Moni",
"id": "sg:person.07776170271.83",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel",
"id": "http://www.grid.ac/institutes/grid.13992.30",
"name": [
"Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel"
],
"type": "Organization"
},
"familyName": "Yogev",
"givenName": "Eylon",
"id": "sg:person.015120037757.44",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015120037757.44"
],
"type": "Person"
}
],
"datePublished": "2013",
"datePublishedReg": "2013-01-01",
"description": "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.",
"editor": [
{
"familyName": "Cai",
"givenName": "Leizhen",
"type": "Person"
},
{
"familyName": "Cheng",
"givenName": "Siu-Wing",
"type": "Person"
},
{
"familyName": "Lam",
"givenName": "Tak-Wah",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-642-45030-3_48",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-642-45029-7",
"978-3-642-45030-3"
],
"name": "Algorithms and Computation",
"type": "Book"
},
"keywords": [
"small error probability",
"lower order terms",
"error probability",
"stream of elements",
"order terms",
"data structure",
"space construction",
"theoretical investigation",
"memory requirements",
"relevant parameters",
"Bloom filter",
"probability",
"space",
"filter",
"first theoretical investigation",
"high probability",
"parameters",
"set",
"space consumption",
"problem",
"membership queries",
"construction",
"structure",
"terms",
"elements",
"queries",
"time",
"work",
"consumption",
"requirements",
"streams",
"method",
"investigation",
"update",
"literature",
"community",
"paper"
],
"name": "Sliding Bloom Filters",
"pagination": "513-523",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1020480472"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-642-45030-3_48"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-642-45030-3_48",
"https://app.dimensions.ai/details/publication/pub.1020480472"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-05-20T07:45",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_295.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-642-45030-3_48"
}
]
Download the RDF metadata as: json-ld nt turtle xml License info
JSON-LD is a popular format for linked data which is fully compatible with JSON.
curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-45030-3_48'
N-Triples is a line-based linked data format ideal for batch operations.
curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-45030-3_48'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-45030-3_48'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-45030-3_48'
This table displays all metadata directly associated to this object as RDF triples.
114 TRIPLES
23 PREDICATES
63 URIs
56 LITERALS
7 BLANK NODES
Subject | Predicate | Object | |
---|---|---|---|
1 | sg:pub.10.1007/978-3-642-45030-3_48 | schema:about | anzsrc-for:01 |
2 | ″ | ″ | anzsrc-for:0104 |
3 | ″ | schema:author | N5d0f27c7bccd471e8a82ac4c56f299a4 |
4 | ″ | schema:datePublished | 2013 |
5 | ″ | schema:datePublishedReg | 2013-01-01 |
6 | ″ | schema:description | 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. |
7 | ″ | schema:editor | N083e89c8710a4481922470314b28b70f |
8 | ″ | schema:genre | chapter |
9 | ″ | schema:inLanguage | en |
10 | ″ | schema:isAccessibleForFree | false |
11 | ″ | schema:isPartOf | N8a2ae50a3f384f958dfd4259e1a1214b |
12 | ″ | schema:keywords | Bloom filter |
13 | ″ | ″ | community |
14 | ″ | ″ | construction |
15 | ″ | ″ | consumption |
16 | ″ | ″ | data structure |
17 | ″ | ″ | elements |
18 | ″ | ″ | error probability |
19 | ″ | ″ | filter |
20 | ″ | ″ | first theoretical investigation |
21 | ″ | ″ | high probability |
22 | ″ | ″ | investigation |
23 | ″ | ″ | literature |
24 | ″ | ″ | lower order terms |
25 | ″ | ″ | membership queries |
26 | ″ | ″ | memory requirements |
27 | ″ | ″ | method |
28 | ″ | ″ | order terms |
29 | ″ | ″ | paper |
30 | ″ | ″ | parameters |
31 | ″ | ″ | probability |
32 | ″ | ″ | problem |
33 | ″ | ″ | queries |
34 | ″ | ″ | relevant parameters |
35 | ″ | ″ | requirements |
36 | ″ | ″ | set |
37 | ″ | ″ | small error probability |
38 | ″ | ″ | space |
39 | ″ | ″ | space construction |
40 | ″ | ″ | space consumption |
41 | ″ | ″ | stream of elements |
42 | ″ | ″ | streams |
43 | ″ | ″ | structure |
44 | ″ | ″ | terms |
45 | ″ | ″ | theoretical investigation |
46 | ″ | ″ | time |
47 | ″ | ″ | update |
48 | ″ | ″ | work |
49 | ″ | schema:name | Sliding Bloom Filters |
50 | ″ | schema:pagination | 513-523 |
51 | ″ | schema:productId | N009231635fff44f1b976bd6993f0e1a2 |
52 | ″ | ″ | N4030b946efe243f1a0b9c4bb317ec8fc |
53 | ″ | schema:publisher | N3020ce9268b040d995bfcbb335f2349e |
54 | ″ | schema:sameAs | https://app.dimensions.ai/details/publication/pub.1020480472 |
55 | ″ | ″ | https://doi.org/10.1007/978-3-642-45030-3_48 |
56 | ″ | schema:sdDatePublished | 2022-05-20T07:45 |
57 | ″ | schema:sdLicense | https://scigraph.springernature.com/explorer/license/ |
58 | ″ | schema:sdPublisher | Nde8da78122b8440a9484215709be9984 |
59 | ″ | schema:url | https://doi.org/10.1007/978-3-642-45030-3_48 |
60 | ″ | sgo:license | sg:explorer/license/ |
61 | ″ | sgo:sdDataset | chapters |
62 | ″ | rdf:type | schema:Chapter |
63 | N009231635fff44f1b976bd6993f0e1a2 | schema:name | doi |
64 | ″ | schema:value | 10.1007/978-3-642-45030-3_48 |
65 | ″ | rdf:type | schema:PropertyValue |
66 | N083e89c8710a4481922470314b28b70f | rdf:first | N5ed4d0b7c9bf4b24871c4081cb8a3304 |
67 | ″ | rdf:rest | Ne06893a5ce2e4c6488bbeacc50ace55f |
68 | N3020ce9268b040d995bfcbb335f2349e | schema:name | Springer Nature |
69 | ″ | rdf:type | schema:Organisation |
70 | N4030b946efe243f1a0b9c4bb317ec8fc | schema:name | dimensions_id |
71 | ″ | schema:value | pub.1020480472 |
72 | ″ | rdf:type | schema:PropertyValue |
73 | N4af3ef8229944ed58d972e1ed8e87612 | schema:familyName | Cheng |
74 | ″ | schema:givenName | Siu-Wing |
75 | ″ | rdf:type | schema:Person |
76 | N5d0f27c7bccd471e8a82ac4c56f299a4 | rdf:first | sg:person.07776170271.83 |
77 | ″ | rdf:rest | N948697bf30ee4b9f8f55767dadff1f07 |
78 | N5ed4d0b7c9bf4b24871c4081cb8a3304 | schema:familyName | Cai |
79 | ″ | schema:givenName | Leizhen |
80 | ″ | rdf:type | schema:Person |
81 | N8a2ae50a3f384f958dfd4259e1a1214b | schema:isbn | 978-3-642-45029-7 |
82 | ″ | ″ | 978-3-642-45030-3 |
83 | ″ | schema:name | Algorithms and Computation |
84 | ″ | rdf:type | schema:Book |
85 | N948697bf30ee4b9f8f55767dadff1f07 | rdf:first | sg:person.015120037757.44 |
86 | ″ | rdf:rest | rdf:nil |
87 | Nd43be1c5e6204fda86096c03aa089da7 | schema:familyName | Lam |
88 | ″ | schema:givenName | Tak-Wah |
89 | ″ | rdf:type | schema:Person |
90 | Nde22fb2d457a4dd99e5e920daaf1a46e | rdf:first | Nd43be1c5e6204fda86096c03aa089da7 |
91 | ″ | rdf:rest | rdf:nil |
92 | Nde8da78122b8440a9484215709be9984 | schema:name | Springer Nature - SN SciGraph project |
93 | ″ | rdf:type | schema:Organization |
94 | Ne06893a5ce2e4c6488bbeacc50ace55f | rdf:first | N4af3ef8229944ed58d972e1ed8e87612 |
95 | ″ | rdf:rest | Nde22fb2d457a4dd99e5e920daaf1a46e |
96 | anzsrc-for:01 | schema:inDefinedTermSet | anzsrc-for: |
97 | ″ | schema:name | Mathematical Sciences |
98 | ″ | rdf:type | schema:DefinedTerm |
99 | anzsrc-for:0104 | schema:inDefinedTermSet | anzsrc-for: |
100 | ″ | schema:name | Statistics |
101 | ″ | rdf:type | schema:DefinedTerm |
102 | sg:person.015120037757.44 | schema:affiliation | grid-institutes:grid.13992.30 |
103 | ″ | schema:familyName | Yogev |
104 | ″ | schema:givenName | Eylon |
105 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015120037757.44 |
106 | ″ | rdf:type | schema:Person |
107 | sg:person.07776170271.83 | schema:affiliation | grid-institutes:grid.13992.30 |
108 | ″ | schema:familyName | Naor |
109 | ″ | schema:givenName | Moni |
110 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83 |
111 | ″ | rdf:type | schema:Person |
112 | grid-institutes:grid.13992.30 | schema:alternateName | Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel |
113 | ″ | schema:name | Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel |
114 | ″ | rdf:type | schema:Organization |