Sliding Bloom Filters View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2013

AUTHORS

Moni Naor , Eylon Yogev

ABSTRACT

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. More... »

PAGES

513-523

Book

TITLE

Algorithms and Computation

ISBN

978-3-642-45029-7
978-3-642-45030-3

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-45030-3_48

DOI

http://dx.doi.org/10.1007/978-3-642-45030-3_48

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1020480472


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

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": [
      "Bloom filter", 
      "data structure", 
      "small error probability", 
      "stream of elements", 
      "error probability", 
      "memory requirements", 
      "space consumption", 
      "membership queries", 
      "space construction", 
      "queries", 
      "filter", 
      "set", 
      "high probability", 
      "space", 
      "requirements", 
      "update", 
      "probability", 
      "streams", 
      "construction", 
      "relevant parameters", 
      "time", 
      "work", 
      "method", 
      "elements", 
      "consumption", 
      "parameters", 
      "terms", 
      "structure", 
      "community", 
      "lower order terms", 
      "literature", 
      "order terms", 
      "investigation", 
      "theoretical investigation", 
      "first theoretical investigation", 
      "paper", 
      "problem", 
      "Sliding Bloom Filter", 
      "slackness parameter", 
      "low space construction", 
      "best possible space consumption", 
      "possible space consumption", 
      "additive lower order term"
    ], 
    "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-01-01T19:09", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_157.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

HOW TO GET THIS DATA PROGRAMMATICALLY:

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.

120 TRIPLES      23 PREDICATES      69 URIs      62 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 Nf4169ef7af8d44bc8e426c2800b573b0
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 N3aece61ed6da4897a3ba37047db5e40a
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N84b2e708bbcb401dafffc02f95271e72
12 schema:keywords Bloom filter
13 Sliding Bloom Filter
14 additive lower order term
15 best possible space consumption
16 community
17 construction
18 consumption
19 data structure
20 elements
21 error probability
22 filter
23 first theoretical investigation
24 high probability
25 investigation
26 literature
27 low space construction
28 lower order terms
29 membership queries
30 memory requirements
31 method
32 order terms
33 paper
34 parameters
35 possible space consumption
36 probability
37 problem
38 queries
39 relevant parameters
40 requirements
41 set
42 slackness parameter
43 small error probability
44 space
45 space construction
46 space consumption
47 stream of elements
48 streams
49 structure
50 terms
51 theoretical investigation
52 time
53 update
54 work
55 schema:name Sliding Bloom Filters
56 schema:pagination 513-523
57 schema:productId N17c9f0ec6593411d8fe446731f218269
58 N6cd74a47214f4f8fa4a17cb0be4c2d55
59 schema:publisher Nda8e95716b6345a38677e6b8a222dac6
60 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020480472
61 https://doi.org/10.1007/978-3-642-45030-3_48
62 schema:sdDatePublished 2022-01-01T19:09
63 schema:sdLicense https://scigraph.springernature.com/explorer/license/
64 schema:sdPublisher Ne58b6f78a0464ff8b724b48697de5f2f
65 schema:url https://doi.org/10.1007/978-3-642-45030-3_48
66 sgo:license sg:explorer/license/
67 sgo:sdDataset chapters
68 rdf:type schema:Chapter
69 N17c9f0ec6593411d8fe446731f218269 schema:name doi
70 schema:value 10.1007/978-3-642-45030-3_48
71 rdf:type schema:PropertyValue
72 N323159d106f54277a0b2d17aa6e06b32 schema:familyName Cheng
73 schema:givenName Siu-Wing
74 rdf:type schema:Person
75 N3aece61ed6da4897a3ba37047db5e40a rdf:first N98658bc3fab840f2b3b589c8a1f1c818
76 rdf:rest N609928c22e284f1f975f9297e16666ef
77 N609928c22e284f1f975f9297e16666ef rdf:first N323159d106f54277a0b2d17aa6e06b32
78 rdf:rest Nb4bb8ee90cda4bdaa96603ad34f02dab
79 N6cd74a47214f4f8fa4a17cb0be4c2d55 schema:name dimensions_id
80 schema:value pub.1020480472
81 rdf:type schema:PropertyValue
82 N736bb05d811742e0be217d089ad6abfb schema:familyName Lam
83 schema:givenName Tak-Wah
84 rdf:type schema:Person
85 N84b2e708bbcb401dafffc02f95271e72 schema:isbn 978-3-642-45029-7
86 978-3-642-45030-3
87 schema:name Algorithms and Computation
88 rdf:type schema:Book
89 N98658bc3fab840f2b3b589c8a1f1c818 schema:familyName Cai
90 schema:givenName Leizhen
91 rdf:type schema:Person
92 Nb4bb8ee90cda4bdaa96603ad34f02dab rdf:first N736bb05d811742e0be217d089ad6abfb
93 rdf:rest rdf:nil
94 Nd5fbafef39774a2686a492fdb4f70bf0 rdf:first sg:person.015120037757.44
95 rdf:rest rdf:nil
96 Nda8e95716b6345a38677e6b8a222dac6 schema:name Springer Nature
97 rdf:type schema:Organisation
98 Ne58b6f78a0464ff8b724b48697de5f2f schema:name Springer Nature - SN SciGraph project
99 rdf:type schema:Organization
100 Nf4169ef7af8d44bc8e426c2800b573b0 rdf:first sg:person.07776170271.83
101 rdf:rest Nd5fbafef39774a2686a492fdb4f70bf0
102 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
103 schema:name Mathematical Sciences
104 rdf:type schema:DefinedTerm
105 anzsrc-for:0104 schema:inDefinedTermSet anzsrc-for:
106 schema:name Statistics
107 rdf:type schema:DefinedTerm
108 sg:person.015120037757.44 schema:affiliation grid-institutes:grid.13992.30
109 schema:familyName Yogev
110 schema:givenName Eylon
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015120037757.44
112 rdf:type schema:Person
113 sg:person.07776170271.83 schema:affiliation grid-institutes:grid.13992.30
114 schema:familyName Naor
115 schema:givenName Moni
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83
117 rdf:type schema:Person
118 grid-institutes:grid.13992.30 schema:alternateName Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel
119 schema:name Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel
120 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...