A Detailed Investigation of Memory Requirements for Publish/Subscribe Filtering Algorithms View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2005

AUTHORS

Sven Bittner , Annika Hinze

ABSTRACT

Various filtering algorithms for publish/subscribe systems have been proposed. One distinguishing characteristic is their internal representation of Boolean subscriptions: They either require conversions into DNFs (canonical approaches) or are directly exploited in event filtering (non-canonical approaches). In this paper, we present a detailed analysis and comparison of the memory requirements of canonical and non-canonical filtering algorithms. This includes a theoretical analysis of space usages as well as a verification of our theoretical results by an evaluation of a practical implementation. This practical analysis also considers time (filter) efficiency, which is the other important quality measure of filtering algorithms. By correlating the results of space and time efficiency, we conclude when to use non-canonical and canonical approaches. More... »

PAGES

148-165

Book

TITLE

On the Move to Meaningful Internet Systems 2005: CoopIS, DOA, and ODBASE

ISBN

978-3-540-29736-9
978-3-540-32116-3

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11575771_12

DOI

http://dx.doi.org/10.1007/11575771_12

DIMENSIONS

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


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/0102", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Applied Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Waikato", 
          "id": "https://www.grid.ac/institutes/grid.49481.30", 
          "name": [
            "University of Waikato, New Zealand"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Bittner", 
        "givenName": "Sven", 
        "id": "sg:person.013421674565.86", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013421674565.86"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Waikato", 
          "id": "https://www.grid.ac/institutes/grid.49481.30", 
          "name": [
            "University of Waikato, New Zealand"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Hinze", 
        "givenName": "Annika", 
        "id": "sg:person.015257741031.53", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015257741031.53"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/176567.176573", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019927452"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/872757.872810", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1029558326"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/375663.375677", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045645738"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/863955.863975", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049749352"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/icdcsw.2002.1030823", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1094628548"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/icse.2001.919117", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1094831199"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/icdcsw.2005.104", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1095126776"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/93597.98736", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098976813"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2005", 
    "datePublishedReg": "2005-01-01", 
    "description": "Various filtering algorithms for publish/subscribe systems have been proposed. One distinguishing characteristic is their internal representation of Boolean subscriptions: They either require conversions into DNFs (canonical approaches) or are directly exploited in event filtering (non-canonical approaches). In this paper, we present a detailed analysis and comparison of the memory requirements of canonical and non-canonical filtering algorithms. This includes a theoretical analysis of space usages as well as a verification of our theoretical results by an evaluation of a practical implementation. This practical analysis also considers time (filter) efficiency, which is the other important quality measure of filtering algorithms. By correlating the results of space and time efficiency, we conclude when to use non-canonical and canonical approaches.", 
    "editor": [
      {
        "familyName": "Meersman", 
        "givenName": "Robert", 
        "type": "Person"
      }, 
      {
        "familyName": "Tari", 
        "givenName": "Zahir", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11575771_12", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-29736-9", 
        "978-3-540-32116-3"
      ], 
      "name": "On the Move to Meaningful Internet Systems 2005: CoopIS, DOA, and ODBASE", 
      "type": "Book"
    }, 
    "name": "A Detailed Investigation of Memory Requirements for Publish/Subscribe Filtering Algorithms", 
    "pagination": "148-165", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1010651767"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11575771_12"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "32bf43210e6bdb02ac7a2c7ac319527d0a742abf0d251155efcabd80501ae1f4"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11575771_12", 
      "https://app.dimensions.ai/details/publication/pub.1010651767"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T07:36", 
    "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/0000000357_0000000357/records_99308_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F11575771_12"
  }
]
 

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/11575771_12'

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/11575771_12'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11575771_12'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11575771_12'


 

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

101 TRIPLES      23 PREDICATES      35 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11575771_12 schema:about anzsrc-for:01
2 anzsrc-for:0102
3 schema:author N198d3266993244da8e0748cc0a91a198
4 schema:citation https://doi.org/10.1109/icdcsw.2002.1030823
5 https://doi.org/10.1109/icdcsw.2005.104
6 https://doi.org/10.1109/icse.2001.919117
7 https://doi.org/10.1145/176567.176573
8 https://doi.org/10.1145/375663.375677
9 https://doi.org/10.1145/863955.863975
10 https://doi.org/10.1145/872757.872810
11 https://doi.org/10.1145/93597.98736
12 schema:datePublished 2005
13 schema:datePublishedReg 2005-01-01
14 schema:description Various filtering algorithms for publish/subscribe systems have been proposed. One distinguishing characteristic is their internal representation of Boolean subscriptions: They either require conversions into DNFs (canonical approaches) or are directly exploited in event filtering (non-canonical approaches). In this paper, we present a detailed analysis and comparison of the memory requirements of canonical and non-canonical filtering algorithms. This includes a theoretical analysis of space usages as well as a verification of our theoretical results by an evaluation of a practical implementation. This practical analysis also considers time (filter) efficiency, which is the other important quality measure of filtering algorithms. By correlating the results of space and time efficiency, we conclude when to use non-canonical and canonical approaches.
15 schema:editor Nc94e97ee42054aae81ac65474eaa7a5f
16 schema:genre chapter
17 schema:inLanguage en
18 schema:isAccessibleForFree true
19 schema:isPartOf Ne6f311216c10402d9f256f1c9254771f
20 schema:name A Detailed Investigation of Memory Requirements for Publish/Subscribe Filtering Algorithms
21 schema:pagination 148-165
22 schema:productId N31b9d35f0cd64f0698e0de4e415f713f
23 Nad29a8ef331b4778b23480158f91479b
24 Nf87333e4c6ae42de86b25f1a70e75279
25 schema:publisher Nc1c49b5de3fc4998bac0d89e427ca180
26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010651767
27 https://doi.org/10.1007/11575771_12
28 schema:sdDatePublished 2019-04-16T07:36
29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
30 schema:sdPublisher Nb1a529f3b756484dafae3d1d1b4f1ab6
31 schema:url https://link.springer.com/10.1007%2F11575771_12
32 sgo:license sg:explorer/license/
33 sgo:sdDataset chapters
34 rdf:type schema:Chapter
35 N198d3266993244da8e0748cc0a91a198 rdf:first sg:person.013421674565.86
36 rdf:rest N45b5296f9f3345558cfbc40feabb4993
37 N2f283af613f14850bfb3330a294b85e9 rdf:first N631da0ddfe6f4ffb9a4d7b542b3dc9e2
38 rdf:rest rdf:nil
39 N31b9d35f0cd64f0698e0de4e415f713f schema:name readcube_id
40 schema:value 32bf43210e6bdb02ac7a2c7ac319527d0a742abf0d251155efcabd80501ae1f4
41 rdf:type schema:PropertyValue
42 N45b5296f9f3345558cfbc40feabb4993 rdf:first sg:person.015257741031.53
43 rdf:rest rdf:nil
44 N631da0ddfe6f4ffb9a4d7b542b3dc9e2 schema:familyName Tari
45 schema:givenName Zahir
46 rdf:type schema:Person
47 N8290cc72863147198bb49d5cb25b6da6 schema:familyName Meersman
48 schema:givenName Robert
49 rdf:type schema:Person
50 Nad29a8ef331b4778b23480158f91479b schema:name dimensions_id
51 schema:value pub.1010651767
52 rdf:type schema:PropertyValue
53 Nb1a529f3b756484dafae3d1d1b4f1ab6 schema:name Springer Nature - SN SciGraph project
54 rdf:type schema:Organization
55 Nc1c49b5de3fc4998bac0d89e427ca180 schema:location Berlin, Heidelberg
56 schema:name Springer Berlin Heidelberg
57 rdf:type schema:Organisation
58 Nc94e97ee42054aae81ac65474eaa7a5f rdf:first N8290cc72863147198bb49d5cb25b6da6
59 rdf:rest N2f283af613f14850bfb3330a294b85e9
60 Ne6f311216c10402d9f256f1c9254771f schema:isbn 978-3-540-29736-9
61 978-3-540-32116-3
62 schema:name On the Move to Meaningful Internet Systems 2005: CoopIS, DOA, and ODBASE
63 rdf:type schema:Book
64 Nf87333e4c6ae42de86b25f1a70e75279 schema:name doi
65 schema:value 10.1007/11575771_12
66 rdf:type schema:PropertyValue
67 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
68 schema:name Mathematical Sciences
69 rdf:type schema:DefinedTerm
70 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
71 schema:name Applied Mathematics
72 rdf:type schema:DefinedTerm
73 sg:person.013421674565.86 schema:affiliation https://www.grid.ac/institutes/grid.49481.30
74 schema:familyName Bittner
75 schema:givenName Sven
76 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013421674565.86
77 rdf:type schema:Person
78 sg:person.015257741031.53 schema:affiliation https://www.grid.ac/institutes/grid.49481.30
79 schema:familyName Hinze
80 schema:givenName Annika
81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015257741031.53
82 rdf:type schema:Person
83 https://doi.org/10.1109/icdcsw.2002.1030823 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094628548
84 rdf:type schema:CreativeWork
85 https://doi.org/10.1109/icdcsw.2005.104 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095126776
86 rdf:type schema:CreativeWork
87 https://doi.org/10.1109/icse.2001.919117 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094831199
88 rdf:type schema:CreativeWork
89 https://doi.org/10.1145/176567.176573 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019927452
90 rdf:type schema:CreativeWork
91 https://doi.org/10.1145/375663.375677 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045645738
92 rdf:type schema:CreativeWork
93 https://doi.org/10.1145/863955.863975 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049749352
94 rdf:type schema:CreativeWork
95 https://doi.org/10.1145/872757.872810 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029558326
96 rdf:type schema:CreativeWork
97 https://doi.org/10.1145/93597.98736 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098976813
98 rdf:type schema:CreativeWork
99 https://www.grid.ac/institutes/grid.49481.30 schema:alternateName University of Waikato
100 schema:name University of Waikato, New Zealand
101 rdf:type schema:Organization
 




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


...