Streaming Partitioning of RDF Graphs for Datalog Reasoning View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2021-05-31

AUTHORS

Temitope Ajileye , Boris Motik , Ian Horrocks

ABSTRACT

A cluster of servers is often used to reason over RDF graphs whose size exceeds the capacity of a single server. While many distributed approaches to reasoning have been proposed, the problem of data partitioning has received little attention thus far. In practice, data is usually partitioned by a variant of hashing, which is very simple, but it does not pay attention to data locality. Locality-aware partitioning approaches have been considered, but they usually process the entire dataset on a single server. In this paper, we present two new RDF partitioning strategies. Both are inspired by recent streaming graph partitioning algorithms, which partition a graph while keeping only a small subset of the graph in memory. We have evaluated our approaches empirically against hash and min-cut partitioning. Our results suggest that our approaches can significantly improve reasoning performance, but without unrealistic demands on the memory of the servers used for partitioning. More... »

PAGES

3-22

Book

TITLE

The Semantic Web

ISBN

978-3-030-77384-7
978-3-030-77385-4

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-030-77385-4_1

DOI

http://dx.doi.org/10.1007/978-3-030-77385-4_1

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0803", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computer Software", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Oxford, Oxford, UK", 
          "id": "http://www.grid.ac/institutes/grid.4991.5", 
          "name": [
            "Department of Computer Science, University of Oxford, Oxford, UK"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ajileye", 
        "givenName": "Temitope", 
        "id": "sg:person.010564701705.97", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010564701705.97"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Oxford, Oxford, UK", 
          "id": "http://www.grid.ac/institutes/grid.4991.5", 
          "name": [
            "Department of Computer Science, University of Oxford, Oxford, UK"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Motik", 
        "givenName": "Boris", 
        "id": "sg:person.07401076267.36", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07401076267.36"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Oxford, Oxford, UK", 
          "id": "http://www.grid.ac/institutes/grid.4991.5", 
          "name": [
            "Department of Computer Science, University of Oxford, Oxford, UK"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Horrocks", 
        "givenName": "Ian", 
        "id": "sg:person.013100561643.19", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013100561643.19"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2021-05-31", 
    "datePublishedReg": "2021-05-31", 
    "description": "A cluster of servers is often used to reason over RDF graphs whose size exceeds the capacity of a single server. While many distributed approaches to reasoning have been proposed, the problem of data partitioning has received little attention thus far. In practice, data is usually partitioned by a variant of hashing, which is very simple, but it does not pay attention to data locality. Locality-aware partitioning approaches have been considered, but they usually process the entire dataset on a single server. In this paper, we present two new RDF partitioning strategies. Both are inspired by recent streaming graph partitioning algorithms, which partition a graph while keeping only a small subset of the graph in memory. We have evaluated our approaches empirically against hash and min-cut partitioning. Our results suggest that our approaches can significantly improve reasoning performance, but without unrealistic demands on the memory of the servers used for partitioning.", 
    "editor": [
      {
        "familyName": "Verborgh", 
        "givenName": "Ruben", 
        "type": "Person"
      }, 
      {
        "familyName": "Hose", 
        "givenName": "Katja", 
        "type": "Person"
      }, 
      {
        "familyName": "Paulheim", 
        "givenName": "Heiko", 
        "type": "Person"
      }, 
      {
        "familyName": "Champin", 
        "givenName": "Pierre-Antoine", 
        "type": "Person"
      }, 
      {
        "familyName": "Maleshkova", 
        "givenName": "Maria", 
        "type": "Person"
      }, 
      {
        "familyName": "Corcho", 
        "givenName": "Oscar", 
        "type": "Person"
      }, 
      {
        "familyName": "Ristoski", 
        "givenName": "Petar", 
        "type": "Person"
      }, 
      {
        "familyName": "Alam", 
        "givenName": "Mehwish", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-030-77385-4_1", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-030-77384-7", 
        "978-3-030-77385-4"
      ], 
      "name": "The Semantic Web", 
      "type": "Book"
    }, 
    "keywords": [
      "RDF graphs", 
      "single server", 
      "cluster of servers", 
      "Datalog reasoning", 
      "data partitioning", 
      "data locality", 
      "server", 
      "partitioning strategies", 
      "partitioning approach", 
      "entire dataset", 
      "graph", 
      "reasoning", 
      "hashing", 
      "hash", 
      "small subset", 
      "partitioning", 
      "dataset", 
      "algorithm", 
      "memory", 
      "unrealistic demands", 
      "performance", 
      "demand", 
      "attention", 
      "little attention", 
      "clusters", 
      "data", 
      "subset", 
      "localities", 
      "strategies", 
      "results", 
      "variants", 
      "practice", 
      "size", 
      "capacity", 
      "approach", 
      "min", 
      "paper", 
      "problem"
    ], 
    "name": "Streaming Partitioning of RDF Graphs for Datalog Reasoning", 
    "pagination": "3-22", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1138468547"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-030-77385-4_1"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-030-77385-4_1", 
      "https://app.dimensions.ai/details/publication/pub.1138468547"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:47", 
    "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_366.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-030-77385-4_1"
  }
]
 

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-030-77385-4_1'

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-030-77385-4_1'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-77385-4_1'

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-030-77385-4_1'


 

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

147 TRIPLES      23 PREDICATES      63 URIs      56 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-030-77385-4_1 schema:about anzsrc-for:08
2 anzsrc-for:0803
3 schema:author N55ebc68958b64009b7430933bfa6b830
4 schema:datePublished 2021-05-31
5 schema:datePublishedReg 2021-05-31
6 schema:description A cluster of servers is often used to reason over RDF graphs whose size exceeds the capacity of a single server. While many distributed approaches to reasoning have been proposed, the problem of data partitioning has received little attention thus far. In practice, data is usually partitioned by a variant of hashing, which is very simple, but it does not pay attention to data locality. Locality-aware partitioning approaches have been considered, but they usually process the entire dataset on a single server. In this paper, we present two new RDF partitioning strategies. Both are inspired by recent streaming graph partitioning algorithms, which partition a graph while keeping only a small subset of the graph in memory. We have evaluated our approaches empirically against hash and min-cut partitioning. Our results suggest that our approaches can significantly improve reasoning performance, but without unrealistic demands on the memory of the servers used for partitioning.
7 schema:editor N25a218cbb8d6450baff897ba6eaa7c0f
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nbe05450414a6479c856a5cebeba90fbc
12 schema:keywords Datalog reasoning
13 RDF graphs
14 algorithm
15 approach
16 attention
17 capacity
18 cluster of servers
19 clusters
20 data
21 data locality
22 data partitioning
23 dataset
24 demand
25 entire dataset
26 graph
27 hash
28 hashing
29 little attention
30 localities
31 memory
32 min
33 paper
34 partitioning
35 partitioning approach
36 partitioning strategies
37 performance
38 practice
39 problem
40 reasoning
41 results
42 server
43 single server
44 size
45 small subset
46 strategies
47 subset
48 unrealistic demands
49 variants
50 schema:name Streaming Partitioning of RDF Graphs for Datalog Reasoning
51 schema:pagination 3-22
52 schema:productId N66c78967f2c84912a473b842b1b1a0c2
53 Nf4be0be6408b40879629d45f8685aa42
54 schema:publisher Naca02e2824a148e497655219bfe7d45d
55 schema:sameAs https://app.dimensions.ai/details/publication/pub.1138468547
56 https://doi.org/10.1007/978-3-030-77385-4_1
57 schema:sdDatePublished 2022-05-20T07:47
58 schema:sdLicense https://scigraph.springernature.com/explorer/license/
59 schema:sdPublisher Nc49514d8827c490ebf7a6cac54116e0d
60 schema:url https://doi.org/10.1007/978-3-030-77385-4_1
61 sgo:license sg:explorer/license/
62 sgo:sdDataset chapters
63 rdf:type schema:Chapter
64 N06fba2e7efd7416b8584dcfafb3bd8a1 rdf:first Nc505ec7f1bb7498792ea27b91c1670b8
65 rdf:rest N39d0bb5271be40a8ab4083e66f0cbc77
66 N0954eac38f8743bfba8a06e2b06bde06 schema:familyName Verborgh
67 schema:givenName Ruben
68 rdf:type schema:Person
69 N1f83d15fa4024dd585d574e0019cb930 schema:familyName Ristoski
70 schema:givenName Petar
71 rdf:type schema:Person
72 N251ca980224449d6800c4ff19d4eb955 schema:familyName Corcho
73 schema:givenName Oscar
74 rdf:type schema:Person
75 N25a218cbb8d6450baff897ba6eaa7c0f rdf:first N0954eac38f8743bfba8a06e2b06bde06
76 rdf:rest N06fba2e7efd7416b8584dcfafb3bd8a1
77 N31be7415cd80462ca49c4c3571b7b298 rdf:first Nb22a61befdd74f50920b9d9fd2b4cbe3
78 rdf:rest rdf:nil
79 N39d0bb5271be40a8ab4083e66f0cbc77 rdf:first Ndd39394a73c54659b4e3c83eaf00a138
80 rdf:rest Na1f53c6d480e41ec9ab816954953903f
81 N501ef7b71c964e1e8aa34092c7c21a8a schema:familyName Maleshkova
82 schema:givenName Maria
83 rdf:type schema:Person
84 N52551bfee97f40129c79b7cf50444449 rdf:first sg:person.013100561643.19
85 rdf:rest rdf:nil
86 N55ebc68958b64009b7430933bfa6b830 rdf:first sg:person.010564701705.97
87 rdf:rest Nb435779f790349f1985cb2a5052b6373
88 N66c78967f2c84912a473b842b1b1a0c2 schema:name doi
89 schema:value 10.1007/978-3-030-77385-4_1
90 rdf:type schema:PropertyValue
91 Na1f53c6d480e41ec9ab816954953903f rdf:first Nc1dbc3f9d25244dcacaf8847324b6f30
92 rdf:rest Nb163f749b6954c049d3c38f8aed7f1bd
93 Naca02e2824a148e497655219bfe7d45d schema:name Springer Nature
94 rdf:type schema:Organisation
95 Nafb1acc626044079988a858f7d21fd5f rdf:first N251ca980224449d6800c4ff19d4eb955
96 rdf:rest Nb4c39a5583ae4f0e96c3ad7cd90a8ae7
97 Nb163f749b6954c049d3c38f8aed7f1bd rdf:first N501ef7b71c964e1e8aa34092c7c21a8a
98 rdf:rest Nafb1acc626044079988a858f7d21fd5f
99 Nb22a61befdd74f50920b9d9fd2b4cbe3 schema:familyName Alam
100 schema:givenName Mehwish
101 rdf:type schema:Person
102 Nb435779f790349f1985cb2a5052b6373 rdf:first sg:person.07401076267.36
103 rdf:rest N52551bfee97f40129c79b7cf50444449
104 Nb4c39a5583ae4f0e96c3ad7cd90a8ae7 rdf:first N1f83d15fa4024dd585d574e0019cb930
105 rdf:rest N31be7415cd80462ca49c4c3571b7b298
106 Nbe05450414a6479c856a5cebeba90fbc schema:isbn 978-3-030-77384-7
107 978-3-030-77385-4
108 schema:name The Semantic Web
109 rdf:type schema:Book
110 Nc1dbc3f9d25244dcacaf8847324b6f30 schema:familyName Champin
111 schema:givenName Pierre-Antoine
112 rdf:type schema:Person
113 Nc49514d8827c490ebf7a6cac54116e0d schema:name Springer Nature - SN SciGraph project
114 rdf:type schema:Organization
115 Nc505ec7f1bb7498792ea27b91c1670b8 schema:familyName Hose
116 schema:givenName Katja
117 rdf:type schema:Person
118 Ndd39394a73c54659b4e3c83eaf00a138 schema:familyName Paulheim
119 schema:givenName Heiko
120 rdf:type schema:Person
121 Nf4be0be6408b40879629d45f8685aa42 schema:name dimensions_id
122 schema:value pub.1138468547
123 rdf:type schema:PropertyValue
124 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
125 schema:name Information and Computing Sciences
126 rdf:type schema:DefinedTerm
127 anzsrc-for:0803 schema:inDefinedTermSet anzsrc-for:
128 schema:name Computer Software
129 rdf:type schema:DefinedTerm
130 sg:person.010564701705.97 schema:affiliation grid-institutes:grid.4991.5
131 schema:familyName Ajileye
132 schema:givenName Temitope
133 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010564701705.97
134 rdf:type schema:Person
135 sg:person.013100561643.19 schema:affiliation grid-institutes:grid.4991.5
136 schema:familyName Horrocks
137 schema:givenName Ian
138 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013100561643.19
139 rdf:type schema:Person
140 sg:person.07401076267.36 schema:affiliation grid-institutes:grid.4991.5
141 schema:familyName Motik
142 schema:givenName Boris
143 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07401076267.36
144 rdf:type schema:Person
145 grid-institutes:grid.4991.5 schema:alternateName Department of Computer Science, University of Oxford, Oxford, UK
146 schema:name Department of Computer Science, University of Oxford, Oxford, UK
147 rdf:type schema:Organization
 




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


...