Optimization of distributed SPARQL queries using edmonds' algorithm and prim's algorithm. Vandervalk, B., McCarthy, E., & Wilkinson, M. In Proceedings - 12th IEEE International Conference on Computational Science and Engineering, CSE 2009, volume 1, 2009. doi abstract bibtex Here we describe the application of two well known graph algorithms, Edmonds' algorithm and Prim's algorithm, to the problem of optimizing distributed SPARQL queries. In the context of this paper, a "distributed SPARQL query" is a SPARQL query which is resolved by contacting any number of remote SPARQL endpoints. Two optimization approaches are described. In the first approach, a static query plan is computed in advance of query execution, using one of two standard graph algorithms for finding minimum spanning trees (Edmonds' algorithm and Prim's algorithm). In the second approach, the planning and execution of the query are interleaved, so that as each potential solution is expanded it is permitted to follow an independent query plan. Our optimization approach requires basic statistics regarding RDF predicates which must be obtained prior to the user's query, through automated querying of the remote SPARQL endpoints.
@inproceedings{
title = {Optimization of distributed SPARQL queries using edmonds' algorithm and prim's algorithm},
type = {inproceedings},
year = {2009},
volume = {1},
id = {cd66cd4a-0ef2-31c7-baf0-efdccdc01b96},
created = {2017-12-03T10:44:25.790Z},
file_attached = {false},
profile_id = {17c87d5d-2470-32d7-b273-0734a1d9195f},
last_modified = {2017-12-12T09:00:53.569Z},
read = {false},
starred = {false},
authored = {true},
confirmed = {true},
hidden = {false},
private_publication = {false},
abstract = {Here we describe the application of two well known graph algorithms, Edmonds' algorithm and Prim's algorithm, to the problem of optimizing distributed SPARQL queries. In the context of this paper, a "distributed SPARQL query" is a SPARQL query which is resolved by contacting any number of remote SPARQL endpoints. Two optimization approaches are described. In the first approach, a static query plan is computed in advance of query execution, using one of two standard graph algorithms for finding minimum spanning trees (Edmonds' algorithm and Prim's algorithm). In the second approach, the planning and execution of the query are interleaved, so that as each potential solution is expanded it is permitted to follow an independent query plan. Our optimization approach requires basic statistics regarding RDF predicates which must be obtained prior to the user's query, through automated querying of the remote SPARQL endpoints.},
bibtype = {inproceedings},
author = {Vandervalk, B.P. and McCarthy, E.L. and Wilkinson, M.D.},
doi = {10.1109/CSE.2009.144},
booktitle = {Proceedings - 12th IEEE International Conference on Computational Science and Engineering, CSE 2009}
}
Downloads: 0
{"_id":"QG77Jo64A85Ga4Qrb","bibbaseid":"vandervalk-mccarthy-wilkinson-optimizationofdistributedsparqlqueriesusingedmondsalgorithmandprimsalgorithm-2009","downloads":0,"creationDate":"2018-01-15T08:18:50.431Z","title":"Optimization of distributed SPARQL queries using edmonds' algorithm and prim's algorithm","author_short":["Vandervalk, B.","McCarthy, E.","Wilkinson, M."],"year":2009,"bibtype":"inproceedings","biburl":"https://bibbase.org/service/mendeley/17c87d5d-2470-32d7-b273-0734a1d9195f","bibdata":{"title":"Optimization of distributed SPARQL queries using edmonds' algorithm and prim's algorithm","type":"inproceedings","year":"2009","volume":"1","id":"cd66cd4a-0ef2-31c7-baf0-efdccdc01b96","created":"2017-12-03T10:44:25.790Z","file_attached":false,"profile_id":"17c87d5d-2470-32d7-b273-0734a1d9195f","last_modified":"2017-12-12T09:00:53.569Z","read":false,"starred":false,"authored":"true","confirmed":"true","hidden":false,"private_publication":false,"abstract":"Here we describe the application of two well known graph algorithms, Edmonds' algorithm and Prim's algorithm, to the problem of optimizing distributed SPARQL queries. In the context of this paper, a \"distributed SPARQL query\" is a SPARQL query which is resolved by contacting any number of remote SPARQL endpoints. Two optimization approaches are described. In the first approach, a static query plan is computed in advance of query execution, using one of two standard graph algorithms for finding minimum spanning trees (Edmonds' algorithm and Prim's algorithm). In the second approach, the planning and execution of the query are interleaved, so that as each potential solution is expanded it is permitted to follow an independent query plan. Our optimization approach requires basic statistics regarding RDF predicates which must be obtained prior to the user's query, through automated querying of the remote SPARQL endpoints.","bibtype":"inproceedings","author":"Vandervalk, B.P. and McCarthy, E.L. and Wilkinson, M.D.","doi":"10.1109/CSE.2009.144","booktitle":"Proceedings - 12th IEEE International Conference on Computational Science and Engineering, CSE 2009","bibtex":"@inproceedings{\n title = {Optimization of distributed SPARQL queries using edmonds' algorithm and prim's algorithm},\n type = {inproceedings},\n year = {2009},\n volume = {1},\n id = {cd66cd4a-0ef2-31c7-baf0-efdccdc01b96},\n created = {2017-12-03T10:44:25.790Z},\n file_attached = {false},\n profile_id = {17c87d5d-2470-32d7-b273-0734a1d9195f},\n last_modified = {2017-12-12T09:00:53.569Z},\n read = {false},\n starred = {false},\n authored = {true},\n confirmed = {true},\n hidden = {false},\n private_publication = {false},\n abstract = {Here we describe the application of two well known graph algorithms, Edmonds' algorithm and Prim's algorithm, to the problem of optimizing distributed SPARQL queries. In the context of this paper, a \"distributed SPARQL query\" is a SPARQL query which is resolved by contacting any number of remote SPARQL endpoints. Two optimization approaches are described. In the first approach, a static query plan is computed in advance of query execution, using one of two standard graph algorithms for finding minimum spanning trees (Edmonds' algorithm and Prim's algorithm). In the second approach, the planning and execution of the query are interleaved, so that as each potential solution is expanded it is permitted to follow an independent query plan. Our optimization approach requires basic statistics regarding RDF predicates which must be obtained prior to the user's query, through automated querying of the remote SPARQL endpoints.},\n bibtype = {inproceedings},\n author = {Vandervalk, B.P. and McCarthy, E.L. and Wilkinson, M.D.},\n doi = {10.1109/CSE.2009.144},\n booktitle = {Proceedings - 12th IEEE International Conference on Computational Science and Engineering, CSE 2009}\n}","author_short":["Vandervalk, B.","McCarthy, E.","Wilkinson, M."],"biburl":"https://bibbase.org/service/mendeley/17c87d5d-2470-32d7-b273-0734a1d9195f","bibbaseid":"vandervalk-mccarthy-wilkinson-optimizationofdistributedsparqlqueriesusingedmondsalgorithmandprimsalgorithm-2009","role":"author","urls":{},"metadata":{"authorlinks":{"wilkinson, m":"https://bibbase.org/service/mendeley/17c87d5d-2470-32d7-b273-0734a1d9195f"}},"downloads":0},"search_terms":["optimization","distributed","sparql","queries","using","edmonds","algorithm","prim","algorithm","vandervalk","mccarthy","wilkinson"],"keywords":[],"authorIDs":["3D2gJyDWo9oBKnSCp"],"dataSources":["u3DebWvhQaEque62E","ya2CyA73rpZseyrZ8","2252seNhipfTmjEBQ"]}