Tight Bounds for Sliding Bloom Filters View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2015-05-13

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)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(1)$$\end{document} 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

652-672

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-015-0007-9

DOI

http://dx.doi.org/10.1007/s00453-015-0007-9

DIMENSIONS

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


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"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/978-3-540-70575-8_32", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047066435", 
          "https://doi.org/10.1007/978-3-540-70575-8_32"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2015-05-13", 
    "datePublishedReg": "2015-05-13", 
    "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)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$O(1)$$\\end{document} 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.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s00453-015-0007-9", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "73"
      }
    ], 
    "keywords": [
      "Bloom filter", 
      "data structure", 
      "small error probability", 
      "stream of elements", 
      "error probability", 
      "memory requirements", 
      "space consumption", 
      "membership queries", 
      "space construction", 
      "tight bounds", 
      "queries", 
      "filter", 
      "set", 
      "high probability", 
      "space", 
      "requirements", 
      "update", 
      "probability", 
      "streams", 
      "construction", 
      "bounds", 
      "relevant parameters", 
      "time", 
      "work", 
      "method", 
      "elements", 
      "consumption", 
      "parameters", 
      "terms", 
      "structure", 
      "community", 
      "lower order terms", 
      "literature", 
      "order terms", 
      "investigation", 
      "theoretical investigation", 
      "first theoretical investigation", 
      "problem", 
      "paper", 
      "Sliding Bloom Filter", 
      "slackness parameter", 
      "low space construction", 
      "best possible space consumption", 
      "possible space consumption", 
      "additive lower order term"
    ], 
    "name": "Tight Bounds for Sliding Bloom Filters", 
    "pagination": "652-672", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1005866119"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00453-015-0007-9"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00453-015-0007-9", 
      "https://app.dimensions.ai/details/publication/pub.1005866119"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-01-01T18:37", 
    "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/article/article_671.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s00453-015-0007-9"
  }
]
 

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/s00453-015-0007-9'

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/s00453-015-0007-9'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-015-0007-9'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-015-0007-9'


 

This table displays all metadata directly associated to this object as RDF triples.

114 TRIPLES      22 PREDICATES      71 URIs      62 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00453-015-0007-9 schema:about anzsrc-for:01
2 anzsrc-for:0104
3 schema:author N4ea30787c40b4bf0b82345137f4e243d
4 schema:citation sg:pub.10.1007/978-3-540-70575-8_32
5 schema:datePublished 2015-05-13
6 schema:datePublishedReg 2015-05-13
7 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)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(1)$$\end{document} 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.
8 schema:genre article
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N0dadf189ce994297845a835cc0a5ed62
12 N1143cd677f4145a1879ab72e11fb7acf
13 sg:journal.1047644
14 schema:keywords Bloom filter
15 Sliding Bloom Filter
16 additive lower order term
17 best possible space consumption
18 bounds
19 community
20 construction
21 consumption
22 data structure
23 elements
24 error probability
25 filter
26 first theoretical investigation
27 high probability
28 investigation
29 literature
30 low space construction
31 lower order terms
32 membership queries
33 memory requirements
34 method
35 order terms
36 paper
37 parameters
38 possible space consumption
39 probability
40 problem
41 queries
42 relevant parameters
43 requirements
44 set
45 slackness parameter
46 small error probability
47 space
48 space construction
49 space consumption
50 stream of elements
51 streams
52 structure
53 terms
54 theoretical investigation
55 tight bounds
56 time
57 update
58 work
59 schema:name Tight Bounds for Sliding Bloom Filters
60 schema:pagination 652-672
61 schema:productId N70295b9e904740f398cbb283a1cff459
62 Nf952e507547240c08ea00ea4c6efef92
63 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005866119
64 https://doi.org/10.1007/s00453-015-0007-9
65 schema:sdDatePublished 2022-01-01T18:37
66 schema:sdLicense https://scigraph.springernature.com/explorer/license/
67 schema:sdPublisher N0ec76b31cde04d40a547bdd40f74f332
68 schema:url https://doi.org/10.1007/s00453-015-0007-9
69 sgo:license sg:explorer/license/
70 sgo:sdDataset articles
71 rdf:type schema:ScholarlyArticle
72 N0dadf189ce994297845a835cc0a5ed62 schema:issueNumber 4
73 rdf:type schema:PublicationIssue
74 N0ec76b31cde04d40a547bdd40f74f332 schema:name Springer Nature - SN SciGraph project
75 rdf:type schema:Organization
76 N1143cd677f4145a1879ab72e11fb7acf schema:volumeNumber 73
77 rdf:type schema:PublicationVolume
78 N4ea30787c40b4bf0b82345137f4e243d rdf:first sg:person.07776170271.83
79 rdf:rest Nf70dc64d8ee14641a817c5d52a81c7c0
80 N70295b9e904740f398cbb283a1cff459 schema:name dimensions_id
81 schema:value pub.1005866119
82 rdf:type schema:PropertyValue
83 Nf70dc64d8ee14641a817c5d52a81c7c0 rdf:first sg:person.015120037757.44
84 rdf:rest rdf:nil
85 Nf952e507547240c08ea00ea4c6efef92 schema:name doi
86 schema:value 10.1007/s00453-015-0007-9
87 rdf:type schema:PropertyValue
88 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
89 schema:name Mathematical Sciences
90 rdf:type schema:DefinedTerm
91 anzsrc-for:0104 schema:inDefinedTermSet anzsrc-for:
92 schema:name Statistics
93 rdf:type schema:DefinedTerm
94 sg:journal.1047644 schema:issn 0178-4617
95 1432-0541
96 schema:name Algorithmica
97 schema:publisher Springer Nature
98 rdf:type schema:Periodical
99 sg:person.015120037757.44 schema:affiliation grid-institutes:grid.13992.30
100 schema:familyName Yogev
101 schema:givenName Eylon
102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015120037757.44
103 rdf:type schema:Person
104 sg:person.07776170271.83 schema:affiliation grid-institutes:grid.13992.30
105 schema:familyName Naor
106 schema:givenName Moni
107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83
108 rdf:type schema:Person
109 sg:pub.10.1007/978-3-540-70575-8_32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047066435
110 https://doi.org/10.1007/978-3-540-70575-8_32
111 rdf:type schema:CreativeWork
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)


...