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": [
      "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

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.

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
 




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


...