XOR-Satisfiability Set Membership Filters View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2018-06-26

AUTHORS

Sean A. Weaver , Hannah J. Roberts , Michael J. Smith

ABSTRACT

Set membership filters are used as a primary test for whether large sets contain given elements. The most common such filter is the Bloom filter [6]. Most pertinent to this article is the recently introduced Satisfiability (SAT) filter [31]. This article proposes the XOR-Satisfiability filter, a variant of the SAT filter based on random k-XORSAT. Experimental results show that this new filter can be more than 99% efficient (i.e., achieve the information-theoretic limit) while also having a query speed comparable to the standard Bloom filter, making it practical for use with very large data sets. More... »

PAGES

401-418

References to SciGraph publications

  • 2008. Succinct Data Structures for Retrieval and Approximate Membership (Extended Abstract) in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 2010. Tight Thresholds for Cuckoo Hashing via XORSAT in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 2015. Constructing SAT Filters with a Quantum Annealer in THEORY AND APPLICATIONS OF SATISFIABILITY TESTING -- SAT 2015
  • 2008. Random 2-XORSAT at the Satisfiability Threshold in LATIN 2008: THEORETICAL INFORMATICS
  • 2009. Algebraic Cryptanalysis in NONE
  • 2009. An Optimal Bloom Filter Replacement Based on Matrix Solving in COMPUTER SCIENCE - THEORY AND APPLICATIONS
  • Book

    TITLE

    Theory and Applications of Satisfiability Testing – SAT 2018

    ISBN

    978-3-319-94143-1
    978-3-319-94144-8

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-319-94144-8_24

    DOI

    http://dx.doi.org/10.1007/978-3-319-94144-8_24

    DIMENSIONS

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


    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/0806", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information Systems", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "National Security Agency", 
              "id": "https://www.grid.ac/institutes/grid.482831.4", 
              "name": [
                "Information Assurance Research Group, U.S. National Security Agency, 9800 Savage Rd., Suite 6845, 20755, Ft. George G. Meade, MD, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Weaver", 
            "givenName": "Sean A.", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "National Security Agency", 
              "id": "https://www.grid.ac/institutes/grid.482831.4", 
              "name": [
                "Information Assurance Research Group, U.S. National Security Agency, 9800 Savage Rd., Suite 6845, 20755, Ft. George G. Meade, MD, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Roberts", 
            "givenName": "Hannah J.", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "National Security Agency", 
              "id": "https://www.grid.ac/institutes/grid.482831.4", 
              "name": [
                "Information Assurance Research Group, U.S. National Security Agency, 9800 Savage Rd., Suite 6845, 20755, Ft. George G. Meade, MD, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Smith", 
            "givenName": "Michael J.", 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1080/15427951.2011.560785", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004186227"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/362686.362692", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007357969"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/2976749.2978401", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007495381"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-0-387-88757-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008607024", 
              "https://doi.org/10.1007/978-0-387-88757-9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-0-387-88757-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008607024", 
              "https://doi.org/10.1007/978-0-387-88757-9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-14165-2_19", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014868009", 
              "https://doi.org/10.1007/978-3-642-14165-2_19"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-14165-2_19", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014868009", 
              "https://doi.org/10.1007/978-3-642-14165-2_19"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/2674005.2674994", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015728984"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/872757.872787", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016177921"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-03351-3_25", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017860647", 
              "https://doi.org/10.1007/978-3-642-03351-3_25"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-78773-0_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017939521", 
              "https://doi.org/10.1007/978-3-540-78773-0_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-78773-0_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017939521", 
              "https://doi.org/10.1007/978-3-540-78773-0_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/s0963548315000097", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027976804"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1498698.1594230", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037352743"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "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"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-24318-4_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047891165", 
              "https://doi.org/10.1007/978-3-319-24318-4_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tnet.2002.803864", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061714317"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s0097539795294165", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062880068"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.21468/scipostphys.2.2.013", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1084640529"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/1.9781611973099.62", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1088801527"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/lisat.2017.8001989", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095711734"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2018-06-26", 
        "datePublishedReg": "2018-06-26", 
        "description": "Set membership filters are used as a primary test for whether large sets contain given elements. The most common such filter is the Bloom filter [6]. Most pertinent to this article is the recently introduced Satisfiability (SAT) filter [31]. This article proposes the XOR-Satisfiability filter, a variant of the SAT filter based on random k-XORSAT. Experimental results show that this new filter can be more than 99% efficient (i.e., achieve the information-theoretic limit) while also having a query speed comparable to the standard Bloom filter, making it practical for use with very large data sets.", 
        "editor": [
          {
            "familyName": "Beyersdorff", 
            "givenName": "Olaf", 
            "type": "Person"
          }, 
          {
            "familyName": "Wintersteiger", 
            "givenName": "Christoph M.", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-319-94144-8_24", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-319-94143-1", 
            "978-3-319-94144-8"
          ], 
          "name": "Theory and Applications of Satisfiability Testing \u2013 SAT 2018", 
          "type": "Book"
        }, 
        "name": "XOR-Satisfiability Set Membership Filters", 
        "pagination": "401-418", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-319-94144-8_24"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "38162a5d3dc4da0fe41575d945d6c2d2151f9bc8e000c98c840d2421e6df4622"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1105105441"
            ]
          }
        ], 
        "publisher": {
          "location": "Cham", 
          "name": "Springer International Publishing", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-319-94144-8_24", 
          "https://app.dimensions.ai/details/publication/pub.1105105441"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T05:00", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000325_0000000325/records_100794_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-319-94144-8_24"
      }
    ]
     

    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-319-94144-8_24'

    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-319-94144-8_24'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-94144-8_24'

    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-319-94144-8_24'


     

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

    141 TRIPLES      23 PREDICATES      44 URIs      19 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-319-94144-8_24 schema:about anzsrc-for:08
    2 anzsrc-for:0806
    3 schema:author Ndc63644163f54f6995f3bcfb4ca9f9d9
    4 schema:citation sg:pub.10.1007/978-0-387-88757-9
    5 sg:pub.10.1007/978-3-319-24318-4_9
    6 sg:pub.10.1007/978-3-540-70575-8_32
    7 sg:pub.10.1007/978-3-540-78773-0_2
    8 sg:pub.10.1007/978-3-642-03351-3_25
    9 sg:pub.10.1007/978-3-642-14165-2_19
    10 https://doi.org/10.1017/s0963548315000097
    11 https://doi.org/10.1080/15427951.2011.560785
    12 https://doi.org/10.1109/lisat.2017.8001989
    13 https://doi.org/10.1109/tnet.2002.803864
    14 https://doi.org/10.1137/1.9781611973099.62
    15 https://doi.org/10.1137/s0097539795294165
    16 https://doi.org/10.1145/1498698.1594230
    17 https://doi.org/10.1145/2674005.2674994
    18 https://doi.org/10.1145/2976749.2978401
    19 https://doi.org/10.1145/362686.362692
    20 https://doi.org/10.1145/872757.872787
    21 https://doi.org/10.21468/scipostphys.2.2.013
    22 schema:datePublished 2018-06-26
    23 schema:datePublishedReg 2018-06-26
    24 schema:description Set membership filters are used as a primary test for whether large sets contain given elements. The most common such filter is the Bloom filter [6]. Most pertinent to this article is the recently introduced Satisfiability (SAT) filter [31]. This article proposes the XOR-Satisfiability filter, a variant of the SAT filter based on random k-XORSAT. Experimental results show that this new filter can be more than 99% efficient (i.e., achieve the information-theoretic limit) while also having a query speed comparable to the standard Bloom filter, making it practical for use with very large data sets.
    25 schema:editor Nefa04b2b40854a8cb2c43d72f1759c3d
    26 schema:genre chapter
    27 schema:inLanguage en
    28 schema:isAccessibleForFree false
    29 schema:isPartOf N6b5ffdc1c32b4114a8d95ebd59e78896
    30 schema:name XOR-Satisfiability Set Membership Filters
    31 schema:pagination 401-418
    32 schema:productId N1e676439c2054ee586d94a648b3bb34a
    33 N4a485def8ff54269924c5e2ef751c90d
    34 Neef299855f81428fa5884af73338380e
    35 schema:publisher N6aeb13d75c1d42ceb02e5089f765df74
    36 schema:sameAs https://app.dimensions.ai/details/publication/pub.1105105441
    37 https://doi.org/10.1007/978-3-319-94144-8_24
    38 schema:sdDatePublished 2019-04-16T05:00
    39 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    40 schema:sdPublisher N13901edb5f3942c9b71d5a907794c5d8
    41 schema:url https://link.springer.com/10.1007%2F978-3-319-94144-8_24
    42 sgo:license sg:explorer/license/
    43 sgo:sdDataset chapters
    44 rdf:type schema:Chapter
    45 N0cdbd44b2db84c2bbd59adb13964dbe1 rdf:first N4a6e52115b5e4ab8a76f148791f205e2
    46 rdf:rest rdf:nil
    47 N13901edb5f3942c9b71d5a907794c5d8 schema:name Springer Nature - SN SciGraph project
    48 rdf:type schema:Organization
    49 N1e676439c2054ee586d94a648b3bb34a schema:name readcube_id
    50 schema:value 38162a5d3dc4da0fe41575d945d6c2d2151f9bc8e000c98c840d2421e6df4622
    51 rdf:type schema:PropertyValue
    52 N48aab232c4874216b4f8057e99d04caf schema:familyName Wintersteiger
    53 schema:givenName Christoph M.
    54 rdf:type schema:Person
    55 N4a485def8ff54269924c5e2ef751c90d schema:name dimensions_id
    56 schema:value pub.1105105441
    57 rdf:type schema:PropertyValue
    58 N4a6e52115b5e4ab8a76f148791f205e2 schema:affiliation https://www.grid.ac/institutes/grid.482831.4
    59 schema:familyName Smith
    60 schema:givenName Michael J.
    61 rdf:type schema:Person
    62 N6aeb13d75c1d42ceb02e5089f765df74 schema:location Cham
    63 schema:name Springer International Publishing
    64 rdf:type schema:Organisation
    65 N6b5ffdc1c32b4114a8d95ebd59e78896 schema:isbn 978-3-319-94143-1
    66 978-3-319-94144-8
    67 schema:name Theory and Applications of Satisfiability Testing – SAT 2018
    68 rdf:type schema:Book
    69 N737e1a6a6d434547a8243997ac67ca3d rdf:first N878659a3100e473c8d28e1830df8de00
    70 rdf:rest N0cdbd44b2db84c2bbd59adb13964dbe1
    71 N7852033391c94338ad3e905a751038db schema:affiliation https://www.grid.ac/institutes/grid.482831.4
    72 schema:familyName Weaver
    73 schema:givenName Sean A.
    74 rdf:type schema:Person
    75 N878659a3100e473c8d28e1830df8de00 schema:affiliation https://www.grid.ac/institutes/grid.482831.4
    76 schema:familyName Roberts
    77 schema:givenName Hannah J.
    78 rdf:type schema:Person
    79 Na2a6493893784b33a694fcf43599e76d schema:familyName Beyersdorff
    80 schema:givenName Olaf
    81 rdf:type schema:Person
    82 Nb2e49345bf054cf0b5f9a41736e5e64d rdf:first N48aab232c4874216b4f8057e99d04caf
    83 rdf:rest rdf:nil
    84 Ndc63644163f54f6995f3bcfb4ca9f9d9 rdf:first N7852033391c94338ad3e905a751038db
    85 rdf:rest N737e1a6a6d434547a8243997ac67ca3d
    86 Neef299855f81428fa5884af73338380e schema:name doi
    87 schema:value 10.1007/978-3-319-94144-8_24
    88 rdf:type schema:PropertyValue
    89 Nefa04b2b40854a8cb2c43d72f1759c3d rdf:first Na2a6493893784b33a694fcf43599e76d
    90 rdf:rest Nb2e49345bf054cf0b5f9a41736e5e64d
    91 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    92 schema:name Information and Computing Sciences
    93 rdf:type schema:DefinedTerm
    94 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
    95 schema:name Information Systems
    96 rdf:type schema:DefinedTerm
    97 sg:pub.10.1007/978-0-387-88757-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008607024
    98 https://doi.org/10.1007/978-0-387-88757-9
    99 rdf:type schema:CreativeWork
    100 sg:pub.10.1007/978-3-319-24318-4_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047891165
    101 https://doi.org/10.1007/978-3-319-24318-4_9
    102 rdf:type schema:CreativeWork
    103 sg:pub.10.1007/978-3-540-70575-8_32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047066435
    104 https://doi.org/10.1007/978-3-540-70575-8_32
    105 rdf:type schema:CreativeWork
    106 sg:pub.10.1007/978-3-540-78773-0_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017939521
    107 https://doi.org/10.1007/978-3-540-78773-0_2
    108 rdf:type schema:CreativeWork
    109 sg:pub.10.1007/978-3-642-03351-3_25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017860647
    110 https://doi.org/10.1007/978-3-642-03351-3_25
    111 rdf:type schema:CreativeWork
    112 sg:pub.10.1007/978-3-642-14165-2_19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014868009
    113 https://doi.org/10.1007/978-3-642-14165-2_19
    114 rdf:type schema:CreativeWork
    115 https://doi.org/10.1017/s0963548315000097 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027976804
    116 rdf:type schema:CreativeWork
    117 https://doi.org/10.1080/15427951.2011.560785 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004186227
    118 rdf:type schema:CreativeWork
    119 https://doi.org/10.1109/lisat.2017.8001989 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095711734
    120 rdf:type schema:CreativeWork
    121 https://doi.org/10.1109/tnet.2002.803864 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061714317
    122 rdf:type schema:CreativeWork
    123 https://doi.org/10.1137/1.9781611973099.62 schema:sameAs https://app.dimensions.ai/details/publication/pub.1088801527
    124 rdf:type schema:CreativeWork
    125 https://doi.org/10.1137/s0097539795294165 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062880068
    126 rdf:type schema:CreativeWork
    127 https://doi.org/10.1145/1498698.1594230 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037352743
    128 rdf:type schema:CreativeWork
    129 https://doi.org/10.1145/2674005.2674994 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015728984
    130 rdf:type schema:CreativeWork
    131 https://doi.org/10.1145/2976749.2978401 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007495381
    132 rdf:type schema:CreativeWork
    133 https://doi.org/10.1145/362686.362692 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007357969
    134 rdf:type schema:CreativeWork
    135 https://doi.org/10.1145/872757.872787 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016177921
    136 rdf:type schema:CreativeWork
    137 https://doi.org/10.21468/scipostphys.2.2.013 schema:sameAs https://app.dimensions.ai/details/publication/pub.1084640529
    138 rdf:type schema:CreativeWork
    139 https://www.grid.ac/institutes/grid.482831.4 schema:alternateName National Security Agency
    140 schema:name Information Assurance Research Group, U.S. National Security Agency, 9800 Savage Rd., Suite 6845, 20755, Ft. George G. Meade, MD, USA
    141 rdf:type schema:Organization
     




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


    ...