{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,27]],"date-time":"2026-09-27T12:52:30Z","timestamp":1790513550686,"version":"4.1.0"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,1,4]],"date-time":"2016-01-04T00:00:00Z","timestamp":1451865600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2016,4]]},"DOI":"10.1007\/s00778-015-0415-0","type":"journal-article","created":{"date-parts":[[2016,1,4]],"date-time":"2016-01-04T16:29:34Z","timestamp":1451924974000},"page":"243-268","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":97,"title":["Processing SPARQL queries over distributed RDF graphs"],"prefix":"10.1007","volume":"25","author":[{"given":"Peng","family":"Peng","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lei","family":"Zou","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8126-1717","authenticated-orcid":false,"given":"M. Tamer","family":"\u00d6zsu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lei","family":"Chen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dongyan","family":"Zhao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,1,4]]},"reference":[{"issue":"2","key":"415_CR1","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/s00778-008-0125-y","volume":"18","author":"DJ Abadi","year":"2009","unstructured":"Abadi, D.J., Marcus, A., Madden, S., Hollenbach, K.: SW-store: a vertically partitioned DBMS for semantic web data management. VLDB J. 18(2), 385\u2013406 (2009)","journal-title":"VLDB J."},{"key":"415_CR2","doi-asserted-by":"crossref","unstructured":"Alu\u00e7, G., Hartig, O., \u00d6zsu, M.T., Daudjee, K.: Diversified stress testing of RDF data management systems. In: Proceedings of 13th International Semantic Web Conference, pp 197\u2013212 (2014)","DOI":"10.1007\/978-3-319-11964-9_13"},{"key":"415_CR3","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1145\/320455.320457","volume":"1","author":"MM Astrahan","year":"1976","unstructured":"Astrahan, M.M., Blasgen, H.W., Chamberlin, D.D., Eswaran, K.P., Gray, J.N., Griffiths, P.P., King, W.F., Lorie, R.A., Mehl, J.W., Putzolu, G.R., Traiger, I.L., Wade, B.W., Watson, V.: System R: relational approach to database management. ACM Trans. Database Syst. 1, 97\u2013137 (1976)","journal-title":"ACM Trans. Database Syst."},{"key":"415_CR4","doi-asserted-by":"crossref","unstructured":"Atre, M.: Left Bit Right: for SPARQL join queries with OPTIONAL patterns (left-outer-joins). In: Proceedings of ACM SIGMOD International Conference on Management of Data, pp 1793\u20131808 (2015)","DOI":"10.1145\/2723372.2746483"},{"key":"415_CR5","doi-asserted-by":"crossref","unstructured":"Atre, M., Chaoji, V., Zaki, M.J., Hendler, J.A.: Matrix \u201cbit\u201d loaded: a scalable lightweight join query processor for RDF data. In: Proceedings of 19th International World Wide Web Conference, pp 41\u201350 (2010)","DOI":"10.1145\/1772690.1772696"},{"key":"415_CR6","unstructured":"Buneman, P., Cong, G., Fan, W., Kementsietsidis, A.: Using partial evaluation in distributed query evaluation. In: Proceedings of 32nd International Conference on Very Large Data Bases, pp 211\u2013222 (2006)"},{"key":"415_CR7","doi-asserted-by":"crossref","unstructured":"Cong, G., Fan, W., Kementsietsidis, A.: Distributed query evaluation with performance guarantees. In: Proceedings of ACM SIGMOD International Conference on Management of Data, pp 509\u2013520 (2007)","DOI":"10.1145\/1247480.1247537"},{"issue":"4","key":"415_CR8","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1145\/2389241.2389251","volume":"37","author":"G Cong","year":"2012","unstructured":"Cong, G., Fan, W., Kementsietsidis, A., Li, J., Liu, X.: Partial evaluation for distributed XPath query processing and beyond. ACM Trans. Database Syst. 37(4), 32 (2012)","journal-title":"ACM Trans. Database Syst."},{"key":"415_CR9","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)","edition":"3"},{"issue":"2","key":"415_CR10","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1137\/S0097539797323571","volume":"29","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R., Vardy, A., Whittle, G.: The parametrized complexity of some fundamental problems in coding theory. SIAM J. Comput. 29(2), 545\u2013570 (1999)","journal-title":"SIAM J. Comput."},{"issue":"3\u20134","key":"415_CR11","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<260::AID-RSA5>3.3.CO;2-N","volume":"17","author":"ME Dyer","year":"2000","unstructured":"Dyer, M.E., Greenhill, C.S.: The complexity of counting graph homomorphisms. Random Struct. Algorithms 17(3\u20134), 260\u2013289 (2000)","journal-title":"Random Struct. Algorithms"},{"issue":"1","key":"415_CR12","doi-asserted-by":"crossref","first-page":"264","DOI":"10.14778\/1920841.1920878","volume":"3","author":"W Fan","year":"2010","unstructured":"Fan, W., Li, J., Ma, S., Tang, N., Wu, Y., Wu, Y.: Graph pattern matching: from intractable to polynomial time. Proc. VLDB Endow. 3(1), 264\u2013275 (2010)","journal-title":"Proc. VLDB Endow."},{"issue":"11","key":"415_CR13","doi-asserted-by":"crossref","first-page":"1304","DOI":"10.14778\/2350229.2350248","volume":"5","author":"W Fan","year":"2012","unstructured":"Fan, W., Wang, X., Wu, Y.: Performance guarantees for distributed reachability queries. Proc. VLDB Endow. 5(11), 1304\u20131315 (2012)","journal-title":"Proc. VLDB Endow."},{"issue":"12","key":"415_CR14","doi-asserted-by":"crossref","first-page":"1083","DOI":"10.14778\/2732977.2732983","volume":"7","author":"W Fan","year":"2014","unstructured":"Fan, W., Wang, X., Wu, Y., Deng, D.: Distributed graph simulation: impossibility and possibility. Proc. VLDB Endow. 7(12), 1083\u20131094 (2014)","journal-title":"Proc. VLDB Endow."},{"key":"415_CR15","doi-asserted-by":"crossref","unstructured":"Galarraga, L., Hose, K., Schenkel, R.: Partout: a distributed engine for efficient RDF processing. In: Proceedings of 23rd International World Wide Web Conference (Companion Volume), pp 267\u2013268 (2014)","DOI":"10.1145\/2567948.2577302"},{"key":"415_CR16","unstructured":"G\u00f6rlitz, O., Staab, S.: SPLENDID: SPARQL endpoint federation exploiting VOID descriptions. In: Proceedings of ISWC 2011 Workshop on Consuming Linked Data (2011)"},{"issue":"2\u20133","key":"415_CR17","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1016\/j.websem.2005.06.005","volume":"3","author":"Y Guo","year":"2005","unstructured":"Guo, Y., Pan, Z., Heflin, J.: LUBM: a benchmark for OWL knowledge base systems. J. Web Semant. 3(2\u20133), 158\u2013182 (2005)","journal-title":"J. Web Semant."},{"key":"415_CR18","doi-asserted-by":"crossref","unstructured":"Gurajada, S., Seufert, S., Miliaraki, I., Theobald, M.: TriAD: a distributed shared-nothing RDF engine based on asynchronous message passing. In: Proceedings of ACM SIGMOD International Conference on Management of Data, pp 289\u2013300 (2014)","DOI":"10.1145\/2588555.2610511"},{"key":"415_CR19","doi-asserted-by":"crossref","unstructured":"Harth, A., Hose, K., Karnstedt, M., Polleres, A., Sattler, K., Umbrich, J.: Data summaries for on-demand queries over linked data. In: Proceedings of 19th International World Wide Web Conference, pp 411\u2013420 (2010)","DOI":"10.1145\/1772690.1772733"},{"key":"415_CR20","doi-asserted-by":"crossref","unstructured":"Hartig, O., \u00d6zsu, M.T.: Linked data query processing (Tutorial). In: Proceedings of 30th International Conference on Data Engineering, pp 1286\u20131289 (2014)","DOI":"10.1109\/ICDE.2014.6816762"},{"key":"415_CR21","doi-asserted-by":"crossref","unstructured":"Hose, K., Schenkel, R.: WARP: Workload-aware replication and partitioning for RDF. In: Proceedings of Workshops of 29th International Conference on Data Engineering, pp 1\u20136 (2013)","DOI":"10.1109\/ICDEW.2013.6547414"},{"issue":"11","key":"415_CR22","doi-asserted-by":"crossref","first-page":"1123","DOI":"10.14778\/3402707.3402747","volume":"4","author":"J Huang","year":"2011","unstructured":"Huang, J., Abadi, D.J., Ren, K.: Scalable SPARQL querying of large RDF graphs. Proc. VLDB Endow. 4(11), 1123\u20131134 (2011)","journal-title":"Proc. VLDB Endow."},{"issue":"9","key":"415_CR23","doi-asserted-by":"crossref","first-page":"1312","DOI":"10.1109\/TKDE.2011.103","volume":"23","author":"MF Husain","year":"2011","unstructured":"Husain, M.F., McGlothlin, J.P., Masud, M.M., Khan, L.R., Thuraisingham, B.M.: Heuristics-based query processing for large RDF graphs using cloud computing. IEEE Trans. Knowl. Data Eng. 23(9), 1312\u20131327 (2011)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"3","key":"415_CR24","doi-asserted-by":"crossref","first-page":"480","DOI":"10.1145\/243439.243447","volume":"28","author":"ND Jones","year":"1996","unstructured":"Jones, N.D.: An introduction to partial evaluation. ACM Comput. Surv. 28(3), 480\u2013503 (1996)","journal-title":"ACM Comput. Surv."},{"issue":"1","key":"415_CR25","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/s00778-014-0364-z","volume":"24","author":"Z Kaoudi","year":"2015","unstructured":"Kaoudi, Z., Manolescu, I.: RDF in the clouds: a survey. VLDB J. 24(1), 67\u201391 (2015)","journal-title":"VLDB J."},{"key":"415_CR26","doi-asserted-by":"crossref","unstructured":"Karypis, G., Kumar, V.: Analysis of multilevel graph partitioning. In: Proceedings of ACM\/IEEE Conference on Supercomputing. Article No. 29 (1995)","DOI":"10.1145\/224170.224229"},{"key":"415_CR27","unstructured":"Khadilkar, V., Kantarcioglu, M., Thuraisingham, B.\u00a0M., Castagna, P.: Jena-HBase: A distributed, scalable and efficient RDF triple store. In: Proceedings of International Semantic Web Conference Posters & Demos Track (2012)"},{"issue":"14","key":"415_CR28","doi-asserted-by":"crossref","first-page":"1894","DOI":"10.14778\/2556549.2556571","volume":"6","author":"K Lee","year":"2013","unstructured":"Lee, K., Liu, L.: Scaling queries over big RDF graphs with semantic hash partitioning. Proc. VLDB Endow. 6(14), 1894\u20131905 (2013)","journal-title":"Proc. VLDB Endow."},{"key":"415_CR29","doi-asserted-by":"crossref","unstructured":"Lee, K., Liu, L., Tang, Y., Zhang, Q., Zhou, Y.: Efficient and customizable data partitioning framework for distributed big RDF data processing in the cloud. In: Proceedings of IEEE 6th International Conference on Cloud Computing, pp 327\u2013334 (2013)","DOI":"10.1109\/CLOUD.2013.63"},{"issue":"3","key":"415_CR30","first-page":"31","volume":"46","author":"F Li","year":"2014","unstructured":"Li, F., Ooi, B.C., \u00d6zsu, M.T., Wu, S.: Distributed data management using MapReduce. ACM Comput. Surv. 46(3), 31 (2014)","journal-title":"ACM Comput. Surv."},{"key":"415_CR31","doi-asserted-by":"crossref","unstructured":"Ma, S., Cao, Y., Huai, J., Wo, T.: Distributed graph pattern matching. In: Proceeding of 21st International World Wide Web Conference, pp 949\u2013958 (2012)","DOI":"10.1145\/2187836.2187963"},{"issue":"1","key":"415_CR32","doi-asserted-by":"crossref","first-page":"647","DOI":"10.14778\/1453856.1453927","volume":"1","author":"T Neumann","year":"2008","unstructured":"Neumann, T., Weikum, G.: RDF-3X: a RISC-style engine for RDF. Proc. VLDB Endow. 1(1), 647\u2013659 (2008)","journal-title":"Proc. VLDB Endow."},{"key":"415_CR33","doi-asserted-by":"crossref","unstructured":"Papailiou, N., Konstantinou, I., Tsoumakos, D., Koziris, N.: $$\\text{ H }_{{\\rm 2}}$$ H 2 RDF: adaptive query processing on RDF data in the cloud. In: Proceedings of 21st International World Wide Web Conference (Companion Volume), pp 397\u2013400 (2012)","DOI":"10.1145\/2187980.2188058"},{"key":"415_CR34","doi-asserted-by":"crossref","unstructured":"Papailiou, N., Tsoumakos, D., Konstantinou, I., Karras, P., Koziris, N.: $$\\text{ H }_{{\\rm 2}}$$ H 2 RDF+: an efficient data management system for big RDF graphs. In: Proceeding of ACM SIGMOD International Conference on Management of Data, pp 909\u2013912 (2014)","DOI":"10.1145\/2588555.2594535"},{"key":"415_CR35","doi-asserted-by":"crossref","unstructured":"P\u00e9rez, J., Arenas, M., Gutierrez, C.: Semantics and complexity of SPARQL. ACM Trans. Database Syst. 34(3), 2009","DOI":"10.1145\/1567274.1567278"},{"key":"415_CR36","doi-asserted-by":"crossref","unstructured":"Quilitz, B., Leser, U.: Querying Distributed RDF Data Sources with SPARQL. In: Proceeding of 5th European Semantic Web Conference, pp 524\u2013538 (2008)","DOI":"10.1007\/978-3-540-68234-9_39"},{"key":"415_CR37","doi-asserted-by":"crossref","unstructured":"Rohloff, K., Schantz, R.\u00a0E.: High-performance, massively scalable distributed systems using the MapReduce software framework: the shard triple-store. In: Proceeding of International Workshop on Programming Support Innovations for Emerging Distributed Applications, Article No. 4 (2010)","DOI":"10.1145\/1940747.1940751"},{"key":"415_CR38","doi-asserted-by":"crossref","unstructured":"Saleem, M., Ngomo, A.\u00a0N.: HiBISCuS: Hypergraph-based source selection for sparql endpoint federation. In: Proceeding of 11th Extended Semantic Web Conference, pp 176\u2013191 (2014)","DOI":"10.1007\/978-3-319-07443-6_13"},{"key":"415_CR39","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1186\/2041-1480-5-47","volume":"5","author":"M Saleem","year":"2014","unstructured":"Saleem, M., Padmanabhuni, S.S., Ngomo, A.N., Iqbal, A., Almeida, J.S., Decker, S., Deus, H.F.: TopFed: TCGA tailored federated query processing and linking to LOD. J. Biomed. Semant. 5, 47 (2014)","journal-title":"J. Biomed. Semant."},{"key":"415_CR40","doi-asserted-by":"crossref","unstructured":"Schmachtenberg, M., Bizer, C., Paulheim, H.: Adoption of best data practices in different topical domains. In: Proceeding of 13th International Semantic Web Conference, pp 245\u2013260 (2014)","DOI":"10.1007\/978-3-319-11964-9_16"},{"key":"415_CR41","doi-asserted-by":"crossref","unstructured":"Schmidt, M., G\u00f6rlitz, O., Haase, P., Ladwig, G., Schwarte, A., Tran, T.: FedBench: A benchmark suite for federated semantic data query processing. In: Proceeding of 10th International Semantic Web Conference, pp 585\u2013600 (2011)","DOI":"10.1007\/978-3-642-25073-6_37"},{"key":"415_CR42","doi-asserted-by":"crossref","unstructured":"Schwarte, A., Haase, P., Hose, K., Schenkel, R., Schmidt, M.: FedX: Optimization techniques for federated query processing on linked data. In: Proceeding of 10th International Semantic Web Conference, pp 601\u2013616 (2011)","DOI":"10.1007\/978-3-642-25073-6_38"},{"issue":"1","key":"415_CR43","doi-asserted-by":"crossref","first-page":"364","DOI":"10.14778\/1453856.1453899","volume":"1","author":"H Shang","year":"2008","unstructured":"Shang, H., Zhang, Y., Lin, X., Yu, J.X.: Taming verification hardness: an efficient algorithm for testing subgraph isomorphism. Proc. VLDB Endow. 1(1), 364\u2013375 (2008)","journal-title":"Proc. VLDB Endow."},{"key":"415_CR44","doi-asserted-by":"crossref","unstructured":"Shao, B., Wang, H., Li, Y.: Trinity: a distributed graph engine on a memory cloud. In: Proceeding of ACM SIGMOD International Conference on Management of Data, pp 505\u2013516 (2013)","DOI":"10.1145\/2463676.2467799"},{"issue":"8","key":"415_CR45","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1145\/79173.79181","volume":"33","author":"LG Valiant","year":"1990","unstructured":"Valiant, L.G.: A bridging model for parallel computation. Commun. ACM 33(8), 103\u2013111 (1990)","journal-title":"Commun. ACM"},{"key":"415_CR46","doi-asserted-by":"crossref","unstructured":"Wang, L., Xiao, Y., Shao, B., Wang, H.: How to partition a billion-node graph. In: Proceeding of 30th International Conference on Data Engineering, pp 568\u2013579 (2014)","DOI":"10.1109\/ICDE.2014.6816682"},{"issue":"4","key":"415_CR47","doi-asserted-by":"crossref","first-page":"265","DOI":"10.14778\/2535570.2488333","volume":"6","author":"K Zeng","year":"2013","unstructured":"Zeng, K., Yang, J., Wang, H., Shao, B., Wang, Z.: A distributed graph engine for web scale RDF data. Proc. VLDB Endow. 6(4), 265\u2013276 (2013)","journal-title":"Proc. VLDB Endow."},{"key":"415_CR48","doi-asserted-by":"crossref","unstructured":"Zhang, X., Chen, L., Tong, Y., Wang, M.: EAGRE: towards scalable I\/O efficient SPARQL query evaluation on the cloud. In: Proceeding of 29th International Conference on Data Engineering, pp 565\u2013576 (2013)","DOI":"10.1109\/ICDE.2013.6544856"},{"key":"415_CR49","doi-asserted-by":"crossref","unstructured":"Zhang, X., Chen, L., Wang, M.: Towards efficient join processing over large RDF graph using mapreduce. In: Proceeding of 24th International Conference on Scientific and Statistical Database Management, pp 250\u2013259 (2012)","DOI":"10.1007\/978-3-642-31235-9_16"},{"issue":"4","key":"415_CR50","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1007\/s00778-013-0337-7","volume":"23","author":"L Zou","year":"2014","unstructured":"Zou, L., \u00d6zsu, M.T., Chen, L., Shen, X., Huang, R., Zhao, D.: gStore: a graph-based SPARQL query engine. VLDB J. 23(4), 565\u2013590 (2014)","journal-title":"VLDB J."}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-015-0415-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00778-015-0415-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-015-0415-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T01:03:26Z","timestamp":1748739806000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00778-015-0415-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1,4]]},"references-count":50,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,4]]}},"alternative-id":["415"],"URL":"https:\/\/doi.org\/10.1007\/s00778-015-0415-0","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1,4]]}}}