Dynamic Data Exchange in Distributed RDF Stores.
Saved in:
| Title: | Dynamic Data Exchange in Distributed RDF Stores. |
|---|---|
| Authors: | Potter, Anthony, Motik, Boris, Nenov, Yavor, Horrocks, Ian |
| Source: | IEEE Transactions on Knowledge & Data Engineering. Dec2018, Vol. 30 Issue 12, p2312-2325. 14p. |
| Subjects: | RDF (Document markup language), Dynamic data exchange, Querying (Computer science), Search algorithms, Distributed databases, Relational databases |
| Abstract: | When RDF datasets become too large to be managed by centralised systems, they are often distributed in a cluster of shared-nothing servers, and queries are answered using a distributed join algorithm. Although such solutions have been extensively studied in relational and RDF databases, we argue that existing approaches exhibit two drawbacks. First, they usually decidestatically(i.e., at query compile time) how to shuffle the data, which can lead to missed opportunities for local computation. Second, they often materialise large intermediate relations whose size is determined by the entire dataset (and not the data stored in each server), so these relations can easily exceed the memory of individual servers. As a possible remedy, we present a novel distributed join algorithm for RDF. Our approach decides when to shuffle datadynamically, which ensures that query answers that can be wholly produced within a server involve only local computation. It also uses a novel flow control mechanism to ensure that every query can be answered even if each server has a bounded amount of memory that is much smaller than the intermediate relations. We complement our algorithm with a new query planning approach that balances the cost of communication against the cost of local processing at each server. Moreover, as in several existing approaches, we distribute RDF data using graph partitioning so as to maximise local computation, but we refine the partitioning algorithm to produce more balanced partitions. We show empirically that our techniques can outperform the state of the art by orders of magnitude in terms of query evaluation times, network communication, and memory use. In particular, bounding the memory use in individual servers can mean the difference between success and failure for answering queries with large answer sets. [ABSTRACT FROM AUTHOR] |
| Copyright of IEEE Transactions on Knowledge & Data Engineering is the property of IEEE and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 132967344 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Dynamic Data Exchange in Distributed RDF Stores. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Potter%2C+Anthony%22">Potter, Anthony</searchLink><br /><searchLink fieldCode="AR" term="%22Motik%2C+Boris%22">Motik, Boris</searchLink><br /><searchLink fieldCode="AR" term="%22Nenov%2C+Yavor%22">Nenov, Yavor</searchLink><br /><searchLink fieldCode="AR" term="%22Horrocks%2C+Ian%22">Horrocks, Ian</searchLink> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22IEEE+Transactions+on+Knowledge+%26+Data+Engineering%22">IEEE Transactions on Knowledge & Data Engineering</searchLink>. Dec2018, Vol. 30 Issue 12, p2312-2325. 14p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22RDF+%28Document+markup+language%29%22">RDF (Document markup language)</searchLink><br /><searchLink fieldCode="DE" term="%22Dynamic+data+exchange%22">Dynamic data exchange</searchLink><br /><searchLink fieldCode="DE" term="%22Querying+%28Computer+science%29%22">Querying (Computer science)</searchLink><br /><searchLink fieldCode="DE" term="%22Search+algorithms%22">Search algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Distributed+databases%22">Distributed databases</searchLink><br /><searchLink fieldCode="DE" term="%22Relational+databases%22">Relational databases</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: When RDF datasets become too large to be managed by centralised systems, they are often distributed in a cluster of shared-nothing servers, and queries are answered using a distributed join algorithm. Although such solutions have been extensively studied in relational and RDF databases, we argue that existing approaches exhibit two drawbacks. First, they usually decidestatically(i.e., at query compile time) how to shuffle the data, which can lead to missed opportunities for local computation. Second, they often materialise large intermediate relations whose size is determined by the entire dataset (and not the data stored in each server), so these relations can easily exceed the memory of individual servers. As a possible remedy, we present a novel distributed join algorithm for RDF. Our approach decides when to shuffle datadynamically, which ensures that query answers that can be wholly produced within a server involve only local computation. It also uses a novel flow control mechanism to ensure that every query can be answered even if each server has a bounded amount of memory that is much smaller than the intermediate relations. We complement our algorithm with a new query planning approach that balances the cost of communication against the cost of local processing at each server. Moreover, as in several existing approaches, we distribute RDF data using graph partitioning so as to maximise local computation, but we refine the partitioning algorithm to produce more balanced partitions. We show empirically that our techniques can outperform the state of the art by orders of magnitude in terms of query evaluation times, network communication, and memory use. In particular, bounding the memory use in individual servers can mean the difference between success and failure for answering queries with large answer sets. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of IEEE Transactions on Knowledge & Data Engineering is the property of IEEE and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=132967344 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1109/TKDE.2018.2818696 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 14 StartPage: 2312 Subjects: – SubjectFull: RDF (Document markup language) Type: general – SubjectFull: Dynamic data exchange Type: general – SubjectFull: Querying (Computer science) Type: general – SubjectFull: Search algorithms Type: general – SubjectFull: Distributed databases Type: general – SubjectFull: Relational databases Type: general Titles: – TitleFull: Dynamic Data Exchange in Distributed RDF Stores. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Potter, Anthony – PersonEntity: Name: NameFull: Motik, Boris – PersonEntity: Name: NameFull: Nenov, Yavor – PersonEntity: Name: NameFull: Horrocks, Ian IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 12 Text: Dec2018 Type: published Y: 2018 Identifiers: – Type: issn-print Value: 10414347 Numbering: – Type: volume Value: 30 – Type: issue Value: 12 Titles: – TitleFull: IEEE Transactions on Knowledge & Data Engineering Type: main |
| ResultId | 1 |
